CIT 594 Assignment
4: Expression Parsing and Evaluation CIT 594, Spring 2005 |
Stack
sStringTokenizer
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.
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.
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.
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
HashMap
s, 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
method for putting a new value into the HashMap
.
Here is the behavior that you should expect (and test for):
IntegerVariable
will return the value most
recently Assigned to it.IntegerVariable
before you have Assigned
a value to it, you will get an ArithmeticException
.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
).
This class contains the method public ArithmeticExpression parse(String expression)
"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,
*
, /
, and %
all have precedence
4
.+
and -
have precedence 3
.=
has precedence 2
.(
has precedence 1
.$
has precedence 0
.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
as
, but it will
incorrectly parse
as
(it should be
). 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.
Implement a simple class ExpressionTester
that extends JFrame
.
ExpressionTester
will implement a GUI containing the following
elements:
JLabel
to tell who wrote the program,JTextField
into which the user can type an arithmetic expression,JButton
, labeled "Calculate
," andJTextField
which is set to the result of evaluating the arithmetic
expression whenever the Calculate
button is pressed.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.
Tuesday, February 15, before midnight.