I am new in Java and trying to add evaluate method to my class. The ExpTree class and its testing program is given to me. I wrote my code as I learned in the class, but do not know why it does not work.
An evaluate() method, which returns the arithmetic evaluation of the ExpTree. 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.
Here is my code:
// This will implement an "Expression Tree" which stores an arithmetic expression
import java.util.*;
public class ExpTree
{
//-------data
private ExpNode root;
//-------constructor
public ExpTree()
{
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);
String token;
ExpNode operator, leftOperand, rightOperand;
Stack<ExpNode> operators = new Stack<ExpNode>();
Stack<ExpNode> operands = new Stack<ExpNode>();
//break up expString into tokens
while (tokenizer.hasMoreTokens())
{
token = tokenizer.nextToken();
// if the current token is a left paren, ignore it
if (token.equals ("("))
;
// if the current token is an operator, put it on the
// operator stack
else if ((token.equals ("+")) || (token.equals ("-")) ||
(token.equals ("*")) || (token.equals ("/")) || (token.equals ("%")))
operators.push (new ExpNode(token));
//if the current token is a right paren, pop the operators stack
//to get the operator, pop the operands stack twice to get the two
//operands (stored as expression trees). Then make the two operands
//children of the operator and push back on the operands tree.
else if (token.equals (")"))
{
operator = operators.pop();
rightOperand = operands.pop();
leftOperand = operands.pop();
operator.setLeft(leftOperand);
operator.setRight(rightOperand);
operands.push(operator);
}
//otherwise, the token should be a number - put it in the operands stack
else
operands.push (new ExpNode(token));
} // while (tokenizer.hasMoreTokens())
//when finished parsing, the operands stack should contain the fully-built
//expression tree.
if (!operands.isEmpty())
root = operands.pop();
}
//-------methods
//isEmpty()
public boolean isEmpty()
{
return (root == null);
}
//printTree methods - prints the tree in RNL order, with indents. Called from "outside"
public void printTree()
{
if (root == null)
System.out.println("The tree is empty");
else
printTree(root, 0); //start with the root with 0 indentations
}
//recursive, private version of printTree
private void printTree(ExpNode subTree, int indents)
{
//if there is a right side, handle it first (with 1 more indent)
if (subTree.getRight() != null)
printTree(subTree.getRight(), indents+1);
//then print the node itself (first move over the right amount of indents)
System.out.println("\n\n\n");
for (int i=0; i<indents; i++)
System.out.print("\t");
System.out.println(subTree);
//if there is a left side, handle it first (with 1 more indent)
if (subTree.getLeft() != null)
printTree(subTree.getLeft(), indents+1);
}
//inorder traversal - starts the recursive calls to print inorder
public String inOrder()
{
return inOrder(root);
}
//inorder traversal - recursive left side of tree, print node, right side of tree
private String inOrder(ExpNode theTreeToTraverse)
{
if (theTreeToTraverse == null)
return ""; //don't try to do anything if tree is null
//else build up a String to return. It will involve recursive calls
String returnString = "";
if (theTreeToTraverse.getLeft() != null)
{
returnString += "(" + inOrder(theTreeToTraverse.getLeft());
}
returnString += theTreeToTraverse;
if (theTreeToTraverse.getRight() != null)
{
returnString += inOrder(theTreeToTraverse.getRight()) + ")";
}
return returnString;
}
//public version of evaluate
public double evaluate(){
if (root == null) //Am I null?
throw new ArithmeticException("The tree is empty, nothing to be evaluated!");
else //You handle it!
return recursiveEvaluate(root);
}
//Recursive version of evaluate
private double recursiveEvaluate(ExpNode subTree){
//If subTree is empty
if (subTree == null)
return 0;
//What are you subTree? A number? An operator?
else if(subTree.getData().equals("+"))
return recursiveEvaluate(subTree.getLeft()) +
recursiveEvaluate(subTree.getRight()) ;
else if(subTree.getData().equals("-"))
return recursiveEvaluate(subTree.getLeft()) -
recursiveEvaluate(subTree.getRight()) ;
else if(subTree.getData().equals("*"))
return recursiveEvaluate(subTree.getLeft()) *
recursiveEvaluate(subTree.getRight()) ;
else if(subTree.getData().equals("/")){
double right = recursiveEvaluate(subTree.getRight());
if(right == 0.0)
throw new ArithmeticException("Divide by zero is undefined!");
return recursiveEvaluate(subTree.getLeft()) / right;
}
else if(subTree.getData().equals("%")){
double right = recursiveEvaluate(subTree.getRight());
if(right == 0.0)
throw new ArithmeticException("Mod by zero exception");
return recursiveEvaluate(subTree.getLeft()) % right;
}
//Converting String type to double
else
return Double.parseDouble(subTree.getData());
}
//Public version of numPlus
public int numPlus(){
return recursiveNumPlus(root);
}
//Recursive version of numPlus
private int recursiveNumPlus(ExpNode subTree){
if (subTree == null)
return 0;
//If you are a '+' sign
if(subTree.getData().equals("+"))
return recursiveNumPlus(subTree.getLeft()) +
recursiveNumPlus(subTree.getRight()) + 1;
else
return recursiveNumPlus(subTree.getLeft()) +
recursiveNumPlus(subTree.getRight());
}
}
//***************************************************************************
// ExpNode holds a "node" for an ExpTree.
class ExpNode
{
//data
private String data;
private ExpNode left;
private ExpNode right;
//constructor
public ExpNode(String el)
{
data = el;
left = right = null;
}
//methods
//toString() - this is how an ExpNode represents itself as a String
public String toString()
{
return data;
}
//getLeft - returns the reference to the left subTree
public ExpNode getLeft()
{
return left;
}
//getRight - returns the reference to the right subTree
public ExpNode getRight()
{
return right;
}
//getData - returns the data (could be an operator or a number, so returns as a String)
public String getData()
{
return data;
}
//setLeft - sets the left subTree to whatever is passed in
public void setLeft(ExpNode newNode)
{
left = newNode;
}
//setRight - sets the right subTree to whatever is passed in
public void setRight(ExpNode newNode)
{
right = newNode;
}
}
The object oriented approach to your problem is to define a dedicated type for each kind of node. In order to keep the length of this answer reasonable and to avoid doing your homework, I'll only show a minimal example for integer expressions only involving addition and multiplication.
The first step is to define what an expression node must provide. For this, we define the interface ExprNode. If you did not learn about polymorphism in your class yet (which should surprise me) you'll probably want to stop reading now and come back after you have learned about it.
We want to evaluate nodes so we'll add an evaluate method that should return the value of the sub-expression rooted at that node. We'll defer its implementation to the specific node classes as these will know best how to evaluate themselves.
We also want to format expressions so we will add another method to format the sub-expression in infix notation.
public interface ExprNode {
int evaluate();
String asInfixString();
}
Now, let's see what nodes we need. Certainly, any expression will contain numbers at the leafs so we'll better start defining a class for them. The implementation of ValueNode is really simple, not to say trivial.
public final class ValueNode implements ExprNode {
private final int value;
public ValueNode(final int value) {
this.value = value;
}
@Override
public int evaluate() {
return this.value;
}
@Override
public String asInfixString() {
return String.valueOf(this.value);
}
}
Next, we have our two binary operations + and *. The implementation of the respective classes is again very simple.
public final class PlusNode implements ExprNode {
private final ExprNode lhs;
private final ExprNode rhs;
public PlusNode(final ExprNode lhs, final ExprNode rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
@Override
public int evaluate() {
return this.lhs.evaluate() + this.rhs.evaluate();
}
@Override
public String asInfixString() {
return String.format("(%s) + (%s)",
this.lhs.asInfixString(),
this.rhs.asInfixString());
}
}
public final class TimesNode implements ExprNode {
private final ExprNode lhs;
private final ExprNode rhs;
public TimesNode(final ExprNode lhs, final ExprNode rhs) {
this.lhs = lhs;
this.rhs = rhs;
}
@Override
public int evaluate() {
return this.lhs.evaluate() * this.rhs.evaluate();
}
@Override
public String asInfixString() {
return String.format("(%s) * (%s)",
this.lhs.asInfixString(),
this.rhs.asInfixString());
}
}
Equipped with that, we can elegantly build expression trees, print and evaluate them. Here is an example for the expression 2 * (3 + 4).
ExprNode expr = new TimesNode(
new ValueNode(2),
new PlusNode(new ValueNode(3), new ValueNode(4)));
System.out.println(expr.asInfixString() + " = " + expr.evaluate());
It will print (2) * ((3) + (4)) = 14.
So, for your ExprTree, you would simply check if the root != null and if so, return root.evaluate().
What if we want more expressions?
Clearly, we will define another sub-type of ExprNode. For example, we can define more binary operators to handle subtraction and division, another unary node for the unary minus and so on. Each of these classes must implement the interface dictated by ExprNode so any sub-class can be used the same way, encapsulating the logic how it evaluates itself.
What if we want more operations?
For example, we might want to format expressions in postfix notation. To be able to do this, we could add another method asPostfixString to ExprNode. However, this is a little awkward since it means we'll have to go and edit all sub-classes we have implemented so far, adding the new operation.
This is a rather fundamental problem. If you lay out a composite structure to encapsulate operations in the nodes, then it is elegant to use and simple to add new node types but difficult to add mode operations. If you are using a case selection in every operation (somewhat like in your code) then it is simpler to add new operations but the code for the operations gets convoluted and it is difficult to add more node types (the code for all operations needs to be altered). This dilemma is known as the tyranny of the dominant model decomposition. The visitor pattern is an attempt to break out of it.
Anyway, if you are taking a basic Java class, I think what you are expected to learn is implementing a polymorphic tree with operations defined in the nodes as shown above.