Post Order Traversal Formula

Question

I am given 2 y 5 1 4 3 - * - * +, and am asked to evaluate it, and then draw the equivalent expression tree. I haven't done any work with this before, can someone show the steps you would take to solve this type of question?

I have looked at: Post order traversal of a formula and am confused as to how to come to that answer.

Answer 1

What you are given is a postfix expression. It is well-known that these things are evaluated with stacks according to the following rule:

Working left to right, when you encounter a value, push it. When you encounter an operator, pop the top two values, apply the operation, and push the result back.

So your expression evaluation proceeds like this

2               (push 2)
2 y             (push y)
2 y 5           (push 5)
2 y 5 1         (push 1)
2 y 5 1 4       (push 4)
2 y 5 1 4 3     (push 3)
2 y 5 1 1       (pop 3, pop 4, push 4-3)
2 y 5 1         (pop 1, pop 1, push 1*1)
2 y 4           (pop 1, pop 5, push 5-1)
2 4y            (pop 4, pop y, push y*4)
2+4y            (pop 4y, pop 2, push 2+4y)

Your answer is the value left on the stack.

Now, you asked about producing a tree also. To produce a tree, rather than evaluating the expression when you find an operator, you "apply" the operator by building a tree fragment with the operator as the root, and the popped tree fragments as children.

So after pushing

2 y 5 1 4 3

you see a -, so you pop the 4 and 3 and you push back this structure

  -
 / \
4   3

Next you see the * so you pop the top tree fragment and the one below it, which is actually a tree fragment consisting of the single node

1

So it will look like

   *
 /   \
1     -
     / \
    4   3

You should be able to take it from here.

Answer 2

The answer at Post order traversal of a formula says find the first operator. In your case it is '-'. The second step he describes is put it between the previous two operands. In your case these two operands are 4 and 3 (they are directly before the '-'). So the formula after this step becomes:

2 y 5 1 (4-3) * - * +

Remember that the expression (4-3) is now one operand.

We apply the steps again to this formula. We see that the first operator now is ''. The two operands before the '' are 1 and (4-3). The formula becomes:

2 y 5 (1*(4-3)) - * +

Now you can apply this untill all operators are gone.

I will not continue giving more steps because probably this is a homework question. However I think it is clear?

Answer 3

As stated by novalis from the question you linked, scan for the first operator and previous 2 operands and then replace that group with a more familiar expression in parentheses, ie.

if you have:

op1 op2 operator
4    3     -

this becomes:

(op1 operator op2)
(4      -      3 )

so, proceeding...

2  y  5  1  4  3 -  *  -  *  +

2  y  5  1 (4 - 3)  *  -  *  +

2  y  5  (1 * (4 - 3)) -  *  +

Proceed in a similar fashion to build the tree. Scan for the first operator and create a tiny tree:

  -
 / \
4   3

Then, each new operand is the top node of your new tree:

   *
 /   \
1     -
     / \
    4   3

and then:

   -
  / \
 5   *
    / \
   1   -
      / \
     4   3