## Expression trees

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Expression trees

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.
dayrinni

Posts: 5
Joined: Sun Nov 30, 2003 1:46 pm

### Re: Expression trees

dayrinni wrote: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?
gooch

Posts: 74
Joined: Thu Sep 25, 2003 4:12 am

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

Posts: 5
Joined: Sun Nov 30, 2003 1:46 pm

dayrinni wrote: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.
gooch

Posts: 74
Joined: Thu Sep 25, 2003 4:12 am

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

Posts: 5
Joined: Sun Nov 30, 2003 1:46 pm

Use the interpreter pattern
flyweight

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.
Guest