Können alle RPN-Ausdrücke so dargestellt werden, dass alle Operatoren links und alle Operanden rechts erscheinen?

Question

Ich habe mich davon überzeugt, dass sie es nicht können.

Nehmen Sie zum Beispiel:

4 4 + 4 /

Stapel:4 Stack:4 4 4 + 4 = 8 Stack:8 Stack:8 4 8 /4 = 2 Stack:2

Es gibt zwei Möglichkeiten, wie Sie den obigen Ausdruck mit denselben Operatoren und Operanden schreiben können, sodass die Operanden an erster Stelle stehen:"4 4 4 + /" und "4 4 4 / +", von denen keiner auf 2 bewertet wird.

"4 4 4 + /" Stack:4 Stack:4 4 Stack:4 4 4 4 + 4 = 8 Stack:4 8 4/8 = 0,5 Stack:0,5

"4 4 4 / +" Stack:4 Stack:4 4 Stack:4 4 4 4/4 = 1 Stack:4 1 4 + 1 = 5 Stack:5

Wenn Sie die Möglichkeit haben, Gegenstände auf dem Stapel auszutauschen, ist das möglich, andernfalls nein.

Gedanken?

Answer 1

Betrachten Sie den algebraischen Ausdruck:

(a + b) * (c + d)

Die offensichtliche Übersetzung in RPN wäre:

a b + c d + *

Auch wenn eine Swap-Operation verfügbar ist, glaube ich nicht, dass es eine Möglichkeit gibt, alle Operatoren auf der rechten Seite zu sammeln:

a b c d +
a b S

wobei S die Summe von c und d ist.Zu diesem Zeitpunkt konnten Sie nicht eine einzige Swap-Operation verwenden, um sowohl a als auch b für eine +-Operation an ihren Platz zu bringen.Stattdessen benötigen Sie eine ausgefeiltere Stapeloperation (z. B. Rollen), um a und b an die richtige Stelle zu bringen.Ich weiß auch nicht, ob ein Rollvorgang in allen Fällen ausreichen würde.

Answer 2

Tatsächlich haben Sie nicht nur die Antwort, sondern auch einen schlüssigen Beweis geliefert, indem Sie ein Gegenbeispiel untersucht haben, das ausreicht, um die im Titel implizierte Annahme zu widerlegen.

Answer 3

Ich weiß, dass dies ein sehr alter Thread ist, aber ich habe ihn erst heute gefunden und wollte sagen, dass die Antwort auf die ursprüngliche Frage meiner Meinung nach JA lautet.Ich bin zuversichtlich, dass alle RPN-Ausdrücke so dargestellt werden können, dass alle Operatoren links und alle Operanden rechts erscheinen, wenn wir zusätzlich zu den normalen arithmetischen Operationen drei zusätzliche „Navigations“-Operatoren in die Darstellung einbeziehen dürfen.

Jeder arithmetische Ausdruck kann als binärer Baum dargestellt werden, mit Variablen und Konstanten an den Blattknoten, binären arithmetischen Operationen an den Zweigen im Baum und unären Operationen wie Negation, Kehrwert oder Quadratwurzel entlang aller Zweige.Die drei zusätzlichen Operationen, die ich vorschlage, stellen den Aufbau eines linken Zweigs, den Aufbau eines rechten Zweigs oder das Erreichen eines Blattknotens in einem Binärbaum dar.Wenn wir nun alle Operanden entsprechend der Position ihrer jeweiligen Blätter im Baum links von der Eingabezeichenfolge platzieren, können wir den Rest der Eingabezeichenfolge mit Operationen versorgen, die angeben, wie der entsprechende Binärbaum im Speicher rekonstruiert und eingefügt werden soll Operanden und mathematische Operationen an den richtigen Stellen einfügen.Abschließend wird ein Tiefenbaum-Traversal-Algorithmus angewendet, um das Ergebnis zu berechnen.

Ich weiß nicht, ob das irgendeine praktische Anwendung hat.Es ist wahrscheinlich eine zu ineffiziente Möglichkeit, Ausdrücke zu kodieren und zu dekodieren.Aber ich bin mir sicher, dass es als akademische Übung machbar ist.

Answer 4

Es reicht aus, jemanden zu zeigen, der es nicht kann, um Ihnen die Antwort darauf zu sagen.

Wenn Sie den Stapelinhalt nicht neu anordnen können, kann der Ausdruck (2+4)*(7+8) nicht neu angeordnet werden.

2 4 + 7 8 + *

Ganz gleich, wie Sie die Reihenfolge ändern, am Ende erhalten Sie etwas, das zusammengefasst werden muss, bevor Sie fortfahren.

Zumindest glaube ich das.