Encyclopedia > Reverse Polish Notation

  Article Content

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

Compare to Polish notation.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Brazil

... elections in 1945, but following a military coup d'état in 1964 saw a succession of generals as president, until 1985. Brazil has since returned to a popularly elected ...

 
 
 
This page was created in 50.5 ms