Jump to content
  • Advertisement
Sign in to follow this  
Carolina

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.

If you intended to correct an error in the post then please contact us.

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


Link to post
Share on other sites
Advertisement
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!