Back

Converting between reverse Polish notation and infix notation

Converting between reverse polish and infix notations
We have already said that a stack is a LIFO device and we know that stacks are used to evaluate expressions. We can diagrams of the stack to help us convert between reverse Polish notation and infix notation.

Example 1
Consider the algebraic expression: 4(A + B)

This uses the infix notation. Converting it to reverse Polish notation gives 4AB+*

How can I check this is correct? I fill the stack with operands, as I see them. So 4 goes in first, followed by A, followed by B. I then get to the first operand. The rule is as follows:

    • Remove the two top items from the stack
    • Do the expression given by the operand
    • Return the result to the stack.

So I remove B and A, add them together and put the result back in the stack. (Note that A + B is the same as B + A). I then get to the multiply symbol. I remove the top two items in the stack. Multiply them and return the result to the stack. (Note that (A + B) * 4 is the same as 4 * (A + B) which is also the same as 4(A + B).

So my reverse Polish notation algebraic expression 4AB+* does indeed have the equivalent infix algebraic expression of 4(A + B) .

Example 2
Consider this sum: (3 * (6 + 2) - 4) / (3 + 7)

This uses infix notation and the answer is 2 .

Using reverse Polish notation, the sum we need to do becomes:3 6 2 + * 4 - 3 7 + /       ..... or does it? How can we check?

    • The operand 3 goes into the stack first, followed by 6 then 2. (Putting operands onto the stack is known as 'pushing' operands. Removing them is known as 'popping' operands.) We then meet the operator 'add' so we remove the top two items from the stack, the 2 and then the 6, add them to get 8 and push this back onto the stack.
    • We then get the 'multiply' operator. We pop the top two items from the stack, the 8 and the 3 and multiply them to get 24. This is pushed back onto the stack.
    • We then push the 4 onto the stack. We see the 'minus' operator next so we pop the top two items from the stack, the 4 followed by the 24 and subtract the 4 from the 24 to get 20. This is pushed onto the stack.
    • We then push 3 onto the stack, followed by 7. We then see the 'addition' operator. We pop the top two items from the stack, the 7 followed by the 3 and add them to get 10. This is pushed onto the stack.
    • We then meet the 'division' operator. We pop the top two items from the stack, the 10 followed by the 20 and divide 10 into 20 to get 2. This is pushed onto the stack.

We have the same answer using reverse Polish notation as we got using infix notation and can therefore conclude that both expressions are equivalent.

Using binary trees to convert between infix notation and reverse Polish notation
So far, we have simply confirmed whether a reverse Polish notation expression is the same as an infix expression. However, we can use binary trees to easily convert between the two.

Consider the example just done:  (3 * (6 + 2) - 4) / (3 + 7)

The binary tree for this is as follows:

If we wanted to get the infix notation from a binary tree, we would follow this algorithm, which is known as 'in-order':

1) Traverse the left sub-tree
2) Visit the root
3) Traverse the right sub-tree

This would give us: (3 * (6 + 2) - 4) / (3 + 7)

If we wanted to get the reverse Polish notation from the same binary tree, we would follow this algorithm, known as 'post-order':

1) Traverse the left sub-tree
2) Traverse the right sub-tree
3) Visit the root

This would give us: 3 6 2 + * 4 - 3 7 + /   

By the way, we could also get Polish notation from the binary tree, by traversing the tree in pre-order using this algorithm:

1) Visit the root
2) Traverse the left sub-tree
3) Traverse the right sub-tree

How does in-order and post-order traversing work?
Traversing trees requires you to understand and use recursion. You can read more about recursion here.

Traversing a tree: IN-ORDER
Using this method, we must visit the tree in this order:

    • Visit the left sub-tree.
    • Visit the root node.
    • Visit the right sub-tree.

How does this work? We visit the left sub-tree, then the node, then the right sub-tree.

    • We start at the root, node A.
    • Underneath node A is the left sub-tree (with root node B) and the right sub-tree (with root node C).
    • We must check the left sub-tree first according to our INORDER rules. Move to B.
    • But B has a left sub-tree (with a root at D) and a right sub-tree (with a root at E).
    • We must check the left sub-tree first according to our INORDER rules. Move to D.
    • D does not have a left sub-tree, so visit the node D.
    • Now check for D’s right sub-tree. It doesn’t have one.
    • We have now done the left sub-tree for the tree that has a root node at B. Now visit node B.
    • Now visit the right sub-tree of B. We move to E.
    • E doesn’t have a left sub-tree so visit E.
    • E doesn’t have a right sub-tree so move to B and because we have now completely visited the tree with the root node at B, we move up to node A. Visit node A.
    • Now visit the right sub-tree of A. We move to C.
    • C doesn’t have a left sub-tree so visit C.
    • C doesn’t have a right sub-tree so move back up to A.
    • We have now visited every node.

The order that we visited the nodes was DBEAC. We can write an algorithm to print out all of the data at the nodes, like this:

    • For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 2). If there isn’t, go to 3).
    • Repeat 1).
    • Print the current node.
    • For the current node, check whether it has a right sub-tree. If it has go to 5) else go to 6).
    • Repeat 1).
    • END

This algorithm will take a little bit of thinking about because it is a recursive algorithm.

Traversing a tree: PRE-ORDER
Using this method, we need to

    1. Visit the root node.
    2. Visit the left sub-tree.
    3. Visit the right sub-tree.

Using our previous binary tree, we would visit the nodes in the order: A B D E C. We can write an algorithm that would print out all of the data at the nodes, like this:

    • Print the current node.
    • For the current node, check if there is a left sub-tree. If there is, go to the root node for this sub-tree and then go to 1). If there isn’t, go to 3).
    • For the current node, check whether it has a right sub-tree. If it has go to 4) else go to 5).
    • Repeat 1).
    • END.

Traversing a tree: POST-ORDER
Using this method, we need to

    1. Visit the left sub-tree.
    2. Visit the right sub-tree.
    3. Visit the root node.

Using our example binary tree, the order that we would visit is: D E B C A

Back