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.
Practical implications
- Calculations proceed from left to right\n* There are no brackets or parentheses, as they are unnecessary.\n* Operands precede operator. They are removed as the operation is evaluated.\n* When an operation is made, the result becomes an operand itself (for later operators)\n* There is no hidden state. No need to wonder if you hit an operator or not.
Example
The calculation: ((1 + 2) * 4) + 3 can be written down like this in RPN:\n 1 2 + 4 * 3 +\nThe expression is evaluated in the following way (the Stack is displayed after Operation has taken place):
\n| Input | Stack | Operation |
|---|
\n| 1 | 1 | Push operand |
\n| 2 | 1, 2 | Push operand |
\n| + | 3 | Addition |
\n| 4 | 3, 4 | Push operand |
\n| * | 12 | Multiplication |
\n| 3 | 12, 3 | Push operand |
\n| + | 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 \nshow below (as seen on HP48S calculator).\n
\n +---------------+\n + +\n + +\n + 1 + [1] [enter]\n +---------------+
+---------------+\n + +\n + 1 +\n + 2 + [2] [enter]\n +---------------+
+---------------+\n + +\n + +\n + 3 + [+] \n +---------------+
+---------------+\n + +\n + 3 +\n + 4 + [4] [enter]\n +---------------+
+---------------+\n + +\n + +\n + 12 + [*] \n +---------------+
+---------------+\n + +\n + 12 +\n + 3 + [3] [enter]\n +---------------+
\n +---------------+\n + +\n + +\n + 15 + [+] \n +---------------+\n
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\n #Add 3 to the output stack (whenever a number is read it is added to the output)\n #Add 4 to the output stack\n #Push + (or it's ID) onto the operator stack\n #After reading expression pop the operators off the stack and add them to the output. In this case there is only one, "+".\n #Output 3 4 +
This already shows a couple of rules:\n* All numbers are added to the output when they are read.\n* At the end of reading the expression, pop all operators off the
stack and onto the output.
The algorithm in detail
- Read character.\n** If the character is a number then add it to the output.\n** If the character is an operator then do something based on the various situations:\n*** If the operator has a higher precedence than the operator at the top of the stack or the stack is empty, push the operator onto the stack.\n*** If the operator's precedence is less than or equal to the precedence of the operator at the top of the stack stack then pop operators off the stack, onto the output until the operator at the top of the stack has less precedence than the current operator or there is no more stack to pop. At this point, push the operator onto the stack. \n** If the character is a left-parenthesis then push it onto the stack.\n** If the character is a right-parenthesis then pop an operators off the stack, onto the output until the operator read is a left-parenthesis at which point it is popped off the stack but not added to the output. If the stack runs out without finding a left-parenthesis then there are mismatched parenthesis.\n** If there are no more characters after the current, pop all the operators off the stack and exit. If a left-parenthesis is popped then there are mismatched parenthesis.\n* After doing one or more of the above steps, go back to the start.
Complex example
Input 3+4*2/(1-5)^2\n Read "3"\n Add "3" to the output\n Output: 3\n Read "+"\n Push "+" onto the stack\n Output: 3\n Stack: +\n Read "4"\n Add "4" to the output\n Output: 3 4\n Stack: +\n Read "*"\n Push "*" onto the stack\n Output: 3 4\n Stack: + *\n Read "2"\n Add "2" to the output\n Output: 3 4 2\n Stack: + *\n Read "/"\n Pop "*" off stack and add it to output, push "/" onto the stack\n Output: 3 4 2 *\n Stack: + /\n Read "("\n Push "(" onto the stack\n Output: 3 4 2 *\n Stack: + / (\n Read "1"\n Add "1" to output\n Output: 3 4 2 * 1\n Stack: + / (\n Read "-"\n Push "-" onto the stack\n Output: 3 4 2 * 1\n Stack: + / ( -\n Read "5"\n Add "5" to output\n Output: 3 4 2 * 1 5\n Stack: + / ( -\n Read ")"\n Pop "-" off stack and add it to the output, pop (\n Output: 3 4 2 * 1 5 -\n Stack: + /\n Read "^"\n Push "^" onto stack\n Output: 3 4 2 * 1 5 -\n Stack: + / ^\n Read "2"\n Add "2" to output\n Output: 3 4 2 * 1 5 - 2\n Stack: + / ^\n End of Expression\n Pop stack to output\n 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
References
Category:Calculators
\n\n