Algorithmus zum auswerten eines binären Ausdrucks-Baum?

Ich hasse Rekursion, kann ich nicht nachvollziehen, durch den code leicht, aber mit Bäumen, die ich nicht haben eine Wahl.

Dies ist, was ich bisher ausprobiert habe.

private int evaluate(Node n)
{
    if (n != null)
    {
        if (n.isLeaf())  //n is a node with a number
            return Integer.parseInt(n.element);
        else
        {
            int left = evaluate(n.left);
            int right = evaluate(n.right);
            return calculate(left, n.element, right);
        } //end else
    } //end if
} //end evaluate
  • Hast du gut gemacht, alles, was Sie brauchen, ist eine triviale, nicht-rekursive calcilate zum Abschluss Ihrer übung. ...Und nicht vergessen, die Rückkehr.
  • Was ist die Frage?
  • Es wäre viel geholfen, wenn Sie auch gepostet, das problem haben Sie mit Ihrem code. Es ist "- Methode muss einen Wert zurückgeben".
  • Die Methode gibt einen Wert zurück, in einigen Fällen aber der compiler nicht verstehen.
  • Ich war Herumspielen mit der berechnen-Funktion, kann es nicht zu funktionieren so wie ich will, aber ich habe die return-Anweisung in. Aber ist die Rekursion bin ich mit sound. Ich bin ziemlich neu und die Rekursion.
  • Sie müssen einen Wert zurückgeben, wenn n == null oder werfen einen NullPointerException.
  • Sie nicht brauchen, um überhaupt Rekursion verwenden, können Sie erreichen, was Sie wollen mithilfe von for-Schleifen. Sie brauchen nur zu verwenden einen stack, denken Sie an Ihre aktuellen und übergeordneten Staaten.

InformationsquelleAutor Pat Gallagher | 2012-11-04
  1. 0

    Meinst du:

    return calculate(left, n.element, right);

    Ich nehme an, Ihr Knoten ist eine operation, z.B. "+", "-" etc.

    Ihre "berechnen" muss, führen Sie die entsprechende operation auf der int "Links" und "rechts" und Sie sind fertig!

    • Ja, ich bin bis zur Festsetzung, die Methode zu berechnen. Ich weiß nichts über Rekursion, also werde ich sehen, ob das funktioniert.
    • Danke, ich habe meine Berechnung Methode zu arbeiten und die Rekursion arbeitet
    InformationsquelleAutor thedayofcondor
  2. 0

    Ist die Methode nicht geben Sie eine gültige Erklärung für jeden Pfad. So müssen Sie return ... am Ende der Methode. Ich nahm null wäre angebracht, da dieser Pfad sollte eigentlich nie besucht in Ihrem Rekursion.

    private int evaluate(Node n)
{
    if (n != null)
    {
        if (n.isLeaf())  //n is a node with a number
            return Integer.parseInt(n.element);
        else
        {
            int left = evaluate(n.left);
            int right = evaluate(n.right);
            return calculate(left, n.element, right);
        } //end else
    } //end if
    return 0;
} //end evaluate

    Abgesehen von diesem Ihrem Rekursion scheint in guter Form sein.

    • Ich Stelle nur verwendet 999999 anstelle von 0. Ich denke, ich werde immer 0 als eine legitime Antwort, während ich das Debuggen, also 999999 dient als eine bessere Anleitung für ein. Aber danke, ich weiß einfach nicht traue mich mit Rekursion, also ich bin froh, dass ich fange an, es richtig zu machen.
    • Wie bereits von anderen könnte man tatsächlich eine Ausnahme. Wie ich schon sagte, dieser Pfad sollte (was ich verstehe von deinem code) eigentlich nie besucht werden, die von Ihrem Programm.
    • Für die Zeit wird, die calculate-Methode hat eine Menge von Komplexität, also für debugging-Zwecke die Nummer jetzt funktioniert
    InformationsquelleAutor Rouby
Schreibe einen Kommentar