Ich habe einige Elemente in einer Warteschlange (zum Beispiel / - 4 2 + 4 5).Rekursive Berechnung einer Warteschlange
, die als (4-2)/(4+5) berechnet werden müssen. Kann mir jemand den rekursiven Algorithmus darüber erklären?
Sie versuchen, eine polish notation zu verstehen, die eine Form der Notation für Logik, Arithmetik und Algebra ist.
Der Ausdruck für das Hinzufügen der Zahlen 4 und 5 ist in der Präfix-/Poliernotation geschrieben + 4 5 anstatt 4 + 5.
Der Ausdruck zum Subtrahieren der Zahlen 4 und 2 ist in der Präfix-/Poliernotation - 4 2 statt 4 - 2.
Dann können Operationen zusammengestellt werden. op3 (op1 m1 n1) (op2 m2 n2), die als (m1 op1 n1) op3 (m2 op2 n2) interpretiert werden kann, wo op1, op2, op3 kann +, -, *, / sein.
Runde Klammern sind optional und die vorherige können polnische Notation geschrieben werden op3 op1 m1 n1 op2 m2 n2
Der einfachste Weg, um es zu verstehen, ist es, einen Baum zu verwenden. Ein Baum wird Ihnen auch helfen, den rekursiven Algorithmus, der zur Bewertung solcher Notationen verwendet wird, besser zu verstehen. Auf einem solchen Baum wird jede Operation als Knoten betrachtet, und Zahlen sind Blätter.
einen Ausdruck auszuwerten, benötigt man:
gut das ist hilfreich wirklich ... aber wie kann ich es implementieren in einer Funktion, die rekursive Methode verwenden, um das Ergebnis zurückgeben –
Denken Sie an den Ausdruck '(4-2)/(4 + 5)' als Baum. '/' ist die Wurzel des Baumes, '-' und' + 'sind die Scheitelpunkte, die mit'/'verbunden sind,' 4' und '2' sind die Scheitelpunkte, die mit' -' verbunden sind und '4' und' 5' sind die Scheitelpunkte sind mit '+' verbunden. Dann beachten Sie, dass die inneren Knoten des Baums Operatoren sind und die Blätter Zahlen sind. Sie können dann den Ausdruck berechnen, indem Sie den Baum in einer Tiefensuche mit einer Rekursionsfunktion auswerten. – Xaver
Vielleicht hilft das? http://stackoverflow.com/questions/2722889/understanding-reverse-polish-notation-for-homework-assignment – ZzetT