Reverse Polish Notation
Reverse Polish Notation (RPN) (aka postfix notation) is an arithmetic formula notation, derived from the polish notation introduced in 1920 by the Polish mathematician Jan Łukasiewicz. RPN was invented by Australian philosopher and computer scientist Charles Hamblin in the mid-1950s, to enable zero-address memory stores.
As a user interface for calculation the notation was first used in Hewlett-Packard's desktop calculators from the late 1960's and then in the HP-35 handheld scientific calculator launched in 1972. In RPN the operands precede the operator, thus dispensing with the need for parentheses. For example, the expression 3 * ( 4 + 7) would be written as 3 4 7 + *, and done on an RPN calculator as "3", "Enter", "4", "Enter", "7", "+", "*".
Implementations of RPN are stack-based; that is, operands are popped from a stack, and calculation results are pushed back onto it. Although this concept may seem obscure at first, RPN has the advantage of being extremely easy, thence fast, for a computer to analyze due to it being a regular grammar.
| Table of contents |
|
2 Example 3 Real-world RPN use 4 See also |
The calculation: ((1 + 2) * 4) + 3 can be written down like this in RPN:
Practical implications
Example
1 2 + 4 * 3 +
The expression is evaluated in the following way (the Stack is displayed after Operation has taken place):
| Input | Stack | Operation |
|---|---|---|
| 1 | 1 | Push operand |
| 2 | 1, 2 | Push operand |
| + | 3 | Addition |
| 4 | 3, 4 | Push operand |
| * | 12 | Multiplication |
| 3 | 12, 3 | Push operand |
| + | 15 | Addition |
The final result, 15, lies on the top of the stack in the end of the calculation.
Real-world RPN use
See also