Recursive evaluate() in expression tree class

evaluate expression-trees java methods recursion

Question

I'm attempting to add an evaluate function to my class, but I'm new to Java. I get the ExpTree class and its testing software. I followed the instructions in the class when I developed my code, but I'm not sure why it didn't 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.

This 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;
    }

}
1
0
12/4/2014 8:23:27 PM

Accepted Answer

The object-oriented solution to your issue is to create a specific type for each kind of node. I'll simply provide a brief example for integer expressions that only include addition and multiplication in order to keep this answer's length manageable and save you from completing your homework.

Specifying what an expression node must provide is the initial step. We specify the interface for this.ExprNode . I shouldn't be surprised if you haven't learnt about polymorphism in class yet, so you may want to quit reading now and come back once you have.

Since we wish to assess nodes, we'll add anevaluate procedure that ought to provide the result of the value of the subexpression rooted at that node. We'll leave it up to the individual node classes to implement it because they'll be able to assess themselves most effectively.

We shall add another technique to format the sub-expression in infix notation as we also want to format expressions.

public interface ExprNode {
    int evaluate();
    String asInfixString();
}

Let's check the necessary nodes now. Any expression will undoubtedly include numbers at the leafs, therefore we should start designing a class for them now. The execution ofValueNode Its quite trivial yet straightforward.

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);
    }
}

Our two binary operations are next.+ and * The implementation of the corresponding classes is once again fairly straightforward.

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());
    }
}

With it, we can create expression trees with grace and then print and assess them. Here is an example of the phrase2 * (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'll print.(2) * ((3) + (4)) = 14 .

then, for yourExprTree simply determine if theroot != null whether so,return root.evaluate() .

What if additional expressions are desired?

Obviously, we'll outline a different sub-type ofExprNode . To handle subtraction and division, for instance, we may construct additional binary operators. Similarly, we can build an additional unary node for the unary minus. Each of these classes must follow the interface requirements specified byExprNode As a result, any subclass may be used in the same manner, encasing the reasoning behind how it assesses itself.

What if we need further surgeries?

For instance, postfix notation might be used to format expressions. We could implement another technique to be able to do this.asPostfixString to ExprNode . This is hard since it requires us to go back and add the new operation to every sub-class we have so far created.

This issue is rather essential. It is beautiful to use and easy to add additional node types provided you set up a composite structure to encapsulate actions in the nodes, but challenging to add mode operations. It is easier to add additional operations if you use case selection in every operation (kind of like in your code), but the code for the operations becomes complicated, making it difficult to add more node types (the code for all operations needs to be altered). This conundrum is referred to as the dominance of the dominant model breakdown. A breach of it is attempted using the visitor behavior.

Nevertheless, if you enroll in a basic Java course, I believe the main thing you will learn is how to create a polymorphic tree with operations specified in the nodes, as shown above.

1
12/4/2014 9:50:01 PM


Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow