Expression trees

[dayrinni]

I have to write one of these and I dont know how. My text book doesn't have one and the explaination in the lab book does not explain what it did. So I am pretty much clueless on how to write one of these. Thanks for any help you can give me.

[gooch]

I have to write one of these and I dont know how. My text book doesn't have one and the explaination in the lab book does not explain what it did. So I am pretty much clueless on how to write one of these. Thanks for any help you can give me.

an expression tree, usually, is just a binary tree which holds an expression.

for example ..

Code: Select all


          *(A)
         /  \
       +(B)9(E)
      /  \
    3(C)7(D)

the letters in parentheses are justnames given to the nodes, to be used in the following explanation.


this tree would represent the expression (3 + 7) * 9. to evaluate it, you simply find the value of each node. value(A) is equal to value(B) * value(E). value(B) is equal to value(C) + value(D). evaluation, then, is done post-order.


how you get an expression into a tree is another subject.

does this help?

[dayrinni]

I am having problems with getting the expession in the tree and clearing a tree after before the program ends or by command.

[gooch]

I am having problems with getting the expession in the tree and clearing a tree after before the program ends or by command.

well, as far as getting the expression in the tree.. i would use a basic recursive descent parser. there's ample information on the algorithm, which is actually relatively easy to code, on the web.. so i won't repeat it here. if you need help, or have any questions about RDP, ask.

as far as clearing the tree .. i tend to have each node be a class, and in the destructor of that class it deletes its children. then all you have to do is delete the root node.

this is probably a bit late of a post to be of any help, though, eh? oh well.

[dayrinni]

I managed to get to write it after awhile, but thank you for your help!

[flyweight]

Use the interpreter pattern

[Guest]

For example take expressions that dont hav parenteses eg 5-4/3+7
the parse tree would be s follows

-
5 4/3+7
+
4/3 7
/
4 3

you can create the parse tree by scanning the expression from left to right looking for for a +,-,* or / operator (use precedence to decide where to stop) the spilt then expression into two sub expressions and so on you can the build and evaluate the expression recursively. the interpreter pattern describes the way you should set up the classes.

eg heres some (psuedo) code demonstrating the interpreter

the actual scanning and spliting of the expressions is up to you

class expression
{
//..
double evaluate() = 0;
//...
};

class plusexpression : public expression
{
//..
double evaluate()
{
return operand1->evaluate() + operand2->evaluate();
}
protected:
expression* operand1;
expresson* operand2;

};

//
class minusexpression : public expression
{
//..
double evaluate()
{
return operand1->evaluate() - operand2->evaluate();
}
protected:
expression* operand1;
expresson* operand2;

};


class divideexpression : public expression
{
//..
double evaluate()
{
return operand1->evaluate() / operand2->evaluate();
}
protected:
expression* operand1;
expresson* operand2;

};

and so on..
Lookup the interpretor pattern for more details

as can be seen expressions parsers are not as trival as one might think

alternatively

u can use a stack technique that pushes the opetarors and values on two stacks and pops them back off in correct order of precedencs using left to right scan.