Bei meine Beschäftigung mittm Thema Expressionparser stieß ich auf ein paar hochinteressante Algorithmen, und auch paar listenreiche Klassen.
Zunächst mal Expression-Beispiel:
Das ist ein Ausdruck in Infix-Schreibweise, und unter Berücksichtigung der Klammer-Regeln und der Vorrang-Regeln der Operatoren, kann man das ausrechnen, kommt
Beim Rechnen geht man so vor, dass man Teil-Ausdrücke bildet, die jeweils mehrere Werte zusammenrechnen zu einem Wert. Dabei darf man nicht einfach von links nach rechts vorgehen, sondern muß die Operatoren mit höherem Vorrang vorrangig abarbeiten (deshalb heißt das auch "Operator-Vorrang" ;)).
Ums ganz schlimm zu machen, wird durch Klammerung auch noch in die Vorränge eingegriffen, also dafür einen gscheiten Algorithmus zu erfinden ist Aufgabe für Genies.
Nun gabs mal ein Genie in Polen, der hat eine klammerfreie Notation erfunden, also eine Schreibweise, wie man obigen Ausdruck auch ohne Klammern und Vorränge eindeutig formulieren kann. Als noch praktischer erwies sich, wenn man die Operatoren hinter die Operanden schreibt, und so sieht dann die "umgekehrt-polnische Notation" obiger Expression aus, alias "Postfix-Notation":Sieht völlig krank aus, aber Computer finden das klasse, denn in dieser Notation können sie den Ausdruck ganz einfach von links nach rechts abarbeiten, und kommt auch
Also von links nach rechts: Wenns eine Zahl ist, dann legt man sie auf einen Zahlen-Stack. Wenns ein Operator ist, dann nimmt dieser sich seine Operanden von genau diesem Stack runter, berechnet damit einen Wert, und legt den wieder drauf:
Nicht wahr: bei einer Zahl nimmt der Stack um eins zu, bei einem binären Operator um eins ab, denn 2 Zahlen werden runtergenommen, und eine neue wieder drauf.
Das ist nur bei binären Operatoren so, bei unären bleibt der Stack gleich, weil eine runter und eine drauf.
Unärer Operator?? Naja, zB. die Negation, also das Minus-Zeichen vor einer Zahl:Dassis postfix-mäßig schlecht mit dem Minus-Zeichen, weils dann nicht mehr eindeutig ist. Also auf "Postfix" notiere ich die Negation mit '!'.
Gesehen? In Zeile#7 bleibt die Höhe des Stacks konstant, nur der letzte Wert wurde ausgetauscht durch seine Negation.
Aber ich spinne noch weiter, denn wenns binäre und unäre Operatoren gibt, gibts dann auch nulläre? Also Operatoren, die gar keine Operanden brauchen, um einen Wert zu bilden?
Klar gibts das - Zahlen zum Beispiel! Und wie man sieht: Zahlen verhalten sich genau nach Postfix-Rechenregel als nulläre Operatoren: Sie nehmen keinen Wert runter, und legen einen Wert drauf.
Zahlen - genauer gesagt - Konstanten sind also nulläre Operatoren.
Unds gibt noch mehr nulläre Operatoren, nämlich die Variablen - kommen wir noch zu.
Zunächst aber der "Shunting-yard-Algorithmus" zur Konvertierung von Infix- in Postfix-Notation:
Zu deutsch "Rangierbahnhof"-Algo, weils einen Operator-Stack gibt, in den jeder Operator erst mal (vorwärts) hineinfährt, und nach gewissen Regeln fährt er dann (rückwärts) wieder raus in die Ausgabe.
Die operatorStack-Regel lautet: Bevor ein neuer Operator auf den Stack darf, werden alle Operatoren höheren oder gleichen Ranges vom Stack in die Ausgabe geflusht. Also rangniedere Operatoren verdrängen rang-gleiche und -höhere vom Stack in die Ausgabe. Somit ist der Stack auch sortiert: der höchste obenauf.
Kleine Zwischenfrage: Nulläre Operatoren - welchen Rang haben die? Antwort:
Und Klammern, was ist mit denen? Die kriegen Rang
Die Sonderbehandlung besteht darin, dass trotz niedrigsten Ranges die öffnende Klammer auch ihrerseits keinen Operator vom Stack drängt.
Schließende Klammer flusht dann den Stack in die Ausgabe, bis hin zur öffnende Klammer. Beide Klammern verfallen, also die öffnende wird runtergepoppt, und die schließende wird garnicht erst draufgelegt.
Beachte, wenn mehrere Operatoren verdrängt werden (Zeilen #9, #15, #17), dass sie in umgekehrter Reihenfolge zur Ausgabe kommen.
So sind Stapel nunmal: Was man als letztes drauflegt, bekommt man als erstes wieder runter.
Zunächst mal Expression-Beispiel:
Das ist ein Ausdruck in Infix-Schreibweise, und unter Berücksichtigung der Klammer-Regeln und der Vorrang-Regeln der Operatoren, kann man das ausrechnen, kommt
-15
bei raus.Beim Rechnen geht man so vor, dass man Teil-Ausdrücke bildet, die jeweils mehrere Werte zusammenrechnen zu einem Wert. Dabei darf man nicht einfach von links nach rechts vorgehen, sondern muß die Operatoren mit höherem Vorrang vorrangig abarbeiten (deshalb heißt das auch "Operator-Vorrang" ;)).
Ums ganz schlimm zu machen, wird durch Klammerung auch noch in die Vorränge eingegriffen, also dafür einen gscheiten Algorithmus zu erfinden ist Aufgabe für Genies.
Nun gabs mal ein Genie in Polen, der hat eine klammerfreie Notation erfunden, also eine Schreibweise, wie man obigen Ausdruck auch ohne Klammern und Vorränge eindeutig formulieren kann. Als noch praktischer erwies sich, wenn man die Operatoren hinter die Operanden schreibt, und so sieht dann die "umgekehrt-polnische Notation" obiger Expression aus, alias "Postfix-Notation":Sieht völlig krank aus, aber Computer finden das klasse, denn in dieser Notation können sie den Ausdruck ganz einfach von links nach rechts abarbeiten, und kommt auch
-15
bei raus.Also von links nach rechts: Wenns eine Zahl ist, dann legt man sie auf einen Zahlen-Stack. Wenns ein Operator ist, dann nimmt dieser sich seine Operanden von genau diesem Stack runter, berechnet damit einen Wert, und legt den wieder drauf:
Quellcode
- Berechnung von (Postfix)
- 3 2 + 15 3 / 8 - *
- Schritt ResultStack
- 3 3
- 2 3 2
- + 5 + nimmt 3 2 runter, verrechnet, und gibt 5 wieder drauf
- 15 5 15
- 3 5 15 3
- / 5 5 / nimmt 15 3 runter, verrechnet, und gibt 5 wieder drauf
- 8 5 5 8
- - 5 -3 - nimmt 5 8 runter, verrechnet, und gibt -3 wieder drauf
- * -15 * nimmt 5 -3 runter, verrechnet, und gibt -15 wieder drauf
Das ist nur bei binären Operatoren so, bei unären bleibt der Stack gleich, weil eine runter und eine drauf.
Unärer Operator?? Naja, zB. die Negation, also das Minus-Zeichen vor einer Zahl:Dassis postfix-mäßig schlecht mit dem Minus-Zeichen, weils dann nicht mehr eindeutig ist. Also auf "Postfix" notiere ich die Negation mit '!'.
Aber ich spinne noch weiter, denn wenns binäre und unäre Operatoren gibt, gibts dann auch nulläre? Also Operatoren, die gar keine Operanden brauchen, um einen Wert zu bilden?
Klar gibts das - Zahlen zum Beispiel! Und wie man sieht: Zahlen verhalten sich genau nach Postfix-Rechenregel als nulläre Operatoren: Sie nehmen keinen Wert runter, und legen einen Wert drauf.
Zahlen - genauer gesagt - Konstanten sind also nulläre Operatoren.
Unds gibt noch mehr nulläre Operatoren, nämlich die Variablen - kommen wir noch zu.
Zunächst aber der "Shunting-yard-Algorithmus" zur Konvertierung von Infix- in Postfix-Notation:
Zu deutsch "Rangierbahnhof"-Algo, weils einen Operator-Stack gibt, in den jeder Operator erst mal (vorwärts) hineinfährt, und nach gewissen Regeln fährt er dann (rückwärts) wieder raus in die Ausgabe.
Die operatorStack-Regel lautet: Bevor ein neuer Operator auf den Stack darf, werden alle Operatoren höheren oder gleichen Ranges vom Stack in die Ausgabe geflusht. Also rangniedere Operatoren verdrängen rang-gleiche und -höhere vom Stack in die Ausgabe. Somit ist der Stack auch sortiert: der höchste obenauf.
Kleine Zwischenfrage: Nulläre Operatoren - welchen Rang haben die? Antwort:
99
, also maximal. Dadurch verdrängt eine Zahl nur eine andere Zahl, aber keinen der anderen Operatoren.Und Klammern, was ist mit denen? Die kriegen Rang
0
, und Sonderbehandlung. Rang 0
bewirkt, dass die öffnende Klammer von anneren Operatoren überhaupt nicht verdrängt werden kann.Die Sonderbehandlung besteht darin, dass trotz niedrigsten Ranges die öffnende Klammer auch ihrerseits keinen Operator vom Stack drängt.
Schließende Klammer flusht dann den Stack in die Ausgabe, bis hin zur öffnende Klammer. Beide Klammern verfallen, also die öffnende wird runtergepoppt, und die schließende wird garnicht erst draufgelegt.
Quellcode
- Infix->Postfix - Konvertierung
- (3 + 2) * (15 / 3 - 8)
- Schritt Op-Stack Postfix-Ausgabe
- ( (
- 3 ( 3
- + ( + 3 + verdrängt 3 vom Op-Stack in die Ausgabe
- 2 ( + 2 3
- ) 3 2 + ) Op-Stack + 2 -> Ausgabe 2 +
- * * 3 2 +
- ( * ( 3 2 +
- 15 * ( 15 3 2 +
- / * ( / 3 2 + 15 / Op-Stack 15 -> Ausgabe 15
- 3 * ( / 3 3 2 + 15
- - * ( - 3 2 + 15 3 / - Op-Stack / 3 -> Ausgabe 3 /
- 8 * ( - 8 3 2 + 15 3 /
- ) * 3 2 + 15 3 / 8 - ) Op-Stack - 8 -> Ausgabe 8 -
- <rest-flush> 3 2 + 15 3 / 8 - *
So sind Stapel nunmal: Was man als letztes drauflegt, bekommt man als erstes wieder runter.
Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „ErfinderDesRades“ ()