Evaluating Expressions Using Reverse Polish Notation

The act of writing a program to evaluate simple mathematical expressions supplied as strings (for example, given `4+2*3`

, return `10`

) is actually not as trivial as it first appears. Difficulties arise from having to ensure that operator precedence rules are followed (including handling nested parentheses), which makes simply scanning the string and applying operations as they appear an incorrect solution. One way to correctly do this is by first converting the expression into a form known as **Reverse Polish Notation**, and then deriving the final answer from this form. Both of these steps use a data structure known as a **stack**.

A stack is an incredibly simple data structure, that despite its simplicity is used very widely in computer science. A stack holds a collection of items, but only provides operations to add/remove items from the *top* of the stack. It is analagous to a stack of plates; you can add plates to the top of the stack, and you can remove them from the top in a last-in, first-out manner, however you can’t remove a plate from the middle of the stack until you’ve removed all those above it.

The operations defined for a stack are `push(x)`

(adds x to the top of the stack), and `pop()`

(removes the item at the top of the stack, returning it). A further method `peek()`

is often also implemented, which returns the item at the top of the stack without actually removing it.

Stacks are easily represented in Python as lists - this Gist shows a simple implementation.

Reverse Polish Notation (also known as *postfix notation*) is a notation for writing expressions where operators appear after their operands (as opposed to standard *infix* notation, where the operator appears between them). For example, the infix expression `4*3`

is written as `43*`

in reverse polish notation. Wikipedia provides a nice overview.

A larger example where operator precedence rules can be observed is the infix expression `1+2*3`

, which when translated to reverse polish notation is written as `123*+`

. Notice how the order that the operations appear differs in the translated expression; these expressions are to be interpreted by reading them left to right and replacing each operator (and the operands before it) with the result of that operator with those operands (`123*+ = 16+ = 7`

). Hence this ordering performs the multiplication first as required.

This introduces a nice property of RPN; when evaluating our expression, we don’t need to consider operation precedence, or parentheses. Instead, **operations are applied as they appear**. This makes the process far simpler, and it can be seen that if we have a way of converting an infix input to a Reverse Polish Notation form, then our final answer can be calculated without too much trouble.

As stated earlier, a **stack** can be used to perform this evaluation. Taking each character from the input at a time, if it’s a number, `push()`

it onto the stack. If it’s an operator, `pop()`

two operands off of the stack (which will therefore be the operands on the top of the stack - the last two numbers in the expression), apply the operator, and `push()`

on the result. If the input was correctly formatted in Reverse Polish Notation, this method will terminate with a single value left on the stack - **the result**.

The algorithm I used to perform this step is known as the Shunting-yard algorithm, invented by Dijkstra. The Wikipedia article provides a better explanation of how it works than I can manage, however it’s quite a simple process. As stated earlier, it also uses a stack.

Essentially, for each input character, if it’s a number then shift it to the output string. If it’s an operator, it needs to be pushed to a seperate *operator stack*, and is then popped to the output when an operator of lower precedence is about to be pushed on top of it. Again, see the Wikipedia article for a better explanation.

As stated, performing these two steps in sequence (converting to Reverse Polish Notation, then evaluating that translation) will produce our answer. However, looking at these steps, they’re actually quite similar (a scan left to right, utilising a stack for operands) and they can be combined into one scan of the input for a more efficient operation.

I’ve written an implementation in Python, which also handles multiple digit numbers in the input sequence as well as the exponentiation operator `^`

(adding extra operations only requires small modification of the code). The function `calculate(infix_string)`

is the main entry point to the script, taking an expression in infix notation and returning its value.

I’ve written up this implementation in a Gist.