Wie man einen Ausdruck in der Präfixnotation auswertet

evaluation expression-trees s-expression

Frage

Ich versuche, eine Liste auszuwerten, die einen Ausdruck in der Präfixnotation darstellt. Hier ist ein Beispiel für eine solche Liste:

[+, [sin, 3], [- 10 5]]

Was ist der beste Weg, um den Wert der Liste zu bewerten?

Akzeptierte Antwort

Es wird einfacher, wenn Sie Postfix anstelle von Präfix verwenden. Siehe umgekehrte polnische Notation (RPN) . Wenn ein Ausdruck in RPN gegeben ist, ist es leicht, dies mit nur einem Stapel zu bewerten.

Aber da Sie nach einer Möglichkeit gefragt haben, Präfix- Ausdrücke ohne Rekursion auszuwerten und Stacks zu verwenden (für einen möglicherweise einfacheren Weg, siehe EDIT: unten), ist hier eine Möglichkeit:

Wir können dies mit zwei Stapeln machen.

Ein Stapel (nennen wir es Evaluation) enthält die Operatoren (wie +, sin usw.) und Operanden (wie 3,4 usw.) und der andere Stapel (nennen wir ihn Count) enthält ein Tupel der Anzahl der noch zu sehenden Operanden + die Nummer von Operanden erwartet ein Operator.

Immer wenn Sie einen Operator sehen, schieben Sie den Operator auf den Auswertungsstapel und schieben das entsprechende Tupel auf den Zählerstapel.

Immer wenn Sie einen Operanden (wie 3,5 usw.) sehen, überprüfen Sie das oberste Tupel des Count-Stapels und dekrementieren Sie die Anzahl der Operanden, die in diesem Tupel noch zu sehen sind.

Wenn die Anzahl der noch zu beobachtenden Operanden gleich Null ist, wird das Tupel aus dem Stapel "Anzahl" entfernt. Dann wird aus dem Auswertungs-Stack die Anzahl der benötigten Operanden herausgesprungen (das wissen Sie wegen des anderen Wertes des Tupels), den Operator loslassen und die Operation ausführen, um einen neuen Wert (oder Operand) zu erhalten.

Schieben Sie nun den neuen Operanden auf den Auswertungsstapel zurück. Dieser neue Operanden-Push bewirkt, dass Sie einen weiteren Blick auf den oberen Teil des Count-Stacks werfen und dasselbe tun, was wir gerade getan haben (Dekrementieren der gesehenen Operanden, vergleichen mit Null etc.).

Wenn die Anzahl der Operanden nicht null wird, fahren Sie mit dem nächsten Token in der Eingabe fort.

Zum Beispiel sagen Sie, dass Sie + 3 + 4/20 4 bewerten mussten

Die Stapel sehen wie folgt aus (links oben ist der Stapel)

Count                  Evaluation                   Input
                                                   + 3 + 4 / 20 4

(2,2)                   +                            3 + 4 / 20 4

(2,1)                   3 +                            + 4 / 20 4

(2,2) (2,1)             + 3 +                            4 / 20 4

(2,1) (2,1)             4 + 3 +                            / 20 4

(2,2) (2,1) (2,1)       / 4 + 3 +                            20 4

(2,1) (2,1) (2,1)       20 / 4 + 3 +                            4

(2,0) (2,1) (2,1)       4 8 / 4 + 3 +                   

Since it has become zero, you pop off two operands, the operator / 
and evaluate and push back 5. You pop off (2,0) from the Count stack.

(2,1) (2,1)                5 4 + 3 +

Pushing back you decrement the current Count stack top.

(2,0) (2,1)               5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack.

(2,0)                          9 3 + 

                               12

BEARBEITEN:

Ein Freund schlug einen Weg vor, dies ohne mehrere Stapel zu tun:

Beginne am Ende, gehe zum ersten Operator. Die Token rechts davon sind Operanden. Evaluieren und wiederholen. Scheint viel einfacher als mit zwei Stapeln. Wir können eine doppelt verknüpfte Liste verwenden, um die Eingabe darzustellen, die wir während der Verarbeitung ändern. Wenn Sie auswerten, löschen Sie Knoten und fügen Sie dann das Ergebnis ein. Oder Sie könnten vielleicht nur einen Stapel verwenden.


Beliebte Antwort

KISS, im Umkehrschluss als Postfix-Ausdruck auswerten.




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