Reverse Polish Notation
Reverse Polish is a notation for writing mathemtatical expressions for easier processing by computers. It is named for Polish mathematician Jan Lucasiewicz, who invented the method.
Normally we write a calculation with the operator (+ - x ÷) in the middle of the numbers being worked on:
3 + 4
The above is called infix notation. In Reverse Polish Notation (RPN) though, we instead put the operator at the end:
3 4 +
Here’s another example:
(3+4)×2
In Reverse Polish we would write it like this:
3 4 + 2 x
Now let’s look at a more complicated expression:
5 + ( (3 + 4) + (8 + 7) x (1 + 3) )
To evaluate the expression (calculate the answer), following the conventional mathematical ordering, we do this:
- Add 8 and 7 and memorise the result.
- Then add 1 and 3
- Multiply the result of 1+3 by the 8+7 result that we memorised previously. Then we memorise the result of that calculation.
- Add 3 and 4
- Add the result of 3+4 to the previously memorised result.
- Then finally we add that to 5 and get the answer which is 72
In Reverse Polish notation though, we write the expression strictly in the order that it is evaluated, such as like this:
8 7 + 1 3 + x 3 4 + + 5 +
This is the exact ordering we used above. The meaning is:
- 8 and 7 (added)
- 1 and 3 (added)
- Multiply the two previous results
- 3 and 4 (added)
- Add the two previous results
- 5 is now added to the previous result to get 72
So why are we doing this? The reason this notation is useful is that it greatly simplifies the circuits needed to construct a calculator (or the software needed in a computer). Many early calculators did not have the sophistication to process mathematics in the way we would normally write it. These early calculators would only accept Reverse Polish notation and could not perform infix calculations at all.
To perform the calculation for the infix (normal) version of the expression, the calculator needs to see the whole expression first before it can work out what it needs to do to calculate the answer. Firstly, this means it needs the memory available to store the entire expression before processing it, which used to be a problem, but also it needs circuitry to understand mathematical order of precedence, further circuitry to determine what part of the expression to do next and jump around within the expression. When evaluating Reverse Polish though none of this circuitry is necessary. The calculator simply starts at the left of the expression and works to the right, one step at a time. This is a much simpler circuit to build.
Modern computer software (such as a spreadsheet) does have the sophistication to be able to process infix expressions as we would normally write them and Reverse Polish calculators have long since gone the way of vinyl records. Even so, Reverse Polish is still relevant to modern software. While a user no longer has to grapple with such things, internally it is still common for software to first convert infix expressions into Reverse Polish. This is because it makes the subsequent calculation of the result so much simpler and efficient compared with trying to do it from the infix version.
Reverse Polish is usually evaluated using a stack. As we encounter a number we push it onto the stack. When we encounter an operator, we pop (remove) the last two numbers from the stack and do the relevant operation with the two numbers retrieved. We then push the result back on the stack.
The following table shows an example of the evaluation of the above Reverse Polish expression. The left hand column shows the Reverse Polish, one element at a time. The right hand column shows the contents of the stack after the element in the left hand column has been evaluated.
| Reverse Polish | Stack |
|---|---|
| 8 | 8 |
| 7 | 7,8 |
| + | 15 |
| 1 | 1, 15 |
| 3 | 3, 1, 15 |
| + | 4, 15 |
| x | 60 |
| 3 | 3, 60 |
| 4 | 4, 3, 60 |
| + | 7, 60 |
| + | 67 |
| 5 | 5, 67 |
| + | 72 |
In the first row, we got 8 and pushed 8 onto the stack. Then we got 7 and pushed it onto the stack. Then in the 3rd row we got plus, we popped two numbers from the stack, added them and then pushed the result (15) back onto the stack and so on.
This ordering is not the only ordering that works though. There are orderings that turn out to be more convenient for the process of conversion of infix notation into Reverse Polish. We won’t cover the algorithms for doing this here, but a popular method called the “shunting yard algorithm” produces Reverse Polish like this for the above expression:
5 3 4 + 8 7 + 1 3 + x + +
We can see how this produces the same answer by working through the calculation and the stack:
| Reverse Polish | Stack |
|---|---|
| 5 | 5 |
| 3 | 3, 5 |
| 4 | 4, 3, 5 |
| + | 7, 5 |
| 8 | 8, 7, 5 |
| 7 | 7, 8, 7, 5 |
| + | 15, 7, 5 |
| 1 | 1, 15, 7, 5 |
| 3 | 3, 1, 15, 7, 5 |
| + | 4, 15, 7, 5 |
| x | 60, 7, 5 |
| + | 67, 5 |
| + | 72 |
Image credit: Friden 132 Reverse Polish calculator - Wendy Kaveney
.jpg){kind=link}