Java程序辅导

Lab 4 
The Expression Trees 
Due Date 
Monday July 26h, 2010 by 11:59 PM 
 
GETTING STARTED 
Download the starter code file from /afs/andrew/course/15/111M08/downloads or course 
web 
  
THE BACKGROUND 
In this assignment you will write code for implementing an expression tree. Expression 
trees have many applications in areas such as symbolic manipulators (eg: Mathematica) 
where a symbolic expression can be represented as a binary tree.  
An expression tree is a binary tree that models an expression. For example, the 
expression ((1+2)*(3-(4/5))) is modeled by a tree that looks like this: 
 
 
 
We can use expression trees to manipulate expressions. First we will understand some 
basic operations that we can perform on an expression tree. 
Commute Operation 
Consider commute operation for an operator. For example we know that a*b = b*a, 
where a and b are expressions. This can be shown by a tree as given below. If both trees 
evaluates to the same value, then the operator commutes (at least for that example)  
  
The commute operation swaps the left and right sub trees of an expression: (a*b) 
 
(b*a). For the addition and multiplication operators, the value of the expression remains 
the same after the commute. For the subtraction and division operators, the value of the 
expression may change.  
Mutating and Non-Mutating Transformations 
A non-mutating transformation is one that does not change the data structure. Instead, it 
creates new nodes to return (and leaves the old nodes as they are). For example, a non-
mutating commute operation looks like this:  
 
 
The old node (shown in gray) still exists, and anyone who had a pointer to it can still use 
it. The commute operation added a new node which represents the tree after the 
commute.  
This sort of operation is useful if you're dealing with "somebody else's data"---if 
somebody else created this tree, and might still be planning to use it after you're done 
with it. This is also useful for keeping track of the history of your data structure: you can 
save a pointer to your tree after each operation, and if later someone says, "Hey, what did 
that tree look like after you inserted ten keys?", you'll be able to tell them.  
Unless the compiler is really clever (wait until 15-212 for more about this), a strict 
regime of non-mutation can result in a lot of space being consumed, resulting in more 
frequent garbage collections and possibly in filling up the heap unnecessarily. But 
mutation can be risky if there is a possibility that other parts of your program also 
reference the mutated structures -- if they don't expect changes to be made, you can have 
some hard-to-debug errors! Every time you do a commute, you've created another 
treenode. Java's automatic garbage-collection will take care of the treenodes you didn't 
need, but there is a caveat. Garbage-collection affects performance, because it involves 
checking all allocated objects to see if they are still referenced and accessible. When the 
programmer is confident that it is safe to mutate objects, fewer new objects are made, 
which can reduce the amount of storage allocation and so reduce the frequency of 
garbage collection.  
For some applications you need mutating transformations. A mutating transform reaches 
into the tree and swaps around pointers until the tree looks like it should. For example, 
here's a mutating commute transform:  
 
 
Mutating transforms are nice because they don't waste space on unnecessary treenodes. In 
this assignment you'll implement both mutating and nonmutating commute methods. 
 
 The Assignment 
 
We strongly encourage you to open the starter code files and get yourself familiar with 
the assignment requirements. In the starter code you will find a bunch of java files, 
consisting of classes, abstract classes (will be discussed in class) and interfaces. An 
interface is a collection of standard methods that an implementing class will “implement” 
their own way. An abstract class is a collection of generic methods that have been 
implemented that another class can extend. Abstract classes cannot be instantiated to 
create objects. For example, we can have a “vehicle” class, but a specific vehicle such as 
a Toyota can be extended from a generic vehicle definition to add methods and states that 
are specific to “Toyotas”. Here are the given files. 
• Expression.java is an interface which our expression treenodes will implement. It 
supports three operations: toString(), height(), and compute(). Read the method 
descriptions, but do not modify this file. 
• FloatNode.java contains code for a node that just holds a float. 
• OperatorNode.java is an abstract class which the AddNode, SubNode, 
MultNode, and DivNode classes will inherit from. There are a number of methods 
which are not marked as abstract, and so are to be filled in here. For now, fill in 
the method body for toString() and height(). We'll come back to the rest later.  
• AddNode.java and SubNode.java contain code for the addition and subtraction 
nodes in the evaluation tree. We've filled in the constructor and createNew() 
methods for you; look at them to see how they work, but you only need to fill in 
the compute() method.  
Pay particular attention to the createNew() method, because it's kind of tricky. 
Calling createNew() on an OperatorNode returns a new OperatorNode with the 
same operator. For example, calling createNew() on an AddNode returns another 
AddNode. You can use this on an OperatorNode even if you don't know what 
type it is. This method will be useful for writing non-mutating transformations.  
• MultNode.java and DivNode.java should contain code for the multiplication and 
division nodes in the evaluation tree. Fill in the constructor, createNew(), and 
compute() methods. You can look at AddNode and SubNode for examples - the 
code will be quite similar. 
• You've now completed the basic structure of the expression tree. Use the file 
Driver.java to test your code. Feel free to add your own tests. This file will not be 
graded. Don't be alarmed when your commute method return null - you haven't 
implemented them yet. 
 
 
Implementing the Commute Method 
Now it's time to add commute method to the structure. We'll add mutating and 
nonmutating versions of each one, and track the space usage of the structure as a whole.  
• To begin, we need a way to track space usage. For this we'll use a method in 
OperatorNode called getNumCreated(). This method will track the total number 
of OperatorNodes created since the program began. Fill in the method body. To 
make this work, you'll need to add a static variable to the OperatorNode class, and 
increment the static variable every time the OperatorNode constructor is called. 
Making the variable static ensures that all OperatorNode objects share the same 
copy of the variable. You can initialize the variable to zero when you declare it. 
• Next, fill in the commute() and commuteMutating() methods. The commute() 
method should create one new node; the commuteMutating() method should not 
create any new nodes. The createNew() method, from before, will be useful here.  
You may find the keyword "this" useful. When you're inside an object, "this" is a 
pointer to the object you're inside. So, for example, you can go return this; 
to return a pointer to the current object.  
• Test your code using the file Driver.java. Add your own tests where you feel it's 
appropriate. Expressions are added manually in the driver program. Your program 
must pass all those tests to get the credit. Once you're sure everything works, 
create a zip file with at least the files you are to change:  
o SubNode.java 
o AddNode.java 
o MultNode.java 
o DivNode.java 
o OperatorNode.java 
Grading: 
100 points total, distributed as follows:  
o SubNode.java : 10 points 
o AddNode.java :  10 points 
o MultNode.java : 10 points 
o DivNode.java : 10 points 
o OperatorNode.java : 30 points 
o Passing our test cases : 20 points  
o Style: Commenting and indenting and others: 10  
Make sure that your program compiles and runs properly. As usual, take the 10 style 
points seriously; poorly commented spaghetti code is not acceptable.   
 
Where to Submit: 
Go to afs/andrew.cmu.edu/course/15/111M08/handin and submit zip file under Lab4