Sign in to follow this  
Carolina

Binary Tree problem

Recommended Posts

Carolina    176
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 this post


Link to post
Share on other sites
ToohrVyk    1596
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 Stack
a 2
b 2 1
c 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 this post


Link to post
Share on other sites
Carolina    176
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this