2. Reverse Polish Notation

Although we are very familiar with the infix method of setting out an expression, there is another way called Reverse Polish Notation or postfix notation that will get you to the same answer.

For example a standard infix expression looks like


where the + operator is placed between the numbers being added. And the answer is 9 of course.

In reverse polish notation, the same expression is set out as follows

4 5 +

The rule is that the operator acts upon the preceding two numbers. Therefore adding 4 and 5 together is still 9. But why use this curious method?

Well, it happens to be, that reverse polish can be used in conjunction with the CPU stack to evaluate expressions. This will be explained on the next page.

Let's work on a less trivial example to show that infix and reverse polish are equivalent. Consider the expression below

6*(4+5) - 25/(2+3)

The answer is 49

The same expression laid out in reverse polish look like

6 4 5 + * 25 2 3 + / -

To work it out, start from the left and go to the first operator then carry out that operation on the preceding two numbers. So .. (ignore the presence of the grey part, it is only there to remind you what the full expression look like)

6 4 5 + * 25 2 3 + / -


6 9 * 25 2 3 + / -

the next operator is a multiply * so the expression is now

6 9 * 25 2 3 + / -

which is 54, so the expression up to the next operator look like

54 25 2 3 + / -

so add the 2 and 3 together to make 5, the expression is now

54 25 5 / -

The next operator is a divide, so divide 25 by 5 to get the expression so far as

54 5 -

So finally subtract 5 from 54 and the answer is 49. The same as the infix expression.

By laying out the expression in reverse polish, you avoid the use of brackets to determine precedence. We will use the same example on the next page to show how the stack can be used to work out the answer.

Challenge see if you can find out one extra fact on this topic that we haven't already told you

Click on this link: Reverse Polish Notation



Copyright © www.teach-ict.com