What is reverse Polish?
Reverse Polish notation removes the need for parentheses in an arithmetic expression. Operator priorities are represented by the order in which they occur. Consequently, reverse Polish provides a programmatic method of evaluating complex expressions using trees and stacks. Complex arithmetic expressions in high level language computer programs may be converted into reverse Polish by the compiler when a program is prepared for execution.
Infix, Prefix and Postfix forms
The following expression has been written in the form you are familiar with. This is known as infix notation:
5 + 6
The following expression is equivalent. It has been written in Polish notation. This is known as prefix notation:
+ 5 6
The following expression is equivalent. It has been written in reverse Polish notation. This is known as postfix notation:
5 6 +
Operator priorities
The arithmetic expression (2 + 3) * 4 which is written in normal infix form evaluates to 20. As you know, the contents of the parentheses must be evaluated first. You may have come across the acronym BODMAS (Brackets Order, Division, Multiplication, Addition, Subtraction), or the acrostic sentence Please Excuse My Dear Aunt Sally (Parentheses, Exponentiation, Multiplication, Division, Addition, Subtraction), both of which specify the correct order of operations in a complex arithmetic expression.
Evaluating reverse Polish
The normal (infix) expression (2 + 3) * 4, when written in reverse Polish (postfix) form is: 2 3 + 4 *
To evaluate this, you must read the expression from left to right and apply any operator that you encounter to the two values on the left of it, then remove the operator. For example:
2 3 + 4 *
becomes…
5 4 *
then
5 4 *
becomes…
20
There are two alternative forms of reverse Polish, both of which are valid. This is the other reverse Polish form of the same expression: 4 2 3 + *
This equivalent form of reverse Polish is evaluated as follows:
Read the expression from left to right, and apply the operator to the two values on the left of it, then remove the operator:
4 2 3 + *
becomes…
4 5 *
then
4 5 *
becomes…
20
Examples
The following pairs of arithmetic expressions are equivalent:
| Normal (infix) | Reverse Polish (postfix) |
| (4 + 8) / (1 + 3) | 4 8 + 1 3 + / |
| 28 / (6 + 2 * 4) | 28 6 2 4 * + / |
| (4 + 2 * 5) / (1 + 3 * 2) | 4 2 5 * + 1 3 2 * + / |
Example evaluation
4 2 5 * + 1 3 2 * + /
becomes…
4 10 + 1 3 2 * + /
then
4 10 + 1 3 2 * + /
becomes…
14 1 3 2 * + /
then
14 1 3 2 * + /
becomes…
14 1 6 + /
then
14 1 6 + /
becomes…
14 7 /
then
14 7 /
becomes
2
Try this
Convert the following infix expression into reverse Polish:
(5 + 7) / ((8 – 6) * 3)
NOTE:
Polish notation, also known as prefix notation, was invented by the Polish born philosopher and logician Jan Kukasiewicz in the 1920s. This involved putting arithmetic operators together at the start of an expression. It was later reinvented in the 1960s by a number of people, including Edsgar Dijkstra, specifically for use in computing.
