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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
def parse_rpn(expression): """ Evaluate a reverse polish notation """ stack = [] for val in expression.split(' '): if val in ['-', '+', '*', '/']: op1 = stack.pop() op2 = stack.pop() if val=='-': result = op2 - op1 if val=='+': result = op2 + op1 if val=='*': result = op2 * op1 if val=='/': result = op2 / op1 stack.append(result) else: stack.append(float(val)) return stack.pop() |
The main program to try parse_rpn()
|
1 2 3 4 5 6 7 8 9 10 |
if __name__ == '__main__': expression = '10 3 5 + *' result = parse_rpn(expression) print result expression = '3 5 + 10 *' result = parse_rpn(expression) print result |
The program above contains a main section that tried both of the example expressions above. The answer is the same in both cases
Output
|
1 2 3 |
80.0 80.0 |