Short assignment: Reverse Polish Notation

For this short assignment, you will implement an interpreter, like the Python interpreter. (A very tiny interpreter, of course!) An interpreter takes a human-readable string, parses it (breaks it down into smaller parts, called tokens), and then computes something based on those tokens.

One thing an interpreter might need is a way to evaluate mathematical expressions. In this section, we’ll see how to use stacks to do this.

Take the very simple expression “3 + 4”, stored as a string. We could perhaps write a program that looked at characters from the string from left to right. First, we see the number 3. Then we see the operator +, and we realize that the operator + indicates to add the number before it, and the number after it. Finally, we get the 4, and do the addition.

The order of operations makes things trickier. Consider the string “3 + 4 * 2”. We get a 3. Then a +. Then a 4. Do we add 3 and 4? No, not yet. Then we get a * operator. Then a 2. Now multiply 4 and 2, and finally add 3 and 8. You can imagine that parentheses might make things even worse. The difficulty with computing expressions like “3 + 4 * 2” is that while we might like to process the string from left to right, the order in which computations are performed could be complicated.

Reverse Polish Notation is a way of writing mathematical expressions that easily described the order in which to perform computations, without the need for any order of operations or parentheses. Here is how you might write the above expression: “3 4 2 * +”.

Let’s compute the value of “3 4 2 * +”, reading characters from the string left to right. 3 is a number. Store it in your head. 4 is a number; store it. Then store 2. Then we see an operator, *. The * operator needs two numbers to operate on, so take the two most recent numbers that you stored, 2 and 4, multiply them, and replace them in your head with the result, 8. Then we see a the operator +. Take the two most recent numbers in your head, 8 and 3, add them, and replace those numbers with the result, 11.

An algorithm to compute Reverse Polish expressions can use a stack to provide the “last in, first out” mechanic that allows us to access the most recent numbers when we see an operator. Below is the approach for evaluating an expression in RPN. In the psuedocode, a token is a number or an operator in the string; tokens are separated by spaces.

Create an empty stack
For each token (either a number or a operator) in our RPN expression:
  If the token is a number
    Push the number onto the stack
  If the token is a operator
    Pop two numbers off of the stack
    Operate and push the result onto the stack

In a correctly written RPN expression, there will be one item left in the stack — pop it off and that is the answer

Here is a demonstration of the algorithm at work. (Visualization by Daniel Shanker ’16.)

What to do

Write an interpreter for reverse polish notation. You interpreter should consist of a function, compute_rpn(), which should take as input a string consisting of integers and operators separated by spaces, and output the computed value of the reverse polish notation. You’ll probably want to write other helper functions as well. You may use integer division. The .split() method of the string class may be helpful to you.

Also include some test code that calls the compute_rpn() function for several legal expressions (strings). Here are two starting tests for you. (You should add at least five more, including some simple and some more complex.

print(compute_rpn("5 4 -"))               # should print 1
print(compute_rpn("5 13 1 - 4 / + 4 *"))  # should print 32

Notice something slightly tricky here. 54− means 5 − 4, not 4 − 5. So make sure you get the order correct as you pop values from the stack and apply operators to them.

Challenge problem (no extra points, not required)

For the intrepid, here is a fun extension to the assignment.

If you’d like to extend the basic solution beyond the four basic arithmetic operators, you might notice that for each new operator you add, you have to do a fair amount of typing, maybe adding an if-statement or something for each case.

But what if you built a dictionary that mapped from operators (keys in the dictionary) to functions (values in the dictionary)? Could you skip the if statements?

By the way, Python has some useful functions built-in, in the operator module. (Just do from operator import * if you’d like to have access to add, not, etc. You could grab sqrt from the math library. Indeed, you can call any function you like this way, and need not limit yourself to integer values. You are now ready to write an interpreter for your own programming language.