Reverse Polish Notation

( This is an abstact from the following site:  http://www.theteacher.freeserve.co.uk/alevel/c4/18_3.htm )

Reverse Polish (also called Postfix) Notation is a method of writing arithmetic expressions that is particularly suited to computerised methods of evaluation.

The way in which we normally write arithmetic expressions is called Infix notation, and it is not easy for a computer to evaluate such an expression.

Consider the expression

(a + b) * c

The sequence of instructions needed to evaluate this is :

1. get a
2. get b
3. add them together and store the result
4. get c
5. multiply by the result of step 3

In other words the computer really needs the operands and operators in the sequence

a b + c *

Note that there are never any brackets in a RPN expression.

Evaluation of RPN expressions using a stack.

A RPN expression may be evaluated using the following rules :

• if the next symbol is an operand, place it on the stack.
• if the next symbol is an operator, remove the top two numbers from the stack, perform the operation, and place the result back on the stack.

Example

Using a stack to evaluate the expression, the contents of the stack will be as follows :

The value of the expression is the number remaining at the top of the stack ie 21

Converting Infix notation to RPN

If the expression is written down as a binary tree and a postorder traversal of the tree is undertaken the result is the RPN expression.

Example :

Consider the expression X = A * B + C / D

To form the binary tree, place the '=' sign as the root node, the lowest precedence operators form the next level of the tree etc...

A postorder traversal (left subtree, right subtree, root) of this tree would produce the following RPN expression:

X A B * C D / + =