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.
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,
b. This becomes slightly more complex for expressions which contain
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.
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.
Unlike infix notation, the order operators are evaluated is based on position,
and can be changed without brackets by repositioning the operators. For
(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.
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:
1onto the stack
2onto the stack
3onto the stack
3from the stack, multiply
3and push the result (
6) back onto the stack
- Finally remove
6from the stack, add them together, and put the result (
7) back onto the stack
The animation below illustrates these steps: