CS 201: Data Structures (Spring 2017)
Lab3: 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:+ / \ / \ * 2 / \ 3 5
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:
- / \ / \ + * / \ / \ 4 3 5 2
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 aString
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 howprintExpression()
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, runningmain
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!
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.
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: aBinaryTreeNode
and a list representing the terms (in postfix notation). For the first call, theBinaryTreeNode
should beroot
and the list should bepostfixNotationList
.
parseHelper(BinaryTreeNode node, List<String>
list)
, which will recursively add nodes to the tree:
-
If the
list
is not empty andnode
does not have two children (i.e., at least one child isnull
),parseHelper
should remove the last item from the list and create a newBinaryTreeNode
callednewNode
that stores that item. -
If
node
does not have a right child, thennewNode
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, callparseHelper
with the argumentsnewNode
andlist
. -
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.