Reverse Polish notation
Reverse Polish Notation (RPN) is an arithmetic formula notation, introduced by Polish mathematician Jan Łukasiewicz.
Implementations that use RPN are stack-based; that is, operands are popped from a stack, and calculation results are pushed back into it. Although this concept may seem obscure at first, RPN has the advantage of being extremely easy for a computer to analyze due to it being a regular grammar.
Practical implications
From the practical point of view, in RPN:
- Calculations proceed from left to right
- There are no brackets or parentheses, as they are unnecessary.
- Operands precede operator. They are removed as the operation is evaluated.
- When an operation is made, the result becomes an operand itself (for later operators)
Example
For instance, the calculation: 3 + (4 * (1 + 2)) can be written down like this in RPN:
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.
Examples of RPN Use
- Forth programming language
- PostScript
- Texas Instruments TI-48 and Hewlett-Packard HP-92 calculators
Compare to Polish notation.