CSC 413 Expression Evaluator and Calculator GUI

You will be provided with a code skeleton for the Evaluator class (Evaluator.java). You should program the utility classes it uses - Operand and Operator - and then follow the algorithm described below to complete the implementation of the Evaluator class. The Evaluator implements a single public method, eval, that takes a single String parameter that represents an infix mathematical expression, parses and evaluates the expression, and returns the integer result. An example expression is 2 + 3 * 4, which would be evaluated to 14.

The expressions are composed of integer operands and operators drawn from the set +, -, *, /, ^, (, and ). These operators have the following precedence:

The algorithm that is partially implemented in eval processes the tokens in the expression string using two Stacks; one for operators and one for operands (algorithm reproduced here from http://csis.pace.edu/~murthy/ProgrammingProblems/ 16_Evaluation_of_infix_expressions):

• If an operand token is scanned, an Operand object is created from the token, and pushed to the operand Stack
• If an operator token is scanned, and the operator Stack is empty, then an Operator object is created from the token, and pushed to the operator Stack
• If an operator token is scanned, and the operator Stack is not empty, and the operator's precedence is greater than the precedence of the Operator at the top of the Stack, then an Operator object is created from the token, and pushed to the operator Stack
• If the token is (, an Operator object is created from the token, and pushed to the operator Stack
• If the token is ), then process Operators until the corresponding ( is encountered. Pop the ( Operator.
• If none of the above cases apply, process an Operator.

Processing an Operator means to:

• Pop the operand Stack twice (for each operand - note the order!!)
• Pop the operator Stack
• Execute the Operator with the two Operands
• Push the result onto the operand Stack

When all tokens are read, process Operators until the operator Stack is empty.

Requirement 1: Implement the above algorithm within the Evaluator class.

Requirement 2: Test this implementation with expressions that test all possible cases (you may use the included EvaluatorTest class to do this, or create JUnit tests).

Requirement 3: Implement the following class hierarchy

• Operator must be an abstract superclass.
  • boolean check( String token ) - returns true if the specified token is an operator
  • abstract int priority() - returns the precedence of the operator
  • abstract Operand execute( Operand operandOne, Operand operandTwo ) - performs a mathematical calculation dependent on its type
  • This class should contain a HashMap with all of the Operators stored as values, keyed by their token. An interface should be created in Operator to allow the Evaluator (or other software components in our system) to look up Operators by token.
• Individual Operator classes must be subclassed from Operator to implement each of the operations allowed in our expressions, and should be properly organized in your project.
• Operand
  • boolean check( String token ) - returns true if the specified token is an operand
  • Operand( String token ) - Constructor
  • Operand( int value ) - Constructor
  • int getValue() - returns the integer value of this operand

Requirement 4: Reuse your Evaluator implementation in the provided GUI Calculator (EvaluatorUI.java).