Useful Links

How I will run your code

Save your program in a file called proj.ml in folders called proj1 and proj2 respectively for phases 1 and 2 of your project.

I will test your code in the same environment as the lab machines in MI 302, using the commands

  /usr/bin/ocaml proj.ml

Phase 2 Assignment

For phase 2 of your project, you will implement an interpreter for a simple RPN calculator language, described below. You should submit your program in a folder called proj2, and be sure that it runs as described above.


Your program will read characters from standard in, scan them into tokens, and interpret the tokens in the RPN language described below. There are only three tokens: numbers (which can include both floating-point numbers and integers, with or without - signs), variables (any string of letters, uppercase or lowercase), and operations (described below). You should use the built-in regular expression facilities of Ocaml to scan the input for these tokens. As usual, tokens can be separated by any amount of whitespace.

Your program will be an interpreter for a simple Reverse Polish Notation (RPN) calculator. The basic syntax of this language is that we have some operands, which for us will be either numbers or variable names, and operators, which will be detailed below. A program for this calculator is just a series of operands and operators.

RPN calculators work by maintaining a single stack of operands. Whenever the next token is an operand, we just push it onto the stack. If the next token is an operator, we pop off some elements of the stack, apply the operator, and push the result of the operation back onto the stack. You can Google RPN to get lots more information.

The operators in your RPN language will be as follows:

To implement this, you will need regular expressions for all the token types, and you will also need to maintain a stack as usual for RPN calculators. Your stack will contain both numbers and variable names. To implement the variables, you will of course need to maintain a symbol table as well.


You are free to implement this in any way you wish. However, I recommend you proceed in the following steps.

  1. For starters, forget about variables. First just tokenize integers from the input, and push them all onto a big stack. It is probably a good idea to print out the stack contents at every step along the way for debugging. (You should of course remove this debugging output for your final submission.)
  2. Now start implementing the operations. Start with the easy ones like plus and minus. Get all the operations working with just numbers before you add the set operation or any variables.
  3. Now add variables. This will require a change in your data structure for the stack. Namely, you will need to store variable names on the stack as well as integers. I recommend creating a new data type that can be either a number or a variable. This should have methods like getValue(), which will either return the number or look up the variable in the symbol table, and setValue(...), which will return an error if we have a number, and otherwise modify the symbol table accordingly.
  4. Make sure you test your code extensively.

Style Requirements

You do not have to create your program in the exact way that I have suggested. However, for full credit your program should


After your RPN interpreter is working, I should be able to type in

5 2 + p

and your interpreter should print 7.

Here's a more complicated example:

2 3 d * d 4 + p - p

should print