Modellierung des Shunting-Yard-Algorithmus

9

Hintergrund:

Ich versuche eine Variante des Shunting-Yard-Algorithmus zu implementieren, aber statt den Ausdruck auszugeben RPN-Notation, ich möchte, dass es sich selbst aktualisiert, während Token eingedrückt werden, so dass Ergebnisse in Echtzeit angezeigt werden können (als ob Sie Tasten auf einem Taschenrechner drücken würden und die Anzeige nach jeder Taste aktualisieren müssten).

Hier ist die Shunting-Yard-Klasse ...

%Vor%

Und die Klasse Operation wäre so etwas wie ...

%Vor%

Die Funktion Evaluate() aktualisiert die Stapel entsprechend und der "aktuelle Wert" wäre _operands.Peek()

Hier sind einige der "Operationen", die ich bisher hatte:

public class NullaryOperation : Operation { }
Z.B. Pi, e usw.
Schiebt einfach konstant auf _operands

public class UnaryOperation : Operation { }
Z.B. SquareRoot, Sinus, Cosinus, etc.
Ruft eine Zahl von _operands auf, wertet sie aus und schiebt das Ergebnis auf _operands

public class BinaryOperation : Operation { }
Z.B. +, -, *, /, etc.
Überprüft die Priorität, wertet bei Bedarf das Ergebnis auf _operands

aus

Hier ist das Problem:
Ich brauche die Möglichkeit, öffnende Klammern ( und geschlossene Klammern ) als Teil des Algorithmus auf den Stapel _operations zu schieben. Außerdem, wenn ich eine geschlossene Klammer hinzufüge, muss ich Operanden / Operationen auffüllen, bis ich auf eine offene Klammer stoße.

Ich möchte solche Überprüfungen vermeiden (Überprüfung von Objekttypen):

while (operations.Peek().GetType() != typeof(OpenParen)) { ... }

Ich möchte vermeiden, dass eine Methode wie diese in Operation :

hinzugefügt wird

public abstract bool IsOpenParen();

Ich könnte so etwas tun ...

%Vor%

Wenn alle Untertypen ihren Typ als Enum angeben sollen, scheint dies jedoch ein schlechtes Design zu sein.

Wie sollte ich das so modellieren, dass ich die eingefügten Klammern verfolgen und handhaben kann?

Nebenbei bemerkt: Wenn ich über Klammern als "Operationen" nachdenke, scheint das für mich keinen Sinn zu ergeben. Der Algorithmus auf Wikipedia behandelt sie jedoch so, und ich kann mir keine andere Möglichkeit vorstellen, ihre Position relativ zu anderen "echten" Operationen zu verfolgen.

Danke.

    
user807566 13.03.2013, 13:54
quelle

1 Antwort

1
%Vor%

StarPilot gibt einen korrekten Hinweis, indem er einen weiteren ShuntingYard in den Stapel legt, aber der korrekte Weg besteht darin, ein ShuntingYard als Operand und nicht als Operation anzugeben. Sobald ein verschachteltes ShuntingYard erscheint, werden nun alle nachfolgenden Operanden und Operationen an es übergeben. Es sollte eine Vorbereitung vorgenommen werden, damit ein ShuntingYard eine schließende Klammeroperation erhält, eine oberste Ebene einen Fehler, und die inneren sollten sich selbst auswerten und ersetzen, indem sie Operand mit dem Ergebnis ihrer Auswertung enthält.

    
Vesper 14.03.2013 14:08
quelle

Tags und Links