Reverse Polish notation

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with Polish notation. (Discuss)

Reverse Polish notation (RPN), also known as postfix notation, was invented by Australian philosopher and computer scientist Charles Hamblin in the mid-1950s, to enable zero-address memory stores. It is derived from the Polish notation, which was introduced in 1920 by the Polish mathematician Jan Łukasiewicz. (Hence the suggested name Łukasiewicz notation.) Hamblin presented his work at a conference in June 1957, and published it in 1957 and 1962.

1 Explanation
2 Practical implications
3 Disadvantages
4 Example
- 4.1 The RPN algorithm
5 Converting from infix notation
6 Implementations
7 See also
8 External links

[edit] Explanation

In RPN the operands precede the operator, removing 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", "+", "*". One could reorder this expression, putting the operand directly after each pair of values such as, 4 7 + 3 *. The reordered form would be entered as "4", "Enter", "7", "+", "3", "*". Both expressions are equivalent, but the first requires more memory as all operands must be stored prior to the application of their respective operators. In the second expression the result of the addition of 4 and 7 would be stored on the stack as the variable 11 where the multiplication with 3 is calculated. In the first method 3, 4, and 7 must be stored before any calculations. The second method only requires two memory locations to be stored regardless of the expression's length or complexity. The first method's memory requirements depend directly on the number of operands in the equation.

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.

[edit] Practical implications

Calculations proceed from left to right.
There are no brackets or parentheses, as they are unnecessary.
There is no Equals key, but there is an Enter key.
Operands precede their operator. They are removed as the operation is evaluated.
When an operation is performed, the result becomes an operand itself (for later operators).
There is no hidden state: no need to wonder if an operator was entered or not.
Fewer keystrokes are needed on an RPN calculator than on an algebraic notation calculator for most computations.
For a computer, it is easier and faster to evaluate mathematical expressions written in RPN than mathematical expressions written in infix notation.

[edit] Disadvantages

The widespread use of standard ordered equations (infix) in educational systems (and therefore infix electronic calculators being the norm in classrooms) can make RPN impractical, hard, and hindering at times. (However, it is easy for a computer to convert infix notation to RPN, most notably Dijkstra's Shunting yard algorithm)
Most RPN electronic calculators have programmable functions and multiple memory registers. In formal examinations (such as licensing examinations) calculators with such extended functions are often banned, but using a simple infix calculator is both allowed and available.

[edit] Example

The calculation: 5 + ((1 + 2) * 4) - 3 can be written down like this in RPN:

5 1 2 + 4 * + 3 -

The expression is evaluated in the following way (the Stack is displayed after Operation has taken place):

Input	Operation	Stack
5	Push operand	5
1	Push operand	5, 1
2	Push operand	5, 1, 2
+	Add	5, 3
4	Push operand	5, 3, 4
*	Multiply	5, 12
+	Add	17
3	Push operand	17, 3
-	Sub	14

The final result, 14, lies on the top of the stack at the end of the calculation.

An alternate way of viewing the stack during the above operation is shown below (as seen on HP48S calculator).

+---------------+
|               |
|               |
|             5 |  5 [enter]
+---------------+

+---------------+
|               |
|             5 |
|             1 |  1 [enter]
+---------------+

+---------------+
|             5 |
|             1 |
|             2 |  2 [enter]
+---------------+

+---------------+
|               |
|             5 |
|             3 |  + 
+---------------+

+---------------+
|             5 |
|             3 |
|             4 |  4 [enter]
+---------------+

+---------------+
|               |
|             5 |
|            12 |  * 
+---------------+

+---------------+
|               |
|               |
|            17 |  +
+---------------+

+---------------+
|               |
|            17 |
|             3 |  3 [enter] 
+---------------+

+---------------+
|               |
|               |
|            14 |  -
+---------------+

The enters are in brackets because they are optional when followed by an operator press. An enter is only needed to clear the insertion mark from the line. Thus, RPN allows the expression to be entered and evaluated in nine rather than twelve or thirteen steps.

Not all RPN calculators behave the same way as above. More typically, when a number is pushed onto the stack, it also remains at the top of the stack until another number is entered, or an operator is pressed. On many RPN calculators, the problem illustrated above will be processed as follows:

5 + ((1 + 2) * 4) - 3

5 Enter

Stack contains 5.

1 Enter

Stack contains 1,5.

2 +

Stack contains 3,5. (2 replaces the first 1, is added to the second 1. 2+1=3).

4 *

Stack contains 12,5. (4 * 3 = 12).

Stack contains 17. (12 + 5 = 17).

3 -

Stack contains 14. (17 - 3 = 14).

The result is 14. This approach cuts the problem to 5 steps.

[edit] The RPN algorithm

Generalizing the above example, we can easily describe a method to evaluate any RPN expression:

While there are input tokens left
- Read the next token from input.
- If the token is a number
  - Push it onto the stack.
- Otherwise, the token is a function. (Operators, like +, are simply functions taking two arguments.)
  - It is known that the function takes n arguments.
  - So, pop the top n values from the stack.
    - If there are fewer than n values on the stack
      - (Error) The user has not input sufficient values in the expression.
  - Evaluate the function, with the values as arguments.
  - Push the returned results, if any, back onto the stack.
If there is only one value in the stack
- The value is the result of the calculation.
If there are more values in the stack
- (Error) The user input too many values.

[edit] Converting from infix notation

Main article: Shunting yard algorithm

Edsger Dijkstra invented an algorithm, named the "shunting yard" algorithm because its operation resembles that of a railroad shunting yard, which converts from infix notation to RPN. Like the evaluation of RPN, the shunting yard algorithm 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 string. To convert, the program reads each letter in order and does something based on that letter.

There are other ways of producing output in Reverse Polish from infix notation. Most Operator-precedence parsers can be modified to produce RPN, in particular an abstract syntax tree can be used as an intermediate step.

[edit] Implementations

The first computers to implement architectures enabling RPN were the English Electric Company's KDF9 machine, which was announced in 1960 and delivered (i.e. made available commercially) in 1963, and the American Burroughs B5000, announced in 1961 and also delivered in 1963. One of the designers of the B5000, R. S. Barton, later wrote that he developed RPN independently of Hamblin, sometime in 1958 while reading a textbook on symbolic logic, and before he was aware of Hamblin's work.

Friden introduced RPN to the desktop calculator market with the EC-130 in June of 1963. Hewlett-Packard (HP) engineers designed the 9100A Desktop Calculator in 1968 with RPN. This calculator popularized RPN among the scientific and engineering communities, even though early advertisements for the 9100A failed to mention RPN. The HP-35 handheld scientific calculator brought RPN to the first scientific pocket calculator in 1972. The HP-10C series of calculators, including the famous financial calculator the HP-12C, all used RPN. When Hewlett-Packard introduced a later business calculator, the HP-19B, without RPN, feedback from financiers and others used to using the 12-C compelled them to release the HP-19BII, which gave users the option of using algebraic notation or RPN.

Existing implementations of RPN include: