The ExpressionTree class is to represent algebraic expressions as binary trees. The data fields in tree nodes are to be instances of the Token class described below. The ExpressionTree class is to have a constructor that takes a string representing an infix expression, and creates the binary tree representation of the expression. For this assignment, you may assume that the expression has no parentheses, that the only operators are the binary "+", "-", "*", and "/" operators, and that all other tokens are operands. However it should be easy to add new operator tokens. As in Assignment 5, you should assume that tokens are delimited by spaces and that the string has no white-space characters other than spaces. Your constructor may use a variant of the algorithm on p. 335 of Main, if you give him appropriate credit. You needn't use a queue in this assignment.

The constructor should throw an exception in the case of ill-formed input. Make sure that you can recognize the ill-formedness of an input string like "2 + 3 x" that has too many operands. In this case, the exception(s) that you throw may be of any type. If you can't handle illegal input, you may delete the corresponding test cases of A6.main(), although you can expect a deduction for this.

The Expression class is also to have methods prefix(), postfix() and evaluate(Map). The prefix and postfix() methods are simply to construct and return a String representing the prefix and postfix versions, respectively, of the expression.

The evaluate(Map) method is to return an integer representing the value of the expression. Operands are to be evaluated as follows: if the operand is an integer (i.e., if its string representation is identical to that of an integer), then it should evaluate to that integer. If it a token, then its value is to be looked up in the given Map. If the Map has no value for the token, then the value 0 should be used. In particular, the keys in the Map should be Tokens, and the values should be Integers. For this assignment, you needn't check for division by 0.

It is recommended that you use a separate ExpressionTreeNode class analogous to the BTNode class of the text. However if you do this your class should be a private (inner) class of the ExpressionTree class, which has a private instance variable root of the ExpressionTreeNode class. Messages sent to the tree may then be forwarded to the root.

Tokens in algebraic expressions are to be represented by instances of a Token class. There is no minimum set of public methods that this class needs to have, except that it will need a Token(String) constructor, an equals(Object) method and either a compareTo(Object) or hashCode() method for proper implementation of the Map used during evaluation (as described above). You will probably want to have methods such as toString(), and apply, isOperator(), etc., in order to facilitate the work of the ExpressionTree class.

As always, you may define any additional classes or methods that you find useful. You may use the solutions provided for Assignment 5, if you give appropriate credit.

Test your classes with the class A6, which is available given on the class web site, and don't forget to turn in a hard copy of the results of your testing.