CIT 594 Assignment 4: Expression Parsing and Evaluation
CIT 594, Spring 2005

Purposes:

General Idea:

Write a program to evaluate arithmetic expressions involving both integer constants and integer variables.

There are several parts to this assignment. I think that things will go most smoothly for you if you do the parts in the order described below. I recommend getting each part working and tested before moving on to the next part.

Details:

Use the classes (and interface) defined in the previous assignment. You will also define some new classes: Mod, IntegerVariable, Assign, ExpressionParser, and ExpressionTester, along with the appropriate JUnit tests.

1. Mod

Create JUnit tests for a new class, Mod, that implements the Operation interface. Mod will perform the Java % operation. Be sure that you write tests for Mod with both positive and negative numbers. Once you have the JUnit tests, write Mod.

This is very simple; you are just adding a new operator to the ones you wrote for the last assignment.

2. IntegerVariable and Assign

It's easy to write JUnits tests for these classes, and you should do that first. Implementing the classes is a little harder.

IntegerVariable, like IntegerConstant, is an Operation, hence it must implement evaluate. Also like IntegerConstant, the evaluate method of IntegerVariable ignores its arguments. But constants don't change, so IntegerConstant can just return the same value each time its evaluate method is called. Variables do change their values, so each time you evaluate an IntegerVariable you have to find its current value. Look up the value of the variable in a table (use a HashMap for the table).

Somewhere (we'll discuss where later), you create a HashMap to hold the values of your integer variables. (Eventually you will have several HashMaps, but for now we only need one.) Your HashMap can hold an arbitrary number of variables and their values. Use the name of the variable as the HashMap key, and the value of the variable as the HashMap value.

For the evaluate method of IntegerVariable to be able to look up the current value of this variable in the HashMap, it needs to know where the HashMap is. Your constructor for IntegerVariable will take two arguments, the String name and the HashMap context. (context is, of course, a reference to the actual HashMap, which is defined somewhere else). The constructor stores these in its own instance variables.

IntegerVariable will also have a public void setValue(int value) method for putting a new value into the HashMap.

Here is the behavior that you should expect (and test for):

Assign is another class that implements Operation. This means it must also implement the method

      int evaluate(ArithmeticExpression x, ArithmeticExpression y)

This method will evaluate the right-hand side (y) and assign the result to the left-hand side (x), which must be of type IntegerVariable. The assignment is done using x's setValue method. As in Java, the value of an assignment is the value assigned (that is, the value of y).

3. ExpressionParser

This class contains the method public ArithmeticExpression parse(String expression), and any additional methods and constructors you need. The parse method takes a String representing an arithmetic expression, such as "2+3*(a=5)", and produces the corresponding ArithmeticExpression binary tree. The algorithm for doing this is somewhat complicated, so I'll present it in some detail.

First, each operator has a precedence--for example, in 2+3*4, the multiplication is done before the addition, because multiplication has higher precedence. Specifically,

You may find it convenient to define new Operation types for '(' and '$', since we will be treating them as if they were operators. (The '(' indicates the start of a parenthesized group.) You may also find it convenient to define a method to return the precedence of an operator.

Define two stacks, one for operators (of type Operation) and one for expressions (of type ArithmeticExpression). If you are using Java 5.0, you can use generics to ensure that you are putting the right kind of thing on each stack. On the other hand, if you are not using generics, you probably don't have to create new Operation types for '(' and '$'.

Begin by pushing a '$' onto the operator stack. This isn't a "real" operator, but by treating it as if it were an operator, we can avoid dealing with a lot of special cases where the stack might be empty. It has the lowest precedence, so it will be "evaluated" last; "evaluating" it means we are done, and can return the final result.

Next, you need to tokenize the input String, processing one token (number, variable, or operator) at a time. Relax--the input is simple enough for Java's built-in StringTokenizer to do the job for us. Use the StringTokenizer constructor that takes three arguments, and use all the possible operators, plus space, as the delimiters.

Here's the algorithm:

add a '$' to the end of the expression
while there are tokens remaining in the input string {
|   get the next token
|   depending on the token, take one of the following actions:
|   |   if the token is a space, ignore it, 
|   |   if the token is a number, push it onto the expression stack,
|   |   if the token is a variable name, push it onto the expression stack,
|   |   if the token is a '(', push it onto the operator stack,
|   |   if the token is a ')',
|   |   |   as long as the top operator in the operator stack is not an '('
|   |   |   |   pop an operator from the operator stack,
|   |   |   |   pop two expressions from the expression stack,
|   |   |   |   create a new expression from the operator and two expressions
|   |   |   |   put the new expression onto the expression stack
|   |   |   and pop the '(' from the operator stack
|   |   if the token is an operator
|   |   |   compare its priority to the priority of the top operator in the operator stack
|   |   |   if the new token has higher priority
|   |   |   |    push it onto the operator stack
|   |   |   else
|   |   |   |   as long as the priority of the  token is less than or equal to that of the
|   |   |   |   |                  top operator in the operator stack,
|   |   |   |   |    if the top operator is '$',
|   |   |   |   |   |    return the top expression in the expression stack as the value
|   |   |   |   |   |              of this method
|   |   |   |   |    else
|   |   |   |   |   |    pop an operator from the operator stack,
|   |   |   |   |   |    pop two expressions from the expression stack,
|   |   |   |   |   |    create a new expression from the operator and two expressions
|   |   |   |   |   |    put the new expression onto the expression stack
|   |   |   |   push the new token onto the operator stack

This algorithm has been discussed in class, though in less detail. I've left out a few conversions (such as, you want to turn a number into an ArithmeticExpression before you push it onto the expression stack), but the algorithm itself is, I believe, complete.

Catch and report as many errors in the input expression as you can.

Note: We have discussed precedence, but not associativity. The above algorithm will correctly parse 1 + 2 + 3 as ((1 + 2) + 3), but it will incorrectly parse a = b = c as ((a = b) = c) (it should be (a = (b = c)). You don't need to worry about this.

Don't forget to write JUnit tests for the parser. In the JUnit test class, you will need at least one HashMap for use while testing. To keep each test method independent of all the others, though, you have to make sure that every method starts with a "clean" HashMap, not one containing junk left over from a previous test.

4. ExpressionTester

Implement a simple class ExpressionTester that extends JFrame. ExpressionTester will implement a GUI containing the following elements:

Your ExpressionTester class should create and use one HashMap, so that you can use values from previous assignment statements in each new expression--that is, your class remembers the values you have assigned to variables.

Due date

Tuesday, February 15, before midnight.