Reverse Polish notation
Reverse Polish notation (RPN) , also known as 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 1960s 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, and therefore fast, for a computer to analyze due to it being a regular grammar.
| Table of contents |
|
2 Example 3 Converting from Infix Notation 4 Real-world RPN use 5 See also 6 External references |
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.
An alternate way of viewing the stack during the above operation is show below (as seen on HP48S calculator).
+---------------++ ++ ++ 1 + [1] [enter]+---------------+
+---------------++ ++ 1 ++ 2 + [2] [enter]+---------------+
+---------------++ ++ ++ 3 + [+]+---------------+
+---------------++ ++ 3 ++ 4 + [4] [enter]+---------------+
+---------------++ ++ ++ 12 + [*]+---------------+
+---------------++ ++ 12 ++ 3 + [3] [enter]+---------------+
+---------------++ ++ ++ 15 + [+]+---------------+
Converting from Infix Notation
Like the evaluation of RPN, conversion from Infix notation to RPN is stack-based. Infix expressions are the form of math most people are used to, for instance 3+4 or 3+4*(2-1). For the conversion there are 2 text Variables (Strings), the input and the output. There is also a stack holding operators not yet added to the output stack. To convert, the program reads each letter in order and does something based on that letter.
A simplistic conversion
Input: 3+4
#Add 3 to the output stack (whenever a number is read it is added to the output)
#Add 4 to the output stack
#Push + (or it's ID) onto the operator stack
#After reading expression pop the operators off the stack and add them to the output. In this case there is only one, "+".
#Output 3 4 +
This already shows a couple of rules:
The algorithm in detail
Complex example
Input 3+4*2/(1-5)^2
Read "3"
Add "3" to the output
Output: 3
Read "+"
Push "+" onto the stack
Output: 3
Stack: +
Read "4"
Add "4" to the output
Output: 3 4
Stack: +
Read "*"
Push "*" onto the stack
Output: 3 4
Stack: + *
Read "2"
Add "2" to the output
Output: 3 4 2
Stack: + *
Read "/"
Pop "*" off stack and add it to output, push "/" onto the stack
Output: 3 4 2 *
Stack: + /
Read "("
Push "(" onto the stack
Output: 3 4 2 *
Stack: + / (
Read "1"
Add "1" to output
Output: 3 4 2 * 1
Stack: + / (
Read "-"
Push "-" onto the stack
Output: 3 4 2 * 1
Stack: + / ( -
Read "5"
Add "5" to output
Output: 3 4 2 * 1 5
Stack: + / ( -
Read ")"
Pop "-" off stack and add it to the output, pop (
Output: 3 4 2 * 1 5 -
Stack: + /
Read "^"
Push "^" onto stack
Output: 3 4 2 * 1 5 -
Stack: + / ^
Read "2"
Add "2" to output
Output: 3 4 2 * 1 5 - 2
Stack: + / ^
End of Expression
Pop stack to output
Output: 3 4 2 * 1 5 - 2 ^ / +
If you were writing an interpreter, this output would be tokenized and written to a compiled file to be later interpreted. Conversion from Infix to RPN can also allow for easier computer simplification of expressions. To do this, act like you are solving the RPN expression, however, whenever you come to a variable its value is null, and whenever an operator has a null value, it and its parameters are written to the output (this is a simplification, problems arise when the parameters are operators). When an operator has no null parameters its value can simply be written to the output. This method obviously doesn't include all the simplifications possible.
Real-world RPN use
See also
External references