Lab 5  An Infix Calculator

The purpose of this lab is to implement two well-known algorithms for manipulating arithmetic expressions, as well as gaining experience in the use of stacks and queues.  The application you will be working with is a simple integer calculator.  The calculator performs the arithmetic operations +, -, *, /, and ^ (exponentiation).  It also supports operator precedence and parenthesized expressions.  The calculator interface looks like this:

 


The user can click on the calculator buttons to create an arithmetic expression in infix form.  The infix expression is stored as a queue of tokens and displayed in the "entry" text field below the buttons.  (A "token" is either an operator or a number.  Numbers of more than one digit are entered by clicking a sequence of digit buttons.  As they are entered, the digits are combined in a string variable called ioString, and displayed in the I/O field at the top of the calculator.)  When the user clicks the "=" button, the infix token string is translated into an equivalent expression in postfix form.  The postfix expression is displayed in the postfix field at the bottom of the frame.

After the postfix expression is generated, the program needs to evaluate it.  As we saw in class, postfix notation is easier to evaluate than infix.  But a postfix string is still just a string of tokens.  It does not really capture the structure of the expression.  We can improve on the approach taken in class by defining an Expression object, which encapsulates the structure of an arithmetic expression.  Our program will convert the postfix token string into an Expression object, and then evaluate the Expression.  This will also make it possible to display the Expression in any of the notations we studied in class:  infix, postfix, or prefix.

I've written several classes for your use in completing the assignment, which you can find in lab5.jar .  (Note:  the code is in a package called "calculator".)

CalculatorFrame.  A subclass of JFrame which looks like the face of a calculator.

Calculator.  The main class of the application.  Calculator contains the following instance variables:

• calculatorFrame.  
  
• ioString.  The string of digits currently displayed in the calculator I/O field.
• infix.  A queue of tokens representing the current expression in infix form.  It is displayed in a text field in the calculator frame.
• postfix.  A queue of tokens representing the current expression in postfix form.  It is displayed in a text field in the calculator frame.
• expression.  An object representing the expression entered by the user.
  
• expressionManager.  An object responsible for implementing the infix-to-postfix and postfix-to-expression algorithms.
  

Calculator contains the action listeners for all the calculator buttons.  Their actions are:

• digit key.  Add the digit to the current digit string and display the string in the calculator I/O field.
• operator key.  If the calculator I/O field is not empty, create a number token from the digit string and enqueue it in the infix token queue.  In any case, create an operator token and enqueue it in the infix token queue.
• = key.  Call on the Expression Manager to convert the infix token queue to a postix token queue.  Then call on the Expression Manager to build an Expression object from the postfix token queue.  The Expression is then evaluated, with its result displayed in the calculator I/O field.  In addition, the infix, postfix, and prefix representations of the Expression are displayed.
• clear key.  Clears the ioString and the infix and postfix queues.

Token.  The input from the calculator keys is translated into a stream of tokens.  A token is either an operator ( +, -, *, /, ^, (, ), or = ) or a number.  So tokens are represented by the abstract class Token, which has two concrete subclasses, OperatorToken and NumberToken.  Token has abstract methods "isOperator" and "isNumber" which allow any object to find out whether a given Token is an operator or a number.  (This, of course, is an essential part of both the infix-to-postfix and evaluate-postfix algorithms.)

OperatorToken .  A subclass of Token.  An OperatorToken contains an integer code which is used to represent the operator it represents.   The statement

static final int LEFTP=1,RIGHTP=2,PLUS=3,MINUS=4,TIMES=5,DIVIDE=6,EXPON=7;

is used to define named constants representing each of the seven operator types.  OperatorToken has methods to

• get the in-stack precedence of the operator
• get the incoming precedence of the operator
• apply the operator to a pair of integer operands

Each of these methods uses a switch statement to give a different result for each operator.

NumberToken .  A subclass of Token.  A NumberToken has a single instance variable, the number it represents.

DigitButton .  A subclass of JButton, which is used to implement each of the 10 number keys on the calculator.  A DigitButton contains an integer variable which is equal to the value of the button.  

OperatorButton .  A subclass of JButton, which is used to implement each of the operator keys on the calculator, except for the "=" button, which is treated as a special case.  When each OperatorButton is created, it is given an instance of the corresponding OperatorToken class.  When the button is clicked, the OperatorToken is available to the Calculator class.

You have four responsibilities in completing the application:

1.    Write a Queue class.  The Queue class can be written as an adapter for your own LinkedList class from lab 3, or the LinkedList class in the java.util package.  Use either composition or inheritance, to support the standard Queue interface (i.e., the enqueue and dequeue methods).  Write a toString method for Queue which will allow a queue to be displayed.  (Display the contents of the queue from front to rear.)

2.    Write an ExpressionManager class.  The Expression Manager contains the algorithms for converting an infix expression to postfix notation and for evaluating a postifix expression.

3.    Write an Expression class, and its two subclasses, ConstantExpression and BinaryExpression.

4.    Writing the code to handle errors in the application.  If an error in forming an infix expression is detected by the Expression Manager, it should throw an Exception, causing the Calculator class to display the word "ERROR" in the calculator window.


Part one.  The Queue class

The operations of adding at the rear and removing from the front are already implemented in the LinkedList class.  You must simply write enqueue and dequeue methods which use the existing LinkedList methods.  You should do so in such a way that both enqueue and dequeue are O(1) in the worst case.  You must also write a toString method which returns a String showing all the tokens in the Queue, so that it can be displayed in the calculator frame.  (This may require using some of the other List methods of the LinkedList.)

class Queue {
    void enqueue(Object obj);
    Object dequeue();
    String toString();
}

Note:  java.util contains a Stack class which you may use in writing the expression manager.  Its public methods include push, pop, and peek.

class Stack {
    void push(Object obj);  //  pushes obj onto the top of the stack
    Object peek();  //  returns the top element without removing it
    Object pop();  //  removes and returns the top element
}


Part two.  The Expression class.

An expression (since we are using only binary operators) can be either a constant integer value, or else it is a binary operator applied to two subexpressions.  This leads us to a definition of Expression as an abstract class with two concrete subclasses, ConstantExpression and BinaryExpression.  ConstantExpression will have an integer value as its only instance variable; BinaryExpression will have an operator and two Expressions as instance variables.

Write the Expression class as an abstract class.  It should have an abstract method "evaluate" which returns an integer (the value of the Expression), and abstract methods infix, prefix, and postfix, which return Strings.

Write the ConstantExpression class.  It has one instance variable, an integer.  Write a constructor with an integer value as a parameter.  Write definitions for the evaluate, infix, prefix, and postfix methods.  Evaluate just returns the integer value of the object.  Infix, prefix, and postfix return the String representation of the integer value.

Write the BinaryExpression class.  It has an OperatorToken and two Expressions (its left and right operands) as instance variables.  (Note that this is a recursive definition.)  Write a constructor with an operator and left and right operands as parameters.  Write definitions for the evaluate, infix, prefix, and postfix methods.  Evaluate should evaluate the two operands and apply the operator to the results.  The prefix string should consist of the operator followed by the prefix representations of the left and right operands.  The postfix string should consist of the postfix representations of the left and right operands followed by the operator.  Because of the inherent ambiguity of infix notation, the infix method should generate a fully parenthesized infix representation of the expression; for example, ((3+5)*(12+7)).  So the infix method should generate a string with the left operand, operator, and right operand enclosed by a pair of parentheses.  Note that all of these methods are defined recursively.

The result of these data definitions is that we are actually using a binary tree structure to represent an expression.  Each Expression object is a node in the tree. Each ConstantExpression is a leaf and each BinaryExpression is an internal node.  For example, the expression ((3+5)*(12+7)) corresponds to the following tree:


Each ConstantExpression is represented by a yellow square and each BinaryExpression is represented by a blue circle.  Note that each BinaryExpression has an operator and two subexpressions, which is exactly how it has been defined in your Java code.

examples

1.    The expression "100" can be constructed with the statement

Expression e1 = new ConstantExpression(100);

2.    The expression "3 + 5" can be constructed with the statement

Expression e2 = new BinaryExpression(new OperatorToken(OperatorToken.PLUS, new ConstantExpresson(3), new ConstantExpression(5));

3.    Write a statement (or series of statements) to construct the expression "((3+5)*(12+7))"

Test your Expression class by writing a main program which creates the three example expressions and prints (to System.out) their infix, postfix, and prefix representations, and their values.


Part three.  The Expression Manager class

The Expression Manager implements two methods:  infixToPostfix and buildExpression.

Queue infixToPostfix(Queue infix);
Expression buildExpression(Queue postfix);

Use the stack-based algorithms presented in class to write these methods.

The infixToPostfix method uses the concept of operator precedence described in class.  I've included two methods in OperatorToken to compute the incoming priority (ICP) and the in-stack priority (ISP) for plus, minus, times, and divide.  You'll have to add code to set the priorities of the exponentiation operator and the left parenthesis.

When you've completed this part of the expression manager, you can test it by adding code to the ActionListener for the "=" button, to do the following:

• call on the expression manager to convert the infix token queue to a postix token queue.
• display the contents of the postfix queue in the postfix output field.  (Note:  Use the setPostfixField method in CalculatorFrame.)

The buildExpression method is based on the "evaluate postfix" algorithm presented in class.  However, instead of evaluating the postfix expression directly, it uses the postfix expression to construct an Expression object.

Make the following modifications to the algorithm from class:

• The stack is a stack of Expressions instead of a stack of operand values.
  
• When a NumberToken is obtained from the postfix Queue, create a ConstantExpression and push it onto the stack.
• When an OperatorToken is obtained from the postfix Queue, pop two operand Expressions from the stack, create a BinaryExpression from the operator and two operands, and push it onto the stack.
• When the algorithm is finished, there should be one Expression on the stack.  Use it as the the return value from the makeExpression method.

Once the expression object has been created, the application can evaluate it or display it in any of the three output notations.

You can test this part of the lab by adding code to the ActionListener for the "=" button, to do the following:

• call on the expression manager to build an Expression object from the postfix token queue.
• evaluate the Expression and display the result in the calculator I/O field.
• display the infix, postfix, and prefix representations of the Expression in the appropriate text fields.  (Note:  Use the setInfixField, etc. methods in CalculatorFrame.)

Part four.  Error handling

Modify the Expression Manager so that it throws an exception if it detects an error in the input.  Modify Calculator so that it calls the Expression Manager methods in a try-catch statement.  If an error occurs, display the word "ERROR" in the I/O field.  Continue to display ERROR (and don't respond to any keystrokes) until the user hits the "clear" button.

Some common errors in infix expressions are:

• mismatched parentheses
• missing operator symbol where one is expected
• missing number where one is expected

(It's not necessary for your program to identify the specific cause of each error.)

Try to handle as many errors as you can.