Assignment: An Expression Evaluator

The expressionprog package contains an abstarct class ProgramItem that represents one "command" in a program for a "stack machine." That is, it represents some operation that can be carried out on a stack. There are subclasses of ProgramItem that represent specific operations: Number, Variable, BinOp, UnaryMinus, Function, Assign, and PreviousValue. For example, Number represents the operation of pushing a constant number onto the stack, and Function represents the operation of popping one number from the stack, applying some function to that number, and pushing the result back onto the stack. You can read the comments on the other classes to find out what they do.

A "program" for the stack machine is simply a list of ProgramItems. The purpose of a program is to evaluate an expression; the program is essentially a representation of the expression in postfix form. To execute a program, start with an empty stack. Apply each of the items in the list. Then pop the value of the expression from the stack.

The other main class in expressionprog is Parser. The Parser class defines one static method

            public static ArrayList<ProgramItem> parse(String expr)

This method takes a string that contains an expression in ordinary, infix form, such as "2+2" or "sqrt(x/33) * sin(degrees/180*pi)". It returns a list of ProgramItems that represent the same expression in postfix form, as a stack program. If there is some error in the input string, the parse method throws an IllegalArgumentException, and the message in the exception is an error message that describes the error.

Your assignment for this lab is to write a program that reads expressions typed in by the user. The program will parse each expression and -- if there is no error -- evaluate it and print its value. You will use the parse method from the Parser class to do the parsing. You will need a stack to do the evaluation, and you will need a symbol table to store values of variables.

Part of the assignment is to provide code to apply each type of ProgramItem to the stack. The code that I've given you does not do this. To do this neatly, you should add the following abstract method to the ProgramItem class:

public abstract void apply(Stack stack, Map symbolTable);

As soon as you do this, all the subclasses of ProgramItem will have errors, since they do not provide definitions for the abstract method. You can go into each subclass and provide a definition. (Eclipse will write an outline of the method for you!) The method should apply the operation represented by that program item to the stack. If you aren't sure what that operation should be, read the comment on the class.

Note that the symbol table is used to store values of variables. A variable in this case means a word consisting of a letter followed by letters and digits. The effect of an Assign is to store a value for a variable into the symbol table (and to leave the same value on the stack!). The effect of a Variable program item is to push the value of a variable onto the stack. You will need the symbol table for both of these operations. Before evaluating any expressions, variables named pi and e should already be defined, with values given by Math.PI and Math.E respectively.

A Function program item represents the evaluation of a function such as cos or sqrt. Your program should have a short, fixed list of functions that it understands. The list should include at least sin, cos, sqrt, abs, exp, and ln. (These can be implemented by built-in functions in the Math class.)

The PreviousValue class is meant mostly to allow the user to use the symbol "#" in an expression to represent the value of the previous expression that the user entered. This makes it easy for the user to use the value of one expression in the next expression that they enter. You can think of "#" as being a special variable whose value changes every time an expression is evaluated. To make things interesting, I also allow special variables "#1", "#2", ..., "#9". "#1" is a synonym for "#"; that is, it refers to the value of the previous expression; "#2" refers to the value of the expression before that one; and so on. You can store the values of "#1" through "#9" in the symbol table -- you just have to keep them up to date every time you evaluate an expression.

There are several things you will have to decide, such as: What to do if the user uses a variable that has not yet been assigned a value (it could be an error, or you could use the value 0 for undefined variables). What about an undefined function? Should variable and function names be case-sensitive? How will the program end (when the user enters a blank line, or when the user enters some special string such as "exit")? What do you do if the result of evaluating an expression is NaN (as for sqrt(-1)) or infinity (as for exp(1000))? The comment on your program should make your decisions in theses matters clear, so that the user knows what to expect from the program.

Here is the input/output from a sample run of my version of the program. The user's input is shown in bold:

? sin(pi/4)
Value: 0.7071067811865475

? 1 - #
Value: 0.29289321881345254

? 3+(2*
Error: Expecting a number, variable, etc, but hit the end of input.

? sqrt(2)/2
Value: 0.7071067811865476

? x1 = 17
Value: 17.0

? exp(x1) - 3*(x1/(1+x1))/2.735
Value: 2.4154951717621613E7

? x = y = 12
Value: 12.0

? x/y
Value: 1.0

By the way, you can try running the program Test in expressionprog. That program lets you type in expressions, parses them, and prints out all the program items in the parsed expression.