Expression Trees and Tree Traversals

Introduction

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.

Starter Code

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 - (8pts) Class representing operators (internal nodes) in an expression tree. UNFINISHED!
• ExpressionDriver.java - Simple test driver for executing expression tree methods.
• PrefixParser.java - (2pts) Class for converting postfix expressions into expression trees. UNFINISHED!

Object Oriented Traversals

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 .

Submission

Submit OperatorNode.java and PrefixParser.java through Gradescope.