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:

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

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.