Reverse Polish Notation
Reverse Polish Notation (RPN, or postfix notation) is an arithmetic formula notation, derived from one introduced in 1920 by the Polish mathematician Jan Łukasiewicz. RPN was invented by Australian philosopher and computer scientist, Charles Hamblin in the middle 1950s, to enable zero-address memory stores. It was popularized by the HP-35 calculator in the 1970s. In this notation, 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 + *.
Implementations that use 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 for a computer to analyze due to it being a regular grammar. RPN has been used in Hewlett-Packard calculators as well as in some programming languages such as Forth and PostScript. Most Unix systems also come with a calculator program, dc, that uses RPN.
| Table of contents |
|
2 Example |
Practical implications
Example
The calculation: ((1 + 2) * 4) + 3 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 |
Examples of RPN Use
Compare to Polish notation.
See also Subject Object Verb, Subject Verb Object.
