Parsing & Evaluating Reverse Polish Notation in Python

The Reverse Polish Noation (RPN) is a mathematical notation to define a sequence of steps where the operator follows the operand. This post will show you how to parse and evaluate them in Python. This exercise will then allow us to go one step further and write an Infix Notation evaluator to parse standard simple mathematic formulas.

Examples

For example, the following notation is used to add 3 and 5

3 5 +

If you wanted to add 3 and 5 and then multiply by 10, it will look like

3 5 + 10 *

OR it can even be represented as the following expression

10 3 5 + *

The Implementation

The algorithm can be implemented very simply by using a Stack. Interestingly, in Python the basic list data structure has the ability to work as a stack as well. The append(..) operation can be used to “push” items in the stack. The list also exposes a pop() function, which can be used to “pop”.

The expresion is read from left to right. We split the string by spaces and get a list of items to evaluate. If the item is a number, we push it down the stack. If the item is an operand, we pop two numbers from the stack, perform the operation and push the result back on the stack.

At the end, what’s left on the stack is the answer!

Implementation of RPM in Python

The main program to try parse_rpn()

The program above contains a main section that tried both of the example expressions above. The answer is the same in both cases

Output