A2 Computing - Unit 3
Reverse Polish Notation

Some Terms

Study the following expression,

3 + 4

In this expression, the numbers 3 and 4 are called operands. The + symbol is called the operator.

The notation used here is called infix, because the operator appears between the operands.

Infix

Inifx notation works nicely for human beings. We tend not to think about the need to read and interpret all of these symbols since, once learned, they tend to make sense to us instantly.

There are some points of confusion with infix. For example,

3 + 4 * 5

This expression is ambiguous. We would normally want to use parentheses to ensure that the correct operation is performed first. This means the expression in infix would be one of the following,

( 3 + 4 ) * 5
3 + ( 4 * 5)

The need for parentheses is the main issue with infix. In order to get a machine to work this way, it needs to know how to deal with the brackets. This adds avoidable complexity to the process. Machines would need to store more information during calculations as well as require more complex setup for simple arithmetic operations.

Reverse Polish Notation

In RPN or postfix, the operator follows the operands and parentheses are not used. For example, the infix expression (3 + 4) * 5 is written in RPN as,

3 4 + 5 *

There are many advantages to this,

  • No need for parentheses to avoid ambiguity
  • Calculations occur as soon as an operator is specified
  • RPN uses a stack. Intermediate results are available for later use, RPN calculators have no limit on the complexity of the expressions that can be evaluated
  • No equals key or equivalent needs to be included in an expression for it to be evaluated

RPN is easily implemented in a computer since it can be performed using a data structure called a stack. In a stack, objects are added to the top and removed from the top. This is sometimes called last-in, first-out or LIFO. As a postfix expression is read from left to right, operands are placed on top of the stack. Operators are applied to the operands at the top of the stack.

Examples

Infix

2 + ( 3 * 4 )
( x + y ) / ( x - y )
x ^ 2
x + ( y ^ 2 )

RPN

2 3 4 * +
x y + x y - /
x 2 ^
x y 2 ^ +