Any arithmetic expression can be represented as a tree structure where the internal nodes are operators and the leaf nodes are numbers. For example, the expression \(((7.0 \times 2.0) - (8.0 \div 2.0))\) can be represented with the following tree:

In this lab you will complete the implementation of a binary tree that represents mathematical expressions in this way. This implementation will provide functionality for evaluating expressions and formatting them in prefix, postfix or infix notation.

Before you start coding, carefully read each of the following files to make sure you understand their roles.

- Operator.java - Enumerated type representing the set of operators.
- ExpressionNode.java - Abstract superclass for expression nodes.
- OperandNode.java - Class representing operands (leaves) in an expression tree.
- OperatorNode.java - Class representing operators (internal nodes) in an expression tree. UNFINISHED!
- ExpressionDriver.java - Simple test driver for executing expression tree methods.
- PrefixParser.java - Class for converting postfix expressions into expression trees. UNFINISHED!

Our textbook provides the following sample implementation of a pre-order traversal:

```
static <E> void preorder(BinNode<E> rt) {
if (rt == null) return; // Empty subtree - do nothing
visit(rt); // Process root node
preorder(rt.left()); // Process all nodes in left
preorder(rt.right()); // Process all nodes in right
}
```

In this code, the traversal has been implemented as a static method in
some separate class that is passed a reference to a root node. As an
alternative, it is possible to implement a tree as a recursive data
structure without a separate class to handle the traversals. In this
approach the node *is* the tree, and all of the functionality is
implemented through methods of the node class. Our `ExpressionNode`

class will be organized in this way. Under this approach, a preorder
traversal might look like the following:

```
private void preorder() {
visit(); // Process root node
if (!isLeaf()) {
left().preorder(); // Process all nodes in left
right().preorder(); // Process all nodes in right
}
}
```

It may seem odd to see a recursive method with no (apparent)
arguments. In this case the argument is implicit. Since the recursive
calls are executed on different `BinNode`

objects, it is the object
`this`

that changes from one call to the next.

Note that the method above will only work for full binary trees: it
assumes that every node is either a leaf, or contains two valid
children. Our expression trees will necessarily be full because every
operation must have exactly two operands. The methods for our
`ExpressionNode`

classes will be even simpler than the traversal
above. Since leaves are stored in a a different node type, there is
no need for an explicit `isLeaf`

check .

Submit `OperatorNode.java`

through Autolab . You are not required to
compete `PrefixParser`

, but you should do so if you have time.