Post order traversal of a formula

Question

In data structures, I get converting in order and pre-order formula conversions into trees. However, I'm not so good with post-order.

For the given formula x y z + a b - c * / -

I came up with

                   -
                 /   \
                *     / (divide)
               / \    / \   
              x  +    -  c
                / \  /\
               y  z a  b 

For the most part, this seems to fit, except the * in the left subtree is the joker in the deck. In post order traversal, the last character is the top node of the tree, everything else branches down. Now I take the / and * operators to mean that they should be on opposing nodes. However, when traversing tree, everything fits except for the *, since the left subtree has to work up to the node prior to the root, then switch over to the right subtree.

A nudge in the right direction is appreciated.

Answer 1

Actually, it's easier to write a program that parses a post-order expression than one that parses it in-order, because you don't have to check the priorities of operations.

Try this: make a stack, and add to it the operands as you find them (left to right). When you find an operation, extract the number of operands it expects from the stack and put back a small tree. When you finish it, you'll have only one result in the stack : the final graph.

Ex:

x y z +  ->  x   +
               /  \
              y    z

Answer 2

Go in order. First, write out the entire stack again:

x y z + a b - c * / -

Now, starting at the left, look for the first operator. Replace it and the previous two operands, right there in the stack, with a little in-order bit:

x (y + z) a b - c * / -

Continue with the next operator:

x (y + z) (a - b) c * / -

Then the next:

x (y + z) ((a - b) * c) / -

x ((y + z) / ((a - b) * c)) -

x - ((y + z) / ((a - b) * c))

Now, to make it a tree, just start at the middle (which you already know as it's the last element in the original stack), and hang parenthesized subexpressions from it, outside-to-inside.