Konvertieren von Reverse Polish Notation
https://stackoverflow.com/questions/113424
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es eine Möglichkeit Reverse Polish Notation in „normale“ mathematische Notation zu interpretieren, wenn entweder mit C ++ oder C #? Ich arbeite für ein Ingenieurbüro, so dass sie verwenden RPN gelegentlich und wir müssen einen Weg, es zu konvertieren. Irgendwelche Vorschläge?
Lösung
Ja. Denken Sie an, wie ein RPN-Rechner funktioniert. Statt nun den Wert zu berechnen, anstatt Sie den Vorgang, um den Baum hinzufügen. So zum Beispiel 2 3 4 + *, wenn Sie auf den + zu bekommen, dann eher als 7 auf dem Stapel setzen, setzen Sie (+ 3 4) auf dem Stapel. Und in ähnlicher Weise, wenn Sie die * erhalten (Ihr Stack wird zu diesem Zeitpunkt aussieht 2 (+ 3 4) *), wird es (* 2 (+ 3 4)).
Dies ist Präfixnotation, die Sie dann zu Infix konvertieren. Traverse der Baum von links nach rechts, Tiefe zuerst. Für jede „innere Ebene“, wenn der Vorrang des Betreibers niedriger ist, werden Sie den Betrieb in Klammern setzen müssen. Hier also werden Sie sagen, 2 * (3 + 4), weil die + niedrigere Priorität hat als *.
Hope, das hilft!
Edit: Es gibt eine Feinheit (abgesehen von nicht einstelligen Operationen in der oben unter Berücksichtigung): Ich nahm Linksassoziativität Operatoren. Für rechtsassoziativ (z.B. **), dann erhalten Sie unterschiedliche Ergebnisse für 2 3 4 ** ** ⇒ (** 2 (** 3 4)) gegen 2 3 ** 4 ** ⇒ (** (** 2 3) 4).
Wenn Infix vom Baum zu rekonstruieren, wobei beide Fälle zeigen, dass die Priorität nicht Bracketing erfordert, aber in Wirklichkeit braucht der letztere Fall eingeklammert werden ((2 ** 3) ** 4). Also, für rechts assoziative Operatoren, der linke Zweig muss höherrangigen sein (statt höheren oder-gleich) zu vermeiden Bracketing.
Auch weitere Gedanken sind, dass Sie Klammern für den rechten Zweig der - und / Betreiber zu müssen.
Andere Tipps
Der Rangierbahnhof Algorithmus verwendet wird Infix (das heißt algebraische) zu RPN konvertieren. Das ist das Gegenteil von dem, was Sie wollen.
Können Sie mir ein Beispiel für Ihre RPN Eingabe geben? Ich bin ein Veteran HP Rechner Benutzer / Programmierer. Ich nehme an, Sie haben einen Stapel enthält alle Eingänge und Operatoren. Ich würde vermuten, dass Sie den Ausdrucksbaum rekonstruieren müssen und dann den Baum durchqueren, um die Infix Form zu erzeugen.
C # nicht für das Parsen von Reverse Polish Notation (RPN) .You'll benötigt eine integrierte Unterstützung nicht hat Ihren eigenen Parser zu schreiben, oder eine online finden.
Es gibt Dutzende von Anleitungen für die Umwandlung von Postfix Form (RPN) infix (algebraische Gleichung). Schauen Sie sich auf dieser , vielleicht werden Sie es nützlich finden, und Sie können versuchen, ‚Reverse Engineering‘ es postfix Ausdrücke Infix Form, unter Berücksichtigung der Tatsache zu konvertieren, dass es eine mehr Infixnotation für eine gegebene postfix sein kann. Es gibt sehr wenige nützliche Beispiele, die tatsächlich Umwandlung Postfix Infix diskutieren. Hier ist ein 2-teiliger Eintrag, den ich sehr nützlich erwiesen. Es hat auch einige Pseudo-Code:
Wenn Sie Rubin lesen können, Sie ein paar gute Lösungen für dieses finden hier
Ein Ansatz ist das Beispiel aus dem zweiten Kapitel des Drachen Buchs nehmen die erläutern, wie ein Parser schreiben von Infix zu Postfixnotation zu konvertieren, und umkehren.
Wenn Sie etwas Quelltext (string / s) haben, die Sie suchen aus RPN (Postfixnotation) konvertieren zu „normalen Notation“ (Infix), ist dies sicherlich möglich (und wahrscheinlich nicht zu schwer).
RPN wurde für Stack-basierten Maschinen entwickelt, wie die Art und Weise der Betrieb dargestellt wurde ( "2 + 3" -> "2 3 +") passen, wie es tatsächlich auf der Hardware (Push "2" auf den Stapel durchgeführt wurde, Push "3" auf den Stapel, knallen oben zwei Argumente Stapel aus und fügen sie sie, drücken sie wieder auf Stack).
Im Grunde wollen Sie, indem die zwei Ausdrücke, die Sie auf „Blattknoten“ und die Operation selbst, die danach kommt, die „Eltern-Knoten“ betreiben wollen einen Syntaxbaum aus Ihrem RPN erstellen. Dies wird wahrscheinlich durch rekursiv Blick auf Ihre Eingabezeichenfolge durchgeführt werden (Sie werden wahrscheinlich sicherstellen möchten, dass Teilausdrücke sind für zusätzliche Klarheit richtig eingeklammert, wenn sie es nicht schon sind).
Sobald Sie diese Syntaxbaum, können Sie Ausgabe-Präfix, Infix oder Postfixnotation einfach durch eine Vorbestellung tun, post-Ordnung oder in Ordnung Traversal dieses Baumes (auch hier das einklammern Ihre Ausgabe für Klarheit, wenn gewünscht ).
können einige weitere Informationen hier .
Ich schrieb nur eine Version in Java, es ist hier und eine in Objective-C, über hier .
Möglicher Algorithmus : Angenommen, Sie haben einen Stapel mit dem Eingang in rpn wie der Benutzer es geben würde, z.B. 8, 9, *. Sie durchlaufen das Array von Anfang bis Ende, und Sie immer das aktuelle Element entfernen. Dieses Element, das Sie bewerten. Wenn es ein Operand ist, fügen Sie es auf einem Ergebnis-Stack. Wenn es ein Operator das Ergebnis Stapel pop zweimal (für binäre Operationen) für die Operanden und schreiben das Ergebnis Zeichenfolge auf dem Ergebnis-Stack.
Mit dem Beispiel Eingabe von " 8, 9, +, 2, * " Sie diese Werte auf der resultstack bekommen (eckige Klammern einzelne Elemente anzuzeigen) :
Schritt 1: [8]
Schritt 2: [8], [9]
Schritt 3: [(8 + 9)]
Schritt 4: [(8 + 9)], [2]
Schritt 5: [(8 + 9) * 2]
Wenn der Eingangsstapel leer ist, sind Sie fertig und die resultStack einziges Element ist Ihr Ergebnis. (Beachten Sie jedoch, dass die mehrfachen Eingaben oder solche enthalten könnten, die nicht sinnvoll, wie ein führenden Betrieb: „+ 2 3 /".)
Die Implementierungen in den Links absichtlich verwenden keine Eigenbau-Typen für z.B. Betreiber oder Operanden noch es gilt z.B. Verbundmuster. Es ist nur so sauber und einfach, so dass es leicht und portiert jede andere Sprache verstanden werden kann.
Portierungs es zu C # ist gerade nach vorne.
