Reverse Polish Notation

ianmcloughlin.github.io linkedin github

Reverse Polish Notation (RPN) is a syntax for mathematical expressions. Where the number of operands each operator takes is fixed, RPN does not require any brackets or precedence of operators to unambiguously represent an expression.

Example

Consider the following expression:

$ ((5 + 4) \times 9) \div (6 - 3) $

This expression is written in infix notation. The binary operators are written in-between their two operands. The operators are the common addition, subtraction, multiplication and division operators. The operands are the numbers to which these operators are applied: 5, 4, 9, 6 and 3.

In RPN, this expression is:

$\begin{array}{ccccccccc} 5 & 4 & + & 9 & \times & 6 & 3 & - & \div \end{array}$

The difference is that the operator is written after its operands rather than between them.

Benefits of RPN

Infix is so common, why use RPN instead? There are at least two benefits.

First, RPN does not require bracketing. Infix notation requires brackets for expressions such as $(3 + 4) \times 5$. Without them, 4 would be multiplied 5 giving 20, which in turn would be added to 3. This follows the usual convention of giving multiplication a higher precedence than addition. That would give the result as 23, rather than the correct answer of 35. In fact, RPN does not require any hierarchy of operators at all.

Second, RPN expressions can be evaluated using a simple algorithm. The algorithm involves a single pass of reading the expression from left to right. The intermediate calculations can be done as they arise. Contrast this with expressions in infix notation such as $3 + 4 \times 5$. In this case the expression must be fully read from left to right before the expression can be interpreted. So RPN uses less memory and less instructions.

Evaluation and the Stack

Let’s evaluate the above RPN expression:

$\begin{array}{ccccccccc} 5 & 4 & + & 9 & \times & 6 & 3 & - & \div \end{array}$

Evaluation can be done using a single stack. A stack is a data structure that permits only two operations: pushing and popping. Pushing involves placing an item on the top of the stack. This is the only way to put a new item into the stack, to place it on top. Popping involves removing the item from the top of the stack. This is the only way to remove an item from the stack, to take the top item. In this way, a stack is a last-in-first-out mechanism. The last item in must be the first item out.

In evaluating an RPN expression, a stack is used to store numbers. These numbers can be either the original operands in the expression or the result of applying some operators in the expression to some operands.

An RPN expression is read item by item from left to right. Two simple rules are used as each item is read. The first is applied when the item is a number: push the number to the top of the stack. The second is applied when the item is an operator: (1) pop the first element off the stack, (2) pop the next element off the stack, (3) apply the operator to them, and (4) push the result to the top of the stack. So, the rules are:

Number: push number to stack.

Operator: pop twice from stack, apply operator, push result.

The following table depicts the stack as each symbol of our example RPN expression is read.

$$\def\arraystretch{1.5} \begin{array}{r|ccccccccc} \textrm{RPN} & 5 & 4 & + & 9 & \times & 6 & 3 & - & \div \\ \hline & & & & & & & 3 & & \\ & & 4 & & 9 & & 6 & 6 & 3 & \\ \textrm{Stack}&5 & 5 & 9 & 9 & 81 & 81 & 81 & 81 & 27 \\ \hline \end{array}$$

When the first item, $5$ is read, it is a number, so it’s pushed to the empty stack. The second item, $4$, is a number too, so it is pushed to the stack. The third is the operator $+$, so the top item $4$ on the stack is popped, then the next item $5$ is popped. The numbers are added to give $9$, and the $9$ is pushed to the stack. The final answer is what is left on the stack once the full expression has been read. This will always be a single number if the expression is valid.

Order of the operands

One technicality to watch out for is the order of the operands. Addition and multiplication are commutative so the order does not matter: $4+5=5+4=9$. However, with subtraction and division order does matter: $5-4 \neq 4-5$.

In RPN, using the everyday operators like plus and minus, the convention is for $5 \ 4 \ -$ to mean $5-4$, and not $4-5$. It doesn’t really matter, so long as we agree on what we mean and are consistent. Consider the following idea: creating a new operator $\ominus$ that is defined as $5 \ominus 4 = 4 - 5$. Then we can use $\ominus$ in our RPN expressions. So, $5 \ 4 \ \ominus$ in RPN would evaluate as $5 \ominus 4 = 4 - 5$ in infix.

Valid RPN expressions

What combinations of operators and operands constitute valid RPN expressions? The expression

$\begin{array}{ccc} + & - & 5 \\ \end{array}$

is clearly not valid. Neither is

$\begin{array}{cc} 5 & + \\ \end{array}$

because there aren’t enough operands.

Valid RPN expressions always have one more operand than they have operators. Every operator needs two operands. Two operators need three operands, three need four, and so on. The stack algorithm will only work when:

There are at least two numbers on the stack whenever an operator is read.
There is exactly one number on the stack when the end of the expression is reached.

The first rule implies that every RPN expression must begin with two numbers. The second rule implies that every RPN expression must end with an operator. We should say every valid RPN expression with more than one number, because a number by itself is a valid RPN expression.

While necessary, these conditions are not sufficient. For example, the expression

$\begin{array}{ccccccccc} 1 & 2 & 3 & + & + & + & 4 & 5 & + \\ \end{array}$

starts with two numbers and ends with an operator. It even has the correct number of operators relative to numbers. However, upon reading the third $+$ symbol, the stack has only a single item on it and the operator cannot be applied. At every step in parsing the RPN expression we must have seen more numbers than operators.

Evaluation trees

RPN expressions can be decomposed into evaluation trees. An evaluation tree for an RPN expression has operators for internal vertices, where their operands are their children, and the numbers in the expression are the leaves. The first operand for an operator is drawn as the left-most child, and last is the right-most. So, our example expression

$\begin{array}{ccccccccc} 5 & 4 & + & 9 & \times & 6 & 3 & - & \div \end{array}$

becomes

                  ┏━━━┓
            ╭─────┨ ÷ ┠─────╮
            │     ┗━━━┛     │
          ┏━┷━┓           ┏━┷━┓
        ╭─┨ × ┠─╮       ╭─┨ - ┠─╮
        │ ┗━━━┛ │       │ ┗━━━┛ │
      ┏━┷━┓   ┏━┷━┓   ┏━┷━┓   ┏━┷━┓
    ╭─┨ + ┠─╮ ┃ 9 ┃   ┃ 6 ┃   ┃ 3 ┃
    │ ┗━━━┛ │ ┗━━━┛   ┗━━━┛   ┗━━━┛
  ┏━┷━┓   ┏━┷━┓
  ┃ 5 ┃   ┃ 4 ┃  
  ┗━━━┛   ┗━━━┛

Conversion

You can convert an infix expression to RPN using the Shunting Yard Algorithm by Edsger Dijkstra.