Reverse Polish notation

I'm currently working my way through chapter four of The C Programming Language. The majority of the exercises in the chapter focus on developing a calculator program, however the implementation uses Reverse Polish notation, also known as postfix notation.

There is an excellent YouTube video on the topic, however this post is quickly going to go over some of the key points.

Infix notation

Even if you're not familiar with the name, you've almost certainly come across Infix notation. When infix notation is used operators are placed between operands. For example:

a + b

In the example above the operator, +, is placed between the two operands, a, and b. This becomes slightly more complex for expressions which contain multiple operators:

a + b * c

In the example above the * operator will be evaluated before + operator due to the order of operations. If you want to change the order the operations are performed, you can use brackets:

(a + b) * c

This can make parsing expressions significantly more complex.

Postfix notation

As the name suggests, postfix notation places the operator after the operands. For example:

a b +

Like infix notation, it's also possible to include multiple operators:

a b c * +

The expression above is equivalent to a + b * c.

Replacing brackets

Unlike infix notation, the order operators are evaluated is based on position, and can be changed without brackets by repositioning the operators. For example (a + b) * c can be expressed as follows

a b + c *

This is one of the main reasons postfix notation is easier than infix notation to evaluate programmatically.

Evaluating expressions

Expressions can be evaluated with the following pseudo code:

for each token in the postfix expression:
  if token is an operator:
    operand_2 <- pop from the stack
    operand_1 <- pop from the stack
    result <- evaluate token with operand_1 and operand_2
    push result back onto the stack
  else if token is an operand:
    push token onto the stack
result <- pop from the stack

Note: the algorithm above assumes each operator always takes two operands.

For example the expression 1 2 3 * + would be evaluated as follows:

1. Push 1 onto the stack
2. Push 2 onto the stack
3. Push 3 onto the stack
4. Remove 2 and 3 from the stack, multiply 2 and 3 and push the result (6) back onto the stack
5. Finally remove 1 and 6 from the stack, add them together, and put the result (7) back onto the stack

The animation below illustrates these steps: