CS 201: Data Structures (Winter 2017)

Lab04: Construct expression trees

1. Goals

To practice creating and manipulating trees in Java.

2. Introduction

Today you'll be working with expression trees: trees for representing a mathematical expression. Here's an example:

This tree represents the expression (3*5)+2. We talked earlier in the term about using postfix notation so that you don't have to know about order of operations or parentheses to interpret mathematical expressions. In postfix notation, the operator (+, -, *, /) comes after the things it operates on (operands). In this case, the postfix notation would be 3 5 * 2 +. You'll implement an algorithm for transforming a postfix expression into an expression tree. To make sure you're prepared to code, draw a tree that represents the postfix expression 4 3 + 5 2 * -.

After you've drawn the tree on paper, click here to compare my response to yours:

3. Creating a tree from postfix notation

Download the file for this lab: ExpressionTree.java. It has quite a bit of code already there, and you only need to look at parts of it:

At the top, there's a BinaryTreeNode class. Read through this small nested class.
Following that, you see one instance variable root: the root of the tree. That's the only instance variable you'll need.
Next is a constructor that you'll be implementing; we'll get to that in a moment.
There's an isOperator method for convenience: it tells you if a String is a mathematical operator.
Then there are some helper methods that will display your tree: these are already called for you in main. printExpression() prints an infix notation representation of the tree (like regular math expressions that you use). printTree() displays an ASCII art sort of tree:
```
   +       
  / \   
 /   \  
 *   2   
/ \     
3 5
```
You don't need to understand the details of these methods, although tracing through how printExpression() works may be helpful for checking your understanding of recursive methods.
Finally, main has a couple of test cases for you: once you've implemented your constructor, running main will show you whether you've actually created the trees correctly.
There's a bunch of helper code below main for making the ASCII art: please ignore this code!

The bulk of this lab is implementing an algorithm for constructing an expression tree from postfix notation. The basic idea of this algorithm is that it first turns a space-separated String into a list, where each item in the list is either an operator or a number. It then processes the list from right to left (so the current thing it's processing is always the last thing in the list). If the last thing in the list is an operator, then it will have two children: the item to its immediate left is its right child. If the last thing in the list is a number, then it has no children. You're welcome to think for a few minutes and try to come up with the details of the algorithm. If you are stuck, see the link below for my algorithm.

Before implementing the algorithm (either the one I gave you below or the one you and your partner have come up with), trace through it on paper with the expression 3 5 * 2 + (this is the postfix notation represented by the tree above).

Once you understand the parsing algorithm and feel confident in its correctness, implement it in your expression tree class. Try running the class to see what main prints for your trees.

Click here to see my algorithm:

Parsing postfix notation

First, convert the space-separated string into a list postfixNotationList (this is already done for you).
If the list is empty, return. There's no expression tree to process.
Otherwise, initialize the root as a new node.
Remove the last item from the list and store this item at the root node.
If the item at the root is not an operator, then you're done (the expression is just a single number).
If the item at the root is an operator, call a helper method (which you should create) for parsing postfix notation: parseHelper. This method should take two arguments: a BinaryTreeNode and a list representing the terms (in postfix notation). For the first call, the BinaryTreeNode should be root and the list should be postfixNotationList.

That's all that needs to happen in your constructor. You also have to write the logic for

parseHelper(BinaryTreeNode node, List<String>
list)

, which will recursively add nodes to the tree:

If the list is not empty and node does not have two children (i.e., at least one child is null), parseHelper should remove the last item from the list and create a new BinaryTreeNode called newNode that stores that item.
If node does not have a right child, then newNode should be set as its right child. Otherwise, newNode should be set as its left child.
If newNode represents an operator, then it needs to have children added to it (only operators have children). In this case, call parseHelper with the arguments newNode and list.
If the list is still not empty and node still does not have two children, then repeat starting at (1) again.

4. Extension: Evaluating an expression tree

If you have extra time, you can try evaluating an expression tree. Evaluating the tree means calculating the value of the expression it represents. For example, for the tree at the top of the lab, the value is 17. Brainstorm with your partner how to evaluate an expression tree. You'll likely want to use recursion.

Once you have an idea for how to evaluate, test your idea on paper by walking through what it would do with a small expression tree. Once you're satisfied that it seems to work, try implementing it!

This lab modified from one designed by Anna Rafferty.