|CIT 594 Assignment 1: Expression Evaluation
CIT 594, Spring 2007
Write a program to evaluate arithmetic expressions. All numbers will be
You will need two
Stacks, one to hold operators and another
to hold operands (values). An operand can be either a literal number (which
we will treat as a
double), or the name of a variable that can
double. (I recommend creating an "Operand" class.)
You will need a
HashMap to hold the values of your
"variables." These won't be Java variables, they will be names
Strings) that you will associate with values
doubles). In the algorithm, when you get a value from the
operand stack, it will be either a
double that you can use
directly, or a name that you will have to look up in the
to find the
double associated with it (or, if the operator is
=', put a new value into the
In addition to the five usual arithmetic operators (
you will use the following two "fake" operators:
$ To mark
the end of the arithmetic expression
_ To mark the
bottom of the operator stack
The purpose of these "operators" is to simplify the code by reducing the number of tests of the type "Is there another token?" and "Is there anything in the stack?"
Here's the basic algorithm:
add a '$' to the end of the expression (the program, not the user, does this) push a '_' onto the operator stack 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 number, push it onto the operand stack | | else if the token is a variable name, push it onto the operand stack | | else if the token is a '(', push it onto the operator stack | | else if the token is a ')' | | | while the top operator in the operator stack is not an '(' | | | | pop an operator from the operator stack | | | | pop two values from the operand stack | | | | apply the operator to the two values to compute a new value | | | |__ push the new value onto the operand stack | | | pop the '(' from the operator stack | | else if the token is an operator (+, -, *, /, =, $) | | | while the priority of the new token is less than or equal to | | | | that of the top operator in the operator stack, | | | | pop an operator from the operator stack, | | | | pop two values from the operand stack | | | | apply the operator to the two values to compute a new value | | | |__ put the new value onto the operand stack |__ |__ |__ push the new token onto the operator stack
Here is a precedence table you can use:
Note: We have discussed precedence,
but not associativity. The above algorithm will correctly parse
but it will incorrectly parse
). You don't need to
The above algorithm is incomplete in one important respect: It will not handle unary minus. Extend the algorithm (and your program) to do this. (Hint: First get the program working without the unary minus.)
+' or '
-' is unary
if and only if:
In all other cases,
the operator is binary. Hence,
an expression such as
A unary minus is a different operator from a binary minus (subtraction operator),
but we use the same symbol for both. In your code, you will find it convenient
to use a different symbol (I use a tilde,
'~'). However, it is
up to your program to recognize unary minus; do not force the user to
make this distinction.
Unary minus should have the highest precedence of any operator. When you find one, just push it onto the operator stack. Be sure to distinguish it from the subtraction operator.
Each time you go to push a value onto the operand stack, first check whether the top operator on the operator stack is a unary minus. If it is, pop it off, and push the negation of the value onto the operand stack instead of the original value.
To break the input line into "tokens" (numbers, variable names, special
java.io.StreamTokenizer. The default settings
StreamTokenizer are almost exactly what you need, but you
will need to change one setting in order to handle minus signs correctly.
Write the following classes:
public class ExpressionEvaluator
- This is a model class; it is I/O free.
- It has a default constructor.
- It has the method
public double evaluate(String expression)to evaluate expressions.
evaluatemethod should throw an
ArithmeticExceptionif an attempt is made to divide by zero or to use the value a variable that has not previously been assigned a value.
evaluatemethod should some kind of
RuntimeException(don't throw a checked exception!) for any syntax errors.
- It should not have any other public methods.
- Variable assigned values (with the '
=' operator) are available for subsequent calls to
evaluate(keep their names and values in a
public class ExpressionEvaluatorTest extends junit.framework.TestCase
- This is the usual JUnit test class.
evaluateis the only public method, that's all it needs to test; however, there are still a lot of things to test about that method, so having several test methods is a good idea.
- Be sure to test both with and without previous variable assignments.
- Be sure to test that exceptions are thrown as appropriate.
- See how many syntax errors you can catch!
public class Calculator extends JFrame
- This GUI acts as both controller and view.
- It should have:
- An About menu item to bring up a dialog giving you credit for writing the program
JTextFieldinto which the user can type expressions to be evaluated
JTextFieldfor displaying the result of the current calculation
- Other labels, etc., as needed to make the GUI self-explanatory and reasonably attractive.
- It should display an alert if the
evaluatemethod throws an exception.
Zip the complete Eclipse project and submit via Blackboard before midnight, Tuesday January 16.