parserbaum

hallo

ich möchte für ein programm, was einen funktionsgraphen darstellen soll, einen
parserbaum benutzen. das funktioniert zwar, allerdings sehen einige stellen
unschön aus, was wahrscheinlich ein designfehler ist.

struct node
{
    virtual ~node(){}
    virtual double eval() = 0;
	virtual node **getleft() = 0;
	virtual node **getright() = 0;
	virtual unsigned getpriority() = 0;
};

davon erben klassen wie add, sub, mul... etc, die einfach nur ihre
child-zeiger kapseln und diese auswerten können.
exemplarisch man die "add" klasse:

class add : public node
{
public:
    add(node *n1, node *n2)
    {
		left = n1;
        right = n2;
    }
    ~add()
    {
        delete right;
        delete left;
    }
    double eval()
    {
        return left->eval() + right->eval();
    }
	node **getleft()
	{
		return &left;
	}
	node **getright()
	{
		return &right;
	}
	unsigned getpriority()
	{
		return 1;
	}
private:
    node *left, *right;
};

um den baum aufzubauen nutze ich folgende funktion (gekürtzt):

node *build(const char *&str, const char *end)
{
	node *n = 0;
    while (str != end)
    {
		if (*str <= '9' && *str >= '0')
		{
			double val = 0.0;
			// val einlesen
			n = new num(val);
		}
        else if (*str == '+')
		{
			if (!n)
				n = new num(0.0);

			node *right = build(++str, end);
			if (!right)
			{
				delete n;
				return 0;
			}
			n = new add(n, right);
		}
		else if (*str == '-')
		{
			// subtraktion
		}
		else if (*str == '*')
		{
			if (!n)
				return 0;

			node *right = build(++str, end);
			if (!right)
			{
				delete n;
				return 0;
			}
			n = new mul(n, right);
			n = correct(n, right); // <---
		}
		else if (*str == '(')
		{
			// klammern
		}
    }
	return n;
}

auch das funktioniert, allerdings wird nur die reihenfolge beachtet
und nicht die priorität. deshalb muss man manuell nachhelfen:

node *correct(node *a, node *b)
{
	if (a->getpriority() == b->getpriority())
		return a;

	node *child1 = *a->getleft();
	node *child2 = a->getpriority() < b->getpriority() ? *a->getright() : *b->getleft();
	node *child3 = *b->getright();
	if (!child1 || !child2 || !child3)
		return a;

	if (a->getpriority() > b->getpriority())
	{
		node *temp = a;
		a = b;
		b = temp;
		temp = child1;
		child1 = child3;
		child3 = temp;
	}

	*a->getleft() = child1;
	*a->getright() = b;
	*b->getleft() = child2;
	*b->getright() = child3;
	return a;
}

frage: geht das auch einfacher? wie sollte man den baum aufbauen?

*push*

Badestrand

Zu der Node könntest du noch eine Oberklasse "BinaryOperator" oder so deklarieren, welche die Verwaltung des linken und rechten Knotens übernimmt. Oder du machst überhaupt keine spezifischen Klassen für die einzelnen Knoten, sondern gibst einer flexiblen BinaryOperator-Klasse die eval-Funktion als Funktionszeiger mit, zusätzlich die Priorität (obwohl man die imho gar nicht in der Klasse braucht).

bäumchenparser schrieb:

wie sollte man den baum aufbauen?

Ich bin leider kein Parser-Experte und kenne auch nur zwei Möglichkeiten:

a) Du lässt dir den Baum generieren, indem du einem Compiler-Compiler (z.B. Lex + Yacc) die Syntax angibst und dieser dir daraus C(++) Sourcecode generiert.

b) Der selbe Weg zu Fuß: Du unterteilst den Input-Sourcecode in Tokens (ein Token besteht aus der Art:Keyword/Operator/Quote/... und dem zugehörigen Text/Wert) und baust dann aus der Token-Liste die Strukturen und Parserbäume auf. Eine primitive Methode dabei wäre, jeweils die Token-Liste nach dem höchstwertigen Operator zu durchsuchen und an diesen Links und Rechts die Knoten dranzuhängen, die sich bei einem rekursiven "buildTree"-Aufruf mit dem linken bzw rechten Teilstück ergeben.

knivil

Du kannst hier auch gern im Forum suchen, das Thema gab es schon oefters. Lex+Yacc parsen nur deinen Ausdruck, den Gleichungsbaum musst du dir schon selbst erzeugen. Mit Lex+Yacc ist es aber viel einfacher. Die Tutorials sind dahingehend recht gut. Die frei Variante heisst flex + bison.

Bashar

Es gibt auch Parsergeneratoren, die Syntaxbäume erstellen können, z.B. ANTLR. Hab ich aber noch nicht benutzt.