RPN Kurzschluss Auswertung

Ich bin jetzt mitten in der Herstellung eines einfachen Bytecode-Interpreter, der RPN für Ausdruck Notation und wirklich Postfix-Notation für alles verwendet, aber jetzt bin ich zu der Frage gekommen, die ist: Kurzschluss Auswertung tatsächlich sein kann Wird für Postfix-Ausdrücke verwendet? Zum Beispiel beim Auswerten des Ausdrucks (false & & (faktoriell (7)> faktoriell (5))) C++ weiß das Ergebnis des & &-Operators auf den beiden Operanden wertet false, bevor es sogar zum zweiten Operanden kommt, da (false & & alles) ist immer gleich falsch. Jetzt, wenn Sie dies in RPN setzen, erhalten Sie (falsch (7 Fakultät 5 Fakultät) & &).RPN Kurzschluss Auswertung

Ich wollte einen effizienten RPN-Ausdrucksparser erstellen, daher ist das Problem: Wie mache ich einen effizienten RPN-Ausdrucksparser mit Kurzschlussauswertung?

Quelle

2016-07-22 Imanuel Habekotte

Sie schreiben Code. Wir sind nicht hier, um Ihr System für Sie zu entwerfen oder Ihnen beizubringen, wie Sie es entwerfen. –

@MarcB Danke für die Informationen, die ich denke. Jedenfalls habe ich eine nützliche Antwort bekommen, also ja. –

RPN und Postfix Notation sind die gleichen Dinge, nicht zwei verschiedene Dinge. Sie bauen keine RPN-Parser in Interpreter. Die Eingabe ist bereits geparst und kann linear verarbeitet werden. Wenn Sie eine Kurzschlussauswertung wünschen, müssen Sie Verzweigungen einführen. – EJP

Sie würden einen RPN Ausdruck in zwei Phasen auswerten.

Phase 1: Parsen Sie die RPN, und erstellen Sie eine Baumdarstellung des RPN. In diesem Baum hat der Knoten && beispielsweise zwei untergeordnete Knoten für jede Hälfte des Ausdrucks. Das Konstruieren dieses Baums ist ein nahezu identischer Prozess wie das Auswerten der RPN, mit Ausnahme des Bewertungsteils, der durch den Vorgang des Konstruierens eines neuen Knotens ersetzt wird und seine Kindknoten mit ihrem neuen Elternknoten verknüpft und dann den Elternknoten zurück auf den Knoten drückt RPN Auswertestapel.

Phase 2: Evaluieren Sie den konstruierten Baum mit rekursiven Abstieg. An dieser Stelle wird die Kurzschlussauswertung trivial: Bewerten Sie das linke Kind eines && und entscheiden Sie dann, ob Sie das rechte Kind tatsächlich auswerten möchten.

Das Gleiche gilt für den || Knoten, etc ...

Quelle

2016-07-22 16:52:57

Danke das ist perfekt! :) –

Frage: Wäre es anders, wenn ich anstelle von RPN PN benutze? –

Die erste Phase wäre natürlich anders. Unterschiedliche Logik, um den Baum zu konstruieren. Alternativ könnte der PN-Parser so geschrieben werden, dass er ein "ignore" -Flag trägt, wo er die Eingabe nur analysiert und schluckt, ohne sie zu bewerten, wobei er das Flag rekursiv weitergibt; Mit den Operatoren '&&' und '||' wird das Flag für die Auswertung auf der rechten Seite gesetzt, wenn die Auswertung auf der linken Seite die Auswertung der rechten Seite unnötig macht. –

Antwort

Verwandte Themen