Reverse polish notation (otherwise known as post-fix, RPN for short) is a way of representing mathematical expressions. The notation is used because the format that the expression is in is easier for machines to interpret rather than the notation we are used to, infix notation, where the operator is in between the numbers. The equation can be complex or simple. RPN doesn't require brackets as the equations are laid out in such a format that they aren't required for machines to understand.
There is no inherent reason why operators should be written between the operands, as they are with the standard arithmetic operators. The operators could come before the operands (prefix), between (infix), or after (postfix). Here is the same expression written in three formats:
|Prefix notation||Infix notation||Postfix notation|
|× 3 4||3 × 4||3 4 ×|
We are used to seeing arithmetic written infix and functions written in prefix notation, often with brackets (e.g.
sqrt(9) to express the operation of taking a square root). We could write arithmetic in the same form, such as using Python's
>>> import operator >>> operator.add(operator.mul(3, 4), 2) 14
Advantages of postfix notationEdit
Neither prefix nor postfix notation require brackets to express grouping of operations: the order of evaluation is dictated solely by the order of operations.
Infix notation can only easily express operations that take one or two parameters (such as binary addition or square roots). Operations that take more than two parameters require typographic embellishments such as brackets.
|3 4 +||3 + 4||7|
|5 6 + 3 *||(5 + 6) * 3||33|
|2 4 / 5 6 - *||(2/4)*(5-6)||-0.5|
|2 3 ↑||2³||8|
Evaluation of Reverse Polish expressionsEdit
Expressions stated in reverse Polish notation can be simply evaluated using a stack. As the expression is read, values are pushed onto the stack. When an operation is read, values are popped from the stack and the result pushed back on the stack. The result left on the stack is the overall value of the expression.
The use of a stack and uniform precedence rules makes it very easy to write code to calculate the results of reverse polish expressions.
Using a slightly more complex example than above, evaluation of "3 4 × 10 2 ÷ +" can proceed as follows:
|3 4 × 10 2 ÷ +||
||Stack is empty at the start of the evaluation|
|4 × 10 2 ÷ +||
||Value 3 is pushed|
|× 10 2 ÷ +||
||Value 4 is pushed|
|10 2 ÷ +||
||× operator pops two items off the stack, multiplies them, and pushes the result back on the stack|
|2 ÷ +||
||Value 10 is pushed|
||Value 2 is pushed|
||÷ operator pops two items off the stack, divides one by the other, and pushes the result back on the stack|
||+ operator pops two items off the stack, adds them, and pushes the result back on the stack|
The result left on the stack, 17, is the overall value of the expression.
x y +
x y + z *
3 5 y x * + /
x * y
(5 + y) / (z * (x - 3))
YouTube Video ExampleEdit
- Video link to Computerphile a Youtube channel: https://www.youtube.com/channel/UC9-y-6csu5WGm29I7JiwpnA