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 'inorder':
1) Traverse the left subtree
2) Visit the root
3) Traverse the right subtree
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 'postorder':
1) Traverse the left subtree
2) Traverse the right subtree
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 preorder using this algorithm:
1) Visit the root
2) Traverse the left subtree
3) Traverse the right subtree
How does inorder and postorder traversing work?
Traversing trees requires you to understand and use recursion. You can read more about recursion here.
Traversing a tree: INORDER
Using this method, we must visit the tree in this order:

 Visit the left subtree.
 Visit the root node.
 Visit the right subtree.
How does this work? We visit the left subtree, then the node, then the right subtree.

 We start at the root, node A.
 Underneath node A is the left subtree (with root node B) and the right subtree (with root node C).
 We must check the left subtree first according to our INORDER rules. Move to B.
 But B has a left subtree (with a root at D) and a right subtree (with a root at E).
 We must check the left subtree first according to our INORDER rules. Move to D.
 D does not have a left subtree, so visit the node D.
 Now check for D’s right subtree. It doesn’t have one.
 We have now done the left subtree for the tree that has a root node at B. Now visit node B.
 Now visit the right subtree of B. We move to E.
 E doesn’t have a left subtree so visit E.
 E doesn’t have a right subtree 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 subtree of A. We move to C.
 C doesn’t have a left subtree so visit C.
 C doesn’t have a right subtree 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 subtree. If there is, go to the root node for this subtree 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 subtree. 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: PREORDER
Using this method, we need to
 Visit the root node.
 Visit the left subtree.
 Visit the right subtree.
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 subtree. If there is, go to the root node for this subtree and then go to 1). If there isn’t, go to 3).
 For the current node, check whether it has a right subtree. If it has go to 4) else go to 5).
 Repeat 1).
 END.
Traversing a tree: POSTORDER
Using this method, we need to
 Visit the left subtree.
 Visit the right subtree.
 Visit the root node.
Using our example binary tree, the order that we would visit is: D E B C A