CPSC 225, Spring 2019
Lab 9: Symbol Table
In this lab, you will use a symbol table and a stack to evaluate expressions that can contain variables and functions. You are not required to implement the table or stack; you can use the built-in types HashMap<String,Double> and Stack<Double>. (Stack<Double> implements a standard stack, with push and pop operations.) Both classes are defined in package java.util.
Even more importantly, perhaps, this lab will give you a chance to work with a non-trivial class hierarchy consisting of an abstract class, ProgramItem, and six sub-classes. You will add a new method to the existing classes in this hierarchy.
You will need a copy of the entire folder /classes/cs225/expressionprog in your project. You should copy-and-paste this entire folder — not the individual files in the folder — into the src folder of your project. This directory contains several classes, in a package named expressionprog, that you will use as a starting point for your work.
If you are working on your own computer, you can download the entire folder as a zip file, expressionprog.zip. There is also a copy of the zip file in /classes/cs225.
This lab is due next Tuesday, as usual. You will modify some existing classes, and you will write a new class with a main() routine. Please name the main program Calc.java. Copy Calc.java and the entire expressionprog folder into a folder named lab9 inside your homework folder. I will print out Calc.java and one or two of the classes that you have modified.
What the Program Will Do
You will write a main program, Calc.java, that lets the user type in arithmetic expressions, checks them for errors, and evaluates them. An expression can be an assignment statement that assigns a value to a variable. The user can make up any variable name they want to use. In addition to variables made up by the user, there are special variables #, #1, #2, #3, #4, .... #1 represents the value of the first expression typed in by the user; #2 represents the second value; and so on. The variable named # is always equal to the value of the previous expression. The expression can use certain functions, such as sin(x) and sqrt(x); there is no way to define new functions. Here is a session with my program, with the user's input in bold:
Enter expressions; press return to end. ? 2 + 2 #1: 4.0 ? sin(pi/2) #2: 1.0 ? #1 + 3 #3: 7.0 ? x = 17 #4: 17.0 ? sqrt(x-1) * 3 #5: 12.0 ? # + x #6: 29.0 ? sin(3+) ERROR: Found illegal or unexpected character ")" in input. ? cos(y) ERROR: Undefined variable y ? rate = 0.05 #7: 0.05 ? principal = 10000 #8: 10000.0 ? principal = principal + rate*principal #9: 10500.0 ?
In the third expression, note that #1 is 4.0, the value of the first expression. In expression number 6, the value of # is 12.0, the value from expression number 5.
Assignment: Stack and SymbolTable Operations
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, and Assign. 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 and get the value of the expression, you will start with an empty stack. Then apply each of the items from the list of ProgramItems that represents the program. Finally, you can pop the value of the expression from the stack.
However, as it stands, there is no code for applying ProgramItems to a stack. The nice, object-oriented way to add that code is to program each kind of program item so that it knows how to apply itself to a stack. To implement that, add the following abstract method to the ProgramItem class:
public abstract void apply(Stack<Double> stack, HashMap<String, Double> 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 will need to go into each subclass and provide a definition. (Eclipse can write an outline of the method for you!) The method should apply the operation represented by that ProgramItem to the stack. If you aren't sure what that operation should be, read the comment on the class. All the information that you need is there!
Note that the symbol table is used to store values of variables. The symbol table is a parameter to the apply() method, but most of the ProgramItem subclasses do not use the symbol table. However, a Variable needs the symbol table to find the value of the variable, and an Assign needs the symbol table so that it can assign a value to the variable.
A Function 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, and ln. (These can be implemented by built-in functions in the Math class. The function ln(x) is the natural logarithm function, which in Java is given by Math.log(x).) It should be an error if a function in an expression is not in your list of defined functions.
Assignment: Evaluating Expressions
The other part of the assignment is to write a main program that reads and evaluates expressions. For that, you should created a new class named Calc. It can be either in the expressionprog package or in the default package.
The program must convert a string that is typed in by the user into a stack machine program. For that, you will use the Parser class, defined in Parser.java. 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 an ArrayList of ProgramItems that represent the same expression in postfix form, as a stack program. You can then evaluate the expression by calling the apply() method for each ProgramItem in the list. 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. If the exception is e, you can get the error message by calling e.getMessage().
The program ParserTest.java reads and parses expressions that are typed in by the user, but instead of evaluating them, it prints out all the ProgramItems in the resulting program. The basic outline of your Calc.java will be very similar to ParserTest.java.
Your program will need a HashMap<String,Double> to serve as the symbol table. Note that you will use the same symbol table throughout the program. At the start of the program, you should add "pi" and "e" to the symbol table as predefined variables, with values given by Math.PI and Math.E. Each time your program evaluates an expression, it should update the value of the special variable "#", and it should define a new special variable named "#1" for the first expression, "#2" for the second expression, and so on.
You will need a Stack<Double> to use for evaluating expressions. You can either use the same stack throughout the program, or you can create a new one for each 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 zero for undefined variables). Should variable and function names be case-sensitive? What do you do if the result of evaluating an expression is NaN (as for sqrt(-1)) or infinity (as for e^1000)? You could just ignore the possibility, or you could consider it an error, but if it's not an error, how do you print out the value in a way that the user will understand? The comment on your program should make your decisions in theses matters clear, so that the user knows what to expect from the program.