Rekursives evaluate () in der Ausdrucksbaum-Klasse

evaluate expression-trees java methods recursion

Frage

Ich bin neu in Java und versuche, meine Klasse zu evaluieren. Die ExpTree-Klasse und ihr Testprogramm werden mir gegeben. Ich habe meinen Code geschrieben, wie ich in der Klasse gelernt habe, weiß aber nicht, warum das nicht funktioniert.

Eine evaluate () -Methode, die die arithmetische Auswertung von ExpTree zurückgibt. Dies sollte rekursiv durchgeführt werden, so dass Sie 2 Methoden dafür benötigen. In dem Fall, in dem es zu Division oder Mod durch 0 führen würde, sollte es eine neue ArithmeticException mit einem beschreibenden String werfen. Wenn der Baum leer ist, sollte evaluate () auch eine neue ArithmeticException mit einem beschreibenden String werfen.

Hier ist mein 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;
    }

}

Akzeptierte Antwort

Der objektorientierte Ansatz für Ihr Problem besteht darin, einen dedizierten Typ für jede Art von Knoten zu definieren. Um die Länge dieser Antwort vernünftig zu halten und um Ihre Hausaufgaben zu vermeiden, werde ich nur ein minimales Beispiel für Integer-Ausdrücke zeigen, die nur Addition und Multiplikation beinhalten.

Der erste Schritt besteht darin, festzulegen, was ein Expression-Knoten bereitstellen muss. Dazu definieren wir die Schnittstelle ExprNode . Wenn Sie in Ihrer Klasse noch nichts über Polymorphismus gelernt haben (was mich überraschen sollte), werden Sie wahrscheinlich jetzt aufhören wollen, zu lesen und zurückkommen, nachdem Sie davon erfahren haben.

Wir wollen Knoten auswerten, also fügen wir eine evaluate Methode hinzu, die den Wert des Unterausdrucks zurückgeben soll, der auf diesem Knoten verwurzelt ist. Wir werden die Implementierung auf die spezifischen Knotenklassen verschieben, da diese am besten wissen, wie sie sich selbst bewerten.

Wir möchten auch Ausdrücke formatieren, so dass wir eine weitere Methode hinzufügen, um den Unterausdruck in der Infix-Notation zu formatieren.

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

Jetzt wollen wir sehen, welche Knoten wir brauchen. Gewiss, jeder Ausdruck enthält Zahlen an den Blättern, also fangen wir besser an, eine Klasse für sie zu definieren. Die Implementierung von ValueNode ist wirklich einfach, um nicht zu sagen 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);
    }
}

Als nächstes haben wir unsere zwei binären Operationen + und * . Die Implementierung der jeweiligen Klassen ist wiederum sehr einfach.

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

Ausgerüstet damit können wir Ausdrucksbäume elegant bauen, drucken und auswerten. Hier ist ein Beispiel für den Ausdruck 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());

Es wird gedruckt (2) * ((3) + (4)) = 14 .

Also würden Sie für Ihren ExprTree einfach prüfen, ob die root != null und wenn ja, return root.evaluate() .

Was, wenn wir mehr Ausdrücke wollen?

Natürlich werden wir einen anderen ExprNode von ExprNode . Zum Beispiel können wir mehr binäre Operatoren definieren, um Subtraktion und Division zu handhaben, einen weiteren unären Knoten für das unäre Minus und so weiter. Jede dieser Klassen muss die Schnittstelle implementieren, die von ExprNode diktiert wird, sodass jede Unterklasse auf die gleiche Weise verwendet werden kann, wobei die Logik so eingekapselt wird, wie sie sich selbst auswertet.

Was, wenn wir mehr Operationen wollen?

Zum Beispiel könnten wir Ausdrücke in Postfix-Notation formatieren. Um dies tun zu können, könnten wir asPostfixString eine weitere Methode als asPostfixString ExprNode . Dies ist jedoch ein wenig peinlich, da es bedeutet, dass wir alle bisher implementierten Unterklassen bearbeiten und die neue Operation hinzufügen müssen.

Dies ist ein ziemlich grundlegendes Problem. Wenn Sie eine zusammengesetzte Struktur zum Verkapseln von Operationen in den Knoten erstellen, ist es elegant, neue Knotentypen zu verwenden und einfach hinzuzufügen, es ist jedoch schwierig, Modusoperationen hinzuzufügen. Wenn Sie in jeder Operation eine Fallauswahl verwenden (ähnlich wie in Ihrem Code), ist es einfacher, neue Operationen hinzuzufügen, aber der Code für die Operationen wird verschachtelt und es ist schwierig, weitere Knotentypen hinzuzufügen (der Code für alle Operationen muss) Verändert werden). Dieses Dilemma ist als Tyrannei der dominanten Modellzerlegung bekannt . Das Besuchermuster ist ein Versuch, daraus auszubrechen.

Wie auch immer, wenn Sie eine grundlegende Java-Klasse verwenden, denke ich, was Sie lernen sollten, ist die Implementierung eines polymorphen Baumes mit Operationen, die in den Knoten definiert sind, wie oben gezeigt.



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum