You are given a class called ExpTree, which implements an “expression tree.” ExpTree already works and has the following:
- A constructor which accepts a String that holds a fully parenthesized arithmetic expression. It parses the String and uses 2 Stacks to build up the expression tree. It is commented enough that it should be understandable, although you won’t need to understand it for this Minilab.
- A printTree() that “prints” the tree in such a way that it looks like it is on its side. If you “capture output” (in Textpad) and then print (on paper) what is outputted, then you can draw in the links to see what the tree looks like.
- An inOrder() method, which will traverse the tree in LNR order. It also inserts parentheses so that the String that it returns looks like the original parenthesized expression.
The printTree() and inOrder() methods are implemented recursively, so that there are actually 2 methods for each public method.
You can use the recursive methods that are already implemented as guides. You are to write the following (sets of) methods:
- An evaluate() method, which returns the arithmetic evaluation of the ExpTree (as a double). This should be done recursively, so you will need 2 methods to do it. In the case where it would result in division or mod by 0, it should throw a new ArithmeticException with a descriptive String. If the tree is empty, evaluate() should also throw a new ArithmeticException with a descriptive String.
- A numPlus method, which will traverse the tree and return how many plus signs (“+”) are contained (as an int). This should be done recursively, so you will need 2 methods to do it.
For example, in the ExpTree that is built using “(((3*4)+(2-(4+2)))+10)”
- evaluate() will return 18.0
- numPlus() will return 3
Testing: You are also provided with a testing program which will call your ExpTree with various test cases.
• if the expected result is 6.36 and your result is 6.359999999999…, that is OK (Java doing base10 arithmetic in a base2 number system).
• To convert a String to a double, use Double.parseDouble(). For example,
String numString = “3.14”;
Double.parseDouble(numString) would return an actual 3.14 as a double
Comments and formatting: Your program should have opening comments for the class and each method (and anywhere in the code that is “tricky.” It should also have correct indenting and meaningful variable names.
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
public class ExpTree
private ExpNode root;
root = null;
//constructor where a string is passed in. It is parsed and stored
public ExpTree(String expString)
//declare StringTokenizer, Stacks, and other variables used in parsing
StringTokenizer tokenizer = new StringTokenizer (expString, "()+-*/%", true);
ExpNode operator, leftOperand, rightOperand;
Stack<ExpNode> operators = new Stack<ExpNode>();
Stack<ExpNode> operands = new Stack<ExpNode>();...
This is only a preview of the solution. Please use the purchase button to see the entire solution