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
MitgliedExpNode
? Und tungetLeft
undgetRight
Gegenzug ein anderesExpNode
? Wenn ja, ist Ihr code sollte eher so Aussehenreturn 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 eineExpNode
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.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Den objektorientierten Ansatz, um Ihr problem zu definieren, eine dedizierte geben Sie für jede Art von Knoten. Um die Länge dieser Antwort angemessen und zu vermeiden, tun Sie Ihre Hausaufgaben, werde ich zeigen nur eine minimale Beispiel für integer-Ausdrücke, die nur mit addition und Multiplikation.
Ersten Schritt ist zu definieren, was ein Ausdruck Knoten bereitstellen muss. Für diese definieren wir die Schnittstelle
ExprNode
. Wenn Sie nicht lernen, über Polymorphismus in Ihrer Klasse noch (sollte mich Wundern), werden Sie wahrscheinlich wollen, um aufhören zu Lesen und kommen zurück, nachdem Sie gelernt haben, über Sie.Wollen wir auswerten Knoten so fügen wir eine
evaluate
Methode sollte den Wert der sub-Ausdruck wurzelt in diesem Knoten. Wir verschieben seine Implementierung der node-Klassen, da diese am besten wissen, wie bewerten Sie sich selbst.Wollen wir auch format Ausdrücken, so werden wir hinzufügen, eine andere Methode zum formatieren der sub-Ausdruck in infix-notation.
Nun, mal sehen, was die Knoten, die wir brauchen. Sicherlich, jeder Ausdruck enthält zahlen zu den blš Attern, also werden wir besser starten, definieren Sie eine Klasse für Sie. Die Umsetzung der
ValueNode
ist wirklich einfach, um nicht zu sagen trivial.Weiter, wir haben unsere zwei binären Operationen
+
und*
. Die Implementierung der jeweiligen Klassen ist wieder sehr einfach.Ausgestattet mit, dass, können wir aus bauen Ausdruck Bäume, drucken und auswerten. Hier ist ein Beispiel für den Ausdruck
2 * (3 + 4)
.Gibt es
(2) * ((3) + (4)) = 14
.So, für Ihren
ExprTree
, Sie würde einfach prüfen, ob dieroot != null
und wenn ja,return root.evaluate()
.Was ist, wenn wir wollen, dass mehr Ausdrücken?
Klar, definieren wir eine weitere sub-Art von
ExprNode
. So können wir zum Beispiel definieren, mehr binären Operatoren zu behandeln, die Subtraktion und die division, eine weitere unäre Knoten für unäre minus und so weiter. Jede dieser Klassen müssen das interface implementieren, diktiert durchExprNode
so dass jede sub-Klasse kann verwendet werden, die gleiche Weise, er kapselt die Logik, wie es selbst auswertet.Was ist, wenn wir wollen, dass mehr Operationen?
Zum Beispiel, vielleicht wollen wir formatieren von Ausdrücken in postfix-notation. Um dies tun zu können, könnten wir hinzufügen, eine andere Methode
asPostfixString
zuExprNode
. Dies ist jedoch etwas umständlich, da es bedeutet, dass wir gehen müssen, und Bearbeiten Sie alle sub-Klassen, die wir umgesetzt haben, so weit, hinzufügen der neuen operation.Dies ist ein eher grundlegendes problem. Wenn Sie das Layout einer composite-Struktur zur Kapselung von Operationen in den Knoten, dann es ist elegant zu bedienen und einfach neue node-Typen, aber schwierig zu add-Modus-Operationen. Wenn Sie eine Auswahl in jedem Betrieb (etwas so wie in deinem code), dann ist es einfacher zum hinzufügen neuer Operationen, aber der code für die Operationen bekommt verworren und es ist schwierig, fügen Sie weitere Knoten-Typen (der code für alle Operationen, die geändert werden muss). Dieses dilemma ist bekannt als die Tyrannei der dominanten Modell Zersetzung. Die visitor pattern ist ein Versuch, brechen aus ihm heraus.
Sowieso, wenn Sie die Einnahme einer grundlegenden Java-Klasse, ich finde das, was Sie erwartet, zu lernen, ist die Umsetzung eine polymorphe Struktur mit definierten Operationen in den Knoten, wie oben gezeigt.