Rekursive auswerten() im expression tree-Klasse

Ich bin neu in Java und versuche zu hinzufügen evaluate-Methode in meine Klasse. Die ExpTree Klasse und das Programm testen ist mir gegeben. Ich schrieb mein code, wie ich gelernt, in der Klasse, aber nicht wissen, warum es nicht funktioniert.

Einer evaluate () - Methode, liefert die arithmetische Auswertung des ExpTree. Dies sollte getan werden, rekursiv, so müssen Sie 2 Methoden, um es zu tun. In dem Fall, wo es führen würde, division oder mod von 0, es sollte werfen ein neues ArithmeticException mit einem beschreibenden String. Wenn der Baum leer ist, bewerten sollten() werfen auch ein neues ArithmeticException mit einem beschreibenden String.

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

}
  • Was ist der Baum tatsächlich zu speichern, und was bedeutet es auszuwerten?
  • Es ist nur zahlen, int und double. Es bedeutet, dass, wenn es irgendwelche mathematischen Operationen in der Struktur, hat diese Methode um Sie zu bewerten! Zum Beispiel, dass es passieren wir 3 + 5, dann sollten wir 8 als Ausgang!
  • Es wäre einfacher zu helfen, wenn man zeigen könnte, eine komplette Klasse. Ist recursiveEvaluate Mitglied ExpNode? Und tun getLeft und getRight Gegenzug ein anderes ExpNode? Wenn ja, ist Ihr code sollte eher so Aussehen return this.getLeft().evaluate() + this.getRight().evaluete(). Sie würden nicht brauchen Sie zwei Funktionen in diesem Fall. Oder sind Sie vermutlich soll zur Umsetzung des Visitor-Pattern?
  • So ist es zahlen UND Operatoren? Und die zahlen haben unterschiedliche Datentypen? Es scheint, wie du geschrieben hast einige nette code für das ZÄHLEN der Anzahl der Knoten im Baum, aber Sie müssen mit Blick auf die zahlen und Operatoren auch irgendwie.
  • Tatsächlich, die Art, wie Ava ist strukturiert, es ist äquivalent zu dem, was Sie vorgeschlagen sind. Das problem ist, es gibt eine ganze Menge Sachen, die fehlen - nicht, ob recursiveEvaluate sollte eine ExpNode als argument.
  • setLeft und setRight return new node getLeft und getRight Rückkehr rechten und linken Teilbaum.
  • Zusätzlich zu den Anmerkungen von anderen Benutzern, benötigen Sie wahrscheinlich etwas in Ihrem Baum, die besagt, was die operation durchgeführt wird, es sei denn, dies ist ausschließlich eine addition. Wenn der Ausdruck, der Baum soll in der Lage sein zu handhaben, Multiplikation, Subtraktion usw., Sie brauchen eine Art von Attribut, das Ihnen sagt, was (wahrscheinlich ein enum-Wert). Das Attribut gehört auf die ExpNode.
  • Ehrlich, Ava, ich glaube, du wirst bessere Hilfe zu bekommen, wenn Sie zeigen mehr von dem Programm. Zumindest zeigen die ExpNode Klasse. Nicht jeder erraten, was in Ihr steckt.
  • In einer Objekt-orientierten design, dass wäre in der Klasse geben. Aber wie ich schon früher sagte, es dauern würde, viel weniger zu raten, über diese Dinge, wenn wir sehen könnten-code für eine komplette Klasse.
  • es nicht lassen mich nach meinen ganzen code. aber ich benutzte diese Methode und es funktionierte: else if(Teilbaum.getData().equals("+")) return recursiveEvaluate(Teilbaum.getLeft()) + recursiveEvaluate(Teilbaum.getRight()) ;
  • Die, die ich gerade gepostet in den Kommentaren ist ein Teil der recursiveEvaluate Methode. Ich habe diesen code zu finden, welche der Betreiber ist, dann habe ich eine Ausnahme gemacht, dann konnte ich noch an der Auswertung.
  • Aus den Fragmenten des Codes, die ich bisher gesehen habe, das sieht nicht aus wie eine Objekt-orientierte Lösung im Geiste von Java. Aber es sei denn, Sie sind bereit zu zeigen, uns Ihren tatsächlichen code, es ist etwas mehr wir über es tun können. Wenn Ihre aktuelle Lösung funktioniert für Sie und Sie sind nicht daran interessiert, es zu verbessern, vielleicht wird diese Frage geschlossen werden sollten?
  • Was meinst du mit "es nicht lassen Sie mich nach meinen ganzen code"? Warum kann man nicht Bearbeiten es in der Frage?
  • Sorry Jungs für die Verspätung. Ich bemerkte, wo ich war falsch und wurde daran zu arbeiten. Ich bin immer noch daran interessiert zu wissen, ob es einen besseren und kürzeren code, den ich verwenden kann!!
  • Ich habe das ganze code!
  • So sind Sie glücklich für jetzt und brauchen keine Hilfe mehr?
  • David, Als ich sagte, ich würde gerne wissen, ob ich es tun kann, in einem kürzeren Weg.

InformationsquelleAutor Hr0419 | 2014-12-04
Schreibe einen Kommentar