The Queue class is to have methods enqueue(Object), dequeue, and isEmpty(), in addition to a constructor that builds an empty queue. The enqueue(Object) and dequeue methods should obey the FIFO discipline of the Queue ADT.

The Expression class is to have a constructor that takes a String argument representing the expression in infix format. It needn't check for ill-formed input. You may assume that the string has no white-space characters other than spaces. The class is also to have methods convertToPostfix() and evaluate(). The convertToPostfix() method is to construct and return a String by first constructing a queue of all the tokens, and then using this queue as a source of tokens for the conversion to postfix form. For this assignment, a token is a substring delimited by one or more spaces. It's easy to find the tokens by using the StringTokenizer class in the java.util package. This class is described briefly below.

The evaluate() method is to return an integer representing the value of the expression. You may have this method invoke the convertToPostfix() method if you want.

An algorithm for converting from infix to postfix is given on p 335 of the text. Note that the algorithm used by your method will actually be simpler than this algorithm, since you don't need to worry about parentheses. An algorithm for evaluating postfix expressions is given on p 331 of the text.

You may assume that the only operators are the binary "+", "-", "*", and "/" operators, and that all other tokens are operands. However it should be easy to add new operators to your class. You may assume that operands that are not integers are variables that evaluate to 0. You may assume that there are no parentheses in the expression (or more precisely, that a parenthesis may appear as part of an operand token). You may not assume that the input is a well-formed sequence of operators and operands. The evaluate method should throw an IllegalArgumentException for ill-formed expressions like "3 + 4 5". If you can't handle illegal input, you may delete the corresponding test cases of A5.main(), although you can expect a deduction for this.

Operands are to be evaluated by a private evaluateOperand method that takes a token and returns an Integer object. This method can simply attempt to convert the token to an Integer by passing it to the Integer constructor, and returning 0 in case of failure (signaled by a NumberFormatException). The reason for this approach is that it is easy to generalize to more realistic data.

A StringTokenizer object works much like an Iterator. The basic pattern is

    StringTokenizer tokenizer =
      new StringTokenizer(myString);
    while (tokenizer.hasMoreTokens())
      process(tokenizer.nextToken());

You may define any additional classes or methods that you find useful.