There are two problems in this homework, and both are based on the concept
of expression trees. This concept is covered in example 7.9 and Section 7.3.6 of the textbook. We also talked about it in class on Wednesday, Nov 20. For
this homework, you will write two methods -- the first one is called
*evaluate* and it evaluates an expression tree; the second is called
*expression* and returns a string with the expression corresponding
to the expression tree. The stub for both methods is contained in a
file called *Homework8.java* from here. The
file *Homework8.java* is the only file you should edit, add your
code to, and submit. To be able to run the main method in this file, however,
you will need the other fifteen files. Please do not submit these fifteen files
as part of your submission.

It is going to be a bit of a pain for you to set up this project in
netBeans in the usual way. I am providing a zip file from which you can import the project into netBeans. Here is what you need to do:

- Save the zip file Homework8.zip on your
file system.
- In the netBeans menu, choose File --> Import Project --> From ZIP, and
then choose the saved file as your zip file.

This should open a project called Homework8 with all the 16 files in it.
Our expression trees are of type *BinaryTree*. The *BinaryTree* interface can be found in the file *BinaryTree.java*. (This and
other classes/interfaces used in this assignment are from the textbook.) Each
node of our expression tree thus stores a string. We can assume that each
internal node of our expression tree stores either the string "+" or the string
"*". (That is, we can assume that the other operands don't occur.) Each internal node has two children. Each external node stores a string representing an
integer. (For example the string "6" represents the integer "6".) You can
use the *Integer.parseInt(s)* to recover from a string *s* the
corresponding integer.

An example of an expression tree is the one returned by the method
*tree1()* in *Homework8.java*. It corresponds to the
expression (3+((4+6)*7)).

We now detail the two methods that need to be written. For writing these,
you should only need to know the methods of the *Tree* and *BinaryTree* interface.

## Problem A

Write the code for the method *int evaluate(BinaryTree T, Position v)*. Here, *T* is a non-empty expression tree as described above, and *v* is a position in this tree. The method should return the
integer that the subtree of *T* rooted at *v* evaluates to.
Pseudo-code for this method can be found in the *evaluateExpression* method of Section 7.3.6.

## Problem B

Write the code for the method *String expression(BinaryTree T, Position v)*. Here, *T* is a non-empty expression tree as described above, and *v* is a position in this tree. The method should return a
String representing the expression corresponding to the subtree of *T* rooted at *v*. Pseudo-code for a similar method can be found in the
*printExpression* method of Section 7.3.6. (You can concatenate two
strings *s1* and *s2* via *s1 + s2*.)

Incidentally, code for a different type of solution to both problems is in Section 7.3.7, but here you should follow the pseudo-codes in *evaluateExpression* and *printExpression* in Section 7.3.6.
Submit the source file into a dropbox in ICON called Homework8. This
assignment is due by 11:59 pm on Wednesday, December 4.