For HW4 you have to choose a single program from the list below to write, or more than one for some extra credit. (But I suggest you do one program well rather than two poorly.)
There are only two choices, and I won't be adding any more. So get started!
These projects are not easy. Get started soon. First read the textbook. You'll get partial credit for partial solutions.
On pages 314 and 316 of the textbook you can find pseudo-code for converting infix arithmetic expressions (Strings) into postfix expressions. Write a program based on those algorithms that builds expression trees (see project 1 on page 479). That is, instead of printing out a postifix expression corresponding to the infix expression, build a binary tree corresponding to the infix expression. For example, for the infix expression
(((3 * X) + (Y - 12)) - Z)instead of printing out the postfix expression 3 X * Y 12 - + Z -, build a binary tree (in memory, using a Java class) that would look like this if you could print it in a tree-like form:
-
/ \
/ \
/ \
+ Z
/ \
/ \
/ \
* -
/\ /\
/ \ / \
/ \ / \
3 X Y 12
Write a class ExpressionTree for representing binary expression trees. Have a file ExpressionTree.java with a main method, as well as additional classes and files, as you see fit. Remember: an expression tree object is either a leaf (e.g., representing the number 3), or an internal node (e.g., +), with two subtrees for the arguments.
Include a static method stringToExpressionTree that takes a string as parameter and returns a newly constructed ExpressionTree corresponding to the string, if possible; if the string has invalid syntax, print an error message and abort.
public static ExpressionTree stringToExpressionTree(String inString)Your method may throw exceptions if you wish. (Writing this method is the hardest part of the project.)
Hint: think how to convert a postfix expression to a tree.
So, if the string is just "3", create an ExpressionTree representing the leaf node 3. If the string is "(3+5)", create an ExpressionTree internal node with operator + and subtrees for 3 and 5.
Also write a method toString() that converts an ExpressionTree to a string showing the prefix form of the tree. For example, the string corresponding to the tree above would look similar to -(+(*(3,X),-(Y,12)), Z). Writing toString should be easy: do a pre-order traversal of the expression tree to produce the string.
You may assume that valid input strings contain only numbers, operators, spaces, and parentheses (but no variables), so that all leaf nodes of the expression tree will be numbers. For extra credit, allow variables (e.g., X).
You may wish to use java.util.StringTokenizer. If so, read its documentation carefully.
The psuedo-code on page 314 assumes that the input expression is fully parenthesized. You may make the same assumption in your program. For extra credit, relax that assumption by using the pseudo-code of page 316.
You may want to require that the input string have spaces between all tokens, so that the string would have to be
( ( ( 3 * X ) + ( Y - 12 ) ) - Z )rather than
(((3 * X) + ( Y - 12 )) - Z)It's a bit more work to remove this requirement.
The main method of ExpressionTree.java should test your ExpressionTree class on several sample strings. For each string it should print both the string and the corresponding prefix representation returned by calling the toString method of the corresponding ExpressionTree object.
If the user enters a string on the command line (inside double quotes), try converting it to an ExpressionTree and print it out using toString. For example, with my program I can do the following.
% java ExpressionTree "(((3 * X) + ( Y - 12 )) - Z)" (((3 * X) + ( Y - 12 )) - Z) ---> -(+(*(3, X), -(Y, 12)), Z)
Write a class IntTreeArrayBag (similar to the textbook's IntTreeBag) that represents binary search trees using an array, with ints stored as data. You needn't implement remove or union. But do implement countOccurrences. (You should allow multiple occurrences of a given int to appear in the tree.) Also, implement a toString method that returns a String that represents the tree in prefix form (see question 1 above).
You may use an array of Objects or multiple arrays. Notice that in general, binary search trees are not complete.
Write a test program TestIntTreeArrayBag.java that inserts randomly generated sequences of ints into an empty IntTreeArrayBag and prints out the resulting trees (using toString). Include enough tests to convince your TA that your program is correct.
Finally, for full credit compare the performance of IntTreeBag and IntTreeArrayBag by inserting n random ints and then calling countOccurrences m times on randomly chosen search values. Which implementation is faster for large n? Theoretically, the array representation should be less efficient for sufficiently sparse trees. Investigate whether this is so. How can you generate sparse trees? Present benchmark data and analyze your results.
Specifically, call your program Compare.java. On the command line, let the user of your program optionially specify n (the number of random elements to insert), m (the number of calls to countOccurrences), and the range of int values to allow. Have reasonable default values. For example, n=1000000, m=1000000, and a range from 0 up to 10,000,000 for values. (If 1000000 takes too much time or memory, try a smaller number.)
Measure the time taken with an IntTreeBag to insert n random items and do m searches. Then measure the time taken for an IntTreeArrayBag to insert n random items and do m searches. Repeat these two steps several times and take the averages. (Is there much variation between runs?)
It's a good idea to try various values of n and create a graph (e.g., with gnuplot), as suggested for HW2. Also, do measurements with different degrees of sparseness in the trees to investigate whether arrays become less efficient for sparse trees. Clearly explain your methodology and clearly analyze your results.