Public Group

Binary Tree problem

This topic is 4795 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi! I´d like to know how could I evaluate an algebraic expression using a binary tree and a stack.I know I could do it recursively,but my problem is, the given tree struct(I´m programming in C) is like this: struct Arv Expr{ Atom *at; ArvExpr *left; ArvExpr *right; }; and the Atom struct is: struct Atom { type;//which can be constant,variable or operator union{ double cte;//a constant value when the atom is of type constant char op;//operator,if applicable char var;//variable,if applicable }val; } So,what I´m doing is to traverse the tree is posfix order,each time verifying if the given node is a constant,variable or operator.If it is an operator,I create a new atom with the due operator,and the same goes for a constant.But if it is a variable, I search on a vector for the due variable(an equal character) and create a new atom with the corresponding constant value(since the vector is a vector of struct with a char and with a double value inside). After doing this,I push the new atom into the stack,and keep on with the recursion till the end. Then,I supose I got a posfix expression inside the stack and start popping it to evaluate the expression(there is a stack for the operators and anothe for the operands). SO, the problem is:the evaluation function using the stack is correct,but the order I push operands and operators inside their stacks isn´t the one I want all the time.For instance,for an expression like a*(b + c) it works perfectly but when I have (b+c)*a it doesn´t,since the lower tree is "ont the contrary". People,WHAT DO I DO??=( Thanks all, Carol

Share on other sites
Oh, the joys of binary tree manipulation in C...

Anyway, the first step is to turn the tree into a sequence of commands by performing a postfix traversal of the tree.

For instance, the tree a*(b+c) becomes
a b c + *

Then, execute these commands in left-to-right order: a constant means "push the constant on the stack", a variable means "push the value of the variable on the stack" and an operation means "pop the one (if unary) or two (if binary) top elements of the stack, apply the operation, and push the result".

The example above, with a=2, b=1, c=3 works as:

Code     Stacka        2b        2 1c        2 1 3+        2 4*        8

Note that you can also perform these operations during the traversal (by executing the commands in postfix order). It is also possible to do this without a stack using the simple rule:

let value (node) =  if node.type = constant then node.val.cte  else if node.type = variable then variable_value (node.val.var)  else value node.val.op (node.left,node.right)

Share on other sites
Thanks a bunch! I ended up figuring it out on my own while taking boring Calculus classes today.And the idea was the same.It really works!

Carol

1. 1
Rutin
71
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• Forum Statistics

• Total Topics
633428
• Total Posts
3011822
• Who's Online (See full list)

There are no registered users currently online

×