Reverse Polish Notation

Reverse Polish Notation (RPN, or postfix notation) is an arithmetic formula notation, introduced in 1920 by the Polish mathematician Jan Łukasiewicz[?]. 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 comes with a calculator program that uses RPN: dc.

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: ((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

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
• Hewlett-Packard calculators

Compare to Polish notation.