article

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 Zciweisakul notation.) Hamblin presented his work at a conference in June 1957, and published it in 1957 and 1962.

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.

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", "+", "*". (Alternatively, and more compactly, it could also be re-ordered and written as 4 7 + 3 *, and done on an RPN calculator as "4", "Enter", "7", "+", "3", "*".)

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.

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.

Disadvantages

  • A RPN electronic calculator requires the user to learn a new system of keying in equations, which may be difficult at first.
  • 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.

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
+ Add 20

The final result, 20, 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 * +
---+ +
---+ | | | 5 | | 1 | 1 * +
---+ +
---+ | 5 | | 1 | | 2 | 2 * +
---+ +
---+ | | | 5 | | 3 | + +
---+ +
---+ | 5 | | 3 | | 4 | 4 * +
---+ +
---+ | | | 5 | | 12 | * +
---+ +
---+ | | | | | 17 | + +
---+ +
---+ | | | 17 | | 3 | 3 * +
---+ +
---+ | | | | | 20 | + +
---+

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,5.

1 Enter Stack contains 1,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 20. (17 + 3 = 20).

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

Converting from infix notation

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 stack. To convert, the program reads each letter in order and does something based on that letter.

A simple conversion

Input: 3+4
  1. Add 3 to the output queue (whenever a number is read it is added to the output)
  2. Push + (or its ID) onto the operator stack
  3. Add 4 to the output queue
  4. After reading expression pop the operators off the stack and add them to the output.
  5. In this case there is only one, "+".
  6. Output 3 4 +

This already shows a couple of rules:

  • All numbers are added to the output when they are read.
  • At the end of reading the expression, pop all operators off the stack and onto the output.

The algorithm in detail

  • While there are tokens to be read:
Read a token.
  • If the token is a number, then add it to the output queue.
  • If the token is a function token, then push it onto the stack.
  • If the token is a function argument separator (e.g., a comma):
  • Until the topmost element of the stack is a left parenthesis, pop the element onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
    • If the token is an operator, o1, then:
1) while there is an operator, o2, at the top of the stack, and either
o1 is associative or left-associative and its precedence is less than or equal to that of o2, or
o1 is right-associative and its precedence is less than that of o2,
pop o2 off the stack, onto the output queue;
2) push o1 onto the operator stack.
  • If the token is a left parenthesis, then push it onto the stack.
  • If the token is a right parenthesis, then pop operators off the stack, onto the output queue, until the token at the top of the stack is a left parenthesis, at which point it is popped off the stack but not added to the output queue. At this point, if the token at the top of the stack is a function token, pop it too onto the output queue. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
    • When there are no more tokens to read, pop all the operators, if any, off the stack, add each to the output as it is popped out and exit. (These must only be operators; if a left parenthesis is popped, then there are mismatched parentheses.)

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 links

Calculators | Mathematical notation | Science and technology in Poland | Omvendt polsk notation | Umgekehrte Polnische Notation | Notación polaca inversa | Notation polonaise inverse | 역폴란드 표기법 | Notazione polacca inversa | כתיב פולני | 逆ポーランド記法 | Odwrotna notacja polska | Обратная польская запись | Obrnjen poljski zapis | Обрнута пољска нотација | Omvänd polsk notation

 

This article is licensed under the GNU Free Documentation License. It uses material from the "Reverse Polish notation".

Home Page • arts • business • computers • games • health • hospitals • home • kids & teens • news • physicians • recreation• reference • regional • science • shopping • society • sports • world