The expressions return!!!

In this project, you will be dealing with a tree data structure that can represent mathematical expressions. Don’t worry, there’s no parsing this time, and the evaluation is far easier!


Starting point

Download and extract these materials. Contained are:

To compile and run, do:

javac *.java
java Driver

You’ll see that it prints out a bunch of 0s and <not implemented>s. You need to fix that :)


Expression trees

Like I showed in class, trees come up a lot in representing languages, such as math and programming languages.

The Expression class represents a node in an expression tree. Each instance of Expression can be one of three things:

There are no “bracket” nodes; order of operations is entirely determined by the tree’s structure.

Here are some examples of mathematical expressions and the trees which represent them:

Tree 1: the expression "10" becomes a tree with a single node containing 10. Tree 2: the expression "2 + 2" becomes a tree whose root is a plus sign, and whose left and right children are nodes containing 2. Tree 3: the expression "4 * x + 5" becomes a tree whose root is a plus sign; whose left child is a multiplication (with 4 and x as children); and whose right child is 5. Tree 4: the expression "4 * (x + 5)" with parentheses around the addition becomes a tree whose root is a multiplication; whose left child is 4; and whose right child is a plus sign (with x and 5 as children).

Compare the last two trees. You can think of parentheses as saying, “force this part of the expression to be a sub-tree.”


Your task

Open Expression.java and look through it. There are already some methods written, but there are several stubbed-out ones with TODO inside them.

Each method gives you practice writing very common kinds of tree algorithms: visiting all the nodes in a tree; searching through a tree; creating a new tree which is a modification of an old one; and building a tree from scratch.

The next section documents some methods I wrote for you that will be helpful in writing these.

String toString()

String toPostfix()

double evaluate(Map<String, Double> variables)

Expression reciprocal()

Set<String> getVariables()

static Expression geometricMean(double[] numbers)

You may not use quickParse() to implement this method. Sorry ;)


The methods I wrote for you


Testing

Driver.java has a small amount of code in it to test your Expression methods. However it does pretty minimal testing. Like it tells you, TEST MORE THOROUGHLY!!! Use Expression.quickParse() to easily create test cases.

Here are the outputs I got from my implementation:

toString:        (((4.0 * x) + (y / 9.0)) + 12.0)
toPostfix:       4.0 x * y 9.0 / + 12.0 +
evaluate:        55.0
reciprocal:      (1.0 / (((4.0 * x) + (y / 9.0)) + 12.0))
reciprocal(num): 0.14285714285714285
reciprocal(div): (10.0 / x)
getVariables:    [x, y]
geometricMean:   (((((4.0 * 9.0) * 3.0) * 7.0) * 6.0) ^ 0.2)
it evalutes to:  5.3868466094227525

Extra Credit [+10]

String toNiceString()

Done correctly, if you just have toString() call this method, the relevant lines of the above output would now look like:

toString:        4.0 * x + y / 9.0 + 12.0
reciprocal:      1.0 / (4.0 * x + y / 9.0 + 12.0)
reciprocal(div): 10.0 / x
geometricMean:   (4.0 * 9.0 * 3.0 * 7.0 * 6.0) ^ 0.2

Grading Rubric


Submission

You will submit a ZIP file named username_proj5.zip where username is your Pitt username.

Do not put a folder in the zip file, just the following file(s):

Do not submit any IDE project files.

Submit to the Box folder at this link. Drag your zip file into your browser to upload. If you can see your file, you uploaded it correctly!

You can also re-upload if you made a mistake and need to fix it.