Purposes:

• To give you practice with Stacks
• To familiarize you with StreamTokenizer
• To teach you the algorithm for expression evaluation

General Idea:

Write a program to evaluate arithmetic expressions. All numbers will be treated as double.

Algorithm:

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 hold a 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 HashMap to find the double associated with it (or, if the operator is '=', put a new value into the HashMap).

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:

Operator	Precedence
* /	6
+ -	5
=	4
$	3
(	2
)	1
_	0

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 fix this.

Extending the algorithm:

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.)

Recognizing a unary minus:

A '+' or '-' is unary if and only if:

• It is the very first symbol of an expression, or
• It immediately follows an opening parenthesis ('('), or
• It immediately follows an assignment operator ('=').

In all other cases, the operator is binary. Hence, an expression such as 2 + -3 is illegal, but 2 + (-3) is legal.

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.

Handling a unary minus:

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.

Details:

To break the input line into "tokens" (numbers, variable names, special characters), use java.io.StreamTokenizer. The default settings for 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.
  • The evaluate method should throw an ArithmeticException if an attempt is made to divide by zero or to use the value a variable that has not previously been assigned a value.
  • The evaluate method 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 HashMap instance variable).


public class ExpressionEvaluatorTest extends junit.framework.TestCase

• This is the usual JUnit test class.
• Since evaluate is 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
  • A JTextField into which the user can type expressions to be evaluated
  • A JTextField for 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 evaluate method throws an exception.

Due date:

Zip the complete Eclipse project and submit via Blackboard before midnight, Tuesday January 16.