Gibt es eine Möglichkeit, die umgekehrte polnische Notation in "normale" mathematische Notation zu interpretieren, wenn entweder C ++ oder C # verwendet wird? Ich arbeite für ein Ingenieurbüro, deshalb benutzen sie gelegentlich RPN und wir brauchen einen Weg, um es zu konvertieren. Irgendwelche Vorschläge?
Ja. Denken Sie daran, wie ein RPN-Rechner funktioniert. Anstatt den Wert zu berechnen, fügen Sie stattdessen die Operation zum Baum hinzu. Also, zum Beispiel, 2 3 4 + * , wenn du zum + kommst, dann stellst du (+ 3 4) auf den Stapel, anstatt 7 auf den Stapel zu legen. Und ähnlich, wenn du zu dem * kommst (dein Stack wird in diesem Stadium wie 2 (+ 3 4) * aussehen), wird es (* 2 (+ 3 4)) .
Dies ist die Präfix-Notation, die Sie dann in Infix konvertieren müssen. Durchquere den Baum von links nach rechts, Tiefe zuerst. Für jede "innere Ebene" müssen Sie, wenn die Priorität des Operators niedriger ist, die Operation in Klammern setzen. Hier sagen Sie also 2 * (3 + 4) , weil das + eine niedrigere Priorität hat als *.
Hoffe, das hilft!
Edit: Es gibt eine Subtilität (abgesehen davon, dass die obigen unären Operationen nicht berücksichtigt wurden): Ich habe linksassoziative Operatoren angenommen. Für rechtsassoziativ (z. B. ** ) erhalten Sie unterschiedliche Ergebnisse für 2 3 4 ** ** ⇒ (** 2 (** 3 4)) gegenüber 2 3 ** 4 ** ⇒ (** (** 2 3) 4) .
Bei der Rekonstruktion von Infix aus dem Baum zeigen beide Fälle, dass der Vorrang keine Belichtungsreihen erfordert, aber in Wirklichkeit muss der letztere Fall in Klammern gesetzt werden ( (2 ** 3) ** 4 ). Für rechtsassoziative Operatoren muss der linke Zweig daher eine höhere Priorität haben (anstelle von höher oder gleich), um eine Belichtungsreihenfolge zu vermeiden.
Weitere Überlegungen sind, dass Sie auch Klammern für den rechten Zweig der Operatoren - und / benötigen.
Der Rangier-Yard-Algorithmus wird verwendet, um Infix (d. h. algebraisch) in RPN umzuwandeln. Dies 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 Taschenrechner Benutzer / Programmierer. Ich nehme an, Sie haben einen Stapel mit allen Eingaben & amp; Betreiber. Ich würde vermuten, dass Sie den Ausdrucksbaum rekonstruieren müssen und dann den Baum durchlaufen müssen, um das Infix-Formular zu erzeugen.
C # hat keine integrierte Unterstützung für das Parsing von Reverse Polish Notation (RPN). Sie müssen Ihren eigenen Parser schreiben oder einen online finden.
Es gibt Dutzende Tutorials zum Umwandeln von Postfix-Form (RPN) in Infix (Algebraische Gleichung). Werfen Sie einen Blick auf dies , vielleicht finden Sie es nützlich und Sie können versuchen, es zu 'reverse engineer' zu machen wandeln Sie Postfix-Ausdrücke in Infix-Formulare um, wobei zu beachten ist, dass es mehrere Infix-Notationen für ein gegebenes Postfix-Formular geben kann. Es gibt sehr wenige nützliche Beispiele, die tatsächlich die Umwandlung von Postfix in Infix diskutieren. Hier ist ein zweiteiliger Eintrag, den ich sehr nützlich fand. Es hat auch einen Pseudo-Code:
Ein Ansatz ist das Beispiel aus dem zweiten Kapitel des Drachenbuchs , das erklärt, wie man ein Parser, um von Infix zu Postfix-Notation zu konvertieren, und umgekehrt.
Wenn Sie einen Quelltext (String / s) haben, den Sie von RPN (Postfix-Notation) in "normale Notation" (Infix) konvertieren möchten, ist dies sicherlich möglich (und wahrscheinlich nicht zu schwierig).
RPN wurde für stackbasierte Maschinen entwickelt, da die Art und Weise, wie die Operation dargestellt wurde ("2 + 3" - & gt; "2 3 +") zur tatsächlichen Ausführung auf der Hardware passte (2 auf Stapel schieben) , drücke "3" auf den Stapel, öffne zwei Argumente aus dem Stapel und füge sie hinzu, schiebe sie zurück auf den Stapel).
Grundsätzlich möchten Sie einen Syntaxbaum aus Ihrem RPN erstellen, indem Sie die 2 Ausdrücke, die Sie verwenden wollen, auf "Blattknoten" und die Operation selbst, die danach den "Elternknoten" darstellt, ausführen. Dies wird wahrscheinlich geschehen, indem Sie Ihre Eingabezeichenfolge rekursiv betrachten (Sie werden wahrscheinlich sicherstellen wollen, dass Unterausdrücke für zusätzliche Klarheit in Klammern gesetzt sind, wenn sie nicht bereits vorhanden sind).
Sobald Sie diesen Syntaxbaum haben, können Sie die Präfix-, Infix- oder Postfix-Notation einfach durch Ausführen einer Vororder, Post-Order oder In-Order-Traversierung dieses Baumes ausgeben (wiederum die Ausgabe in Klammern für die Klarheit, falls gewünscht) ).
Einige weitere Informationen finden Sie hier .
Ich habe gerade eine Version in Java geschrieben, es ist hier und eins in Objective-C, über hier .
Möglicher Algorithmus : Wenn Sie einen Stapel mit der Eingabe in rpn haben, wie der Benutzer ihn eingeben würde, z. 8, 9, *. Sie durchlaufen das Array vom ersten bis zum letzten und entfernen immer das aktuelle Element. Dieses Element werten Sie aus. Wenn es sich um einen Operanden handelt, fügen Sie es auf einem Ergebnis-Stack hinzu. Wenn es sich um einen Operator handelt, blenden Sie den Ergebnisstapel zweimal (für binäre Operationen) für die Operanden ein und schreiben die Ergebniszeichenfolge in den Ergebnisstapel.
Mit der Beispieleingabe von " 8, 9, +, 2, * " erhalten Sie diese Werte im resultstack (eckige Klammern zur Angabe einzelner Elemente) :
Schritt 1: [8]
Schritt 2: [8], [9]
Schritt 3: [(8 + 9)]
Schritt 4: [(8 + 9)], [2]
Schritt 5: [(8 + 9) * 2]
Wenn der Eingabestapel leer ist, sind Sie fertig und das einzige Element von ResultStack ist Ihr Ergebnis. (Beachten Sie jedoch, dass die Eingabe mehrere Einträge enthalten kann oder solche, die keinen Sinn ergeben, wie eine führende Operation: "+ 2 3 /".)
Die Implementierungen in den Verbindungen verwenden absichtlich keine selbstgemachten Typen für z. Operatoren oder Operanden noch gilt es z.B. zusammengesetztes Muster. Es ist einfach sauber und einfach, so dass es leicht verstanden und in jede andere Sprache portiert werden kann.
Das Portieren nach C # ist einfach.