Die Reihenfolge der Operationen in der Programmierung verstehen
Tauchen Sie in die Welt des Shunting Yard Algorithmus ein – wir zeigen Ihnen, wie Sie Ausdrücke in maschinenlesbare Formate umwandelt.
Als Programmierer haben wir die Macht, Computer dazu zu bringen, unsere Befehle auszuführen. Doch selbst wenn wir die Kontrolle haben, verbirgt sich oft eine unsichtbare Magie im Code. Dies trifft besonders zu, wenn Sie mit Hochsprachen arbeiten, die vorgefertigte Funktionen bieten, so wie die meisten von uns es tun.
Die Reihenfolge der Operationen
Stellen Sie sich vor, Sie möchten diesen Beispiel-Ausdruck auswerten:
5 + 10 * 3
Nach der mathematischen Reihenfolge der Operationen würden Sie zuerst 10 mit 3 multiplizieren und dann 5 zum Produkt addieren. Aber wie genau würden Sie einem Computer beibringen, dies zu tun? Es gibt verschiedene Möglichkeiten, diesen Ausdruck zu analysieren, aber einige erfordern mehr Hintergrundwissen als andere.
Dieses Tutorial wird den Ausdruck in das richtige Format umwandeln. Sobald er in einer maschinenlesbaren Form vorliegt, können Sie ihn durch deinen Analysealgorithmus geben, der ihn berechnen wird. Dieses Tutorial konzentriert sich auf vier Operatoren: Addition, Subtraktion, Multiplikation und Division.
Verständnis der Infix-Notation
Obwohl Sie es vielleicht noch nicht bemerkt haben, sind Sie wahrscheinlich bereits mit der Infix-Notation vertraut. Der Beispiel-Ausdruck ist in Infix-Notation geschrieben:
5 + 10 * 3
Das bedeutet, dass die Operatoren zwischen den Operanden stehen, auf die sie wirken.
Was ist Postfix-Notation?
Wie bereits erwähnt, müssen Sie den Ausdruck in ein Format umwandeln, das der Computer verstehen kann. Dieses Format wird als Postfix-Notation bezeichnet. Ausdrücke, die in Postfix-Notation geschrieben sind, haben alle Operatoren, die ihren Operanden folgen. Dies ist wichtig, denn wenn die Maschine Ausdrücke in diesem Format liest, wird sie niemals auf einen Operator stoßen, bevor sie auf die Operanden stößt, auf die er wirkt, was bedeutet, dass sie nicht hin und her gehen muss.
Der Beispiel-Ausdruck: 5 + 10 * 3 wird zu: 5 10 3 * +
Das mag ungewöhnlich aussehen, aber es gibt eine Methodik, um zu diesem Ergebnis zu gelangen.
Benutzerfreundliche Umwandlung von Infix in Postfix
Füge Klammern in Reihenfolge der Priorität ein:
(5 + (10 * 3))
Bewege jeden Operator nach rechts, direkt vor seine schließende Klammer:
(5 (10 3 *) +)
Lassen Sie die Klammern weg, und Sie erhalten den Ausdruck in Postfix-Notation:
5 10 3 * +
Hier ist ein weiteres Beispiel, um zu zeigen, dass die Operatoren nicht unbedingt immer am Ende stehen:
8 * 4 + 2
((8 * 4) + 2)
((8 4 *) 2 +)
8 4 * 2 +
Auch dies ist nicht ideal für den Computer. Er wüsste immer noch nicht, wo er die Klammern setzen soll. Glücklicherweise gibt es einen Algorithmus, um die gleichen Ergebnisse zu erzielen.
Anwendung des Shunting Yard Algorithmus
Der Shunting Yard Algorithmus wurde von Dijkstra entwickelt, um die Infix-Notation in Postfix-Notation umzuwandeln. Bevor Sie weitergehen, lassen Sie uns kurz die beiden Datenstrukturen überprüfen, die Sie hier verwenden werden: einen Stapel (Stack) und eine Warteschlange (Queue). Sie können ein Array verwenden, um beide Datenmengen zu speichern. Der Hauptunterschied ergibt sich aus der Reihenfolge, in der Sie die Daten hinzufügen und entfernen.
Warteschlange: Wenn Sie Daten in eine Warteschlange einfügen, fügen Sie sie hinten an. Stellen Sie sich vor, Sie stehen in einer Schlange für eine Veranstaltung, und jede Person in der Schlange ist ein Element in der Warteschlange. Wenn Sie zur Schlange gehen, werden Sie automatisch hinten in die Schlange eingereiht. Wenn die Veranstaltung beginnt und Personen in die Veranstaltung gelassen werden (Elemente aus der Warteschlange entfernt werden), werden sie von vorne aus der Schlange gezogen, da diese Personen schon länger dort sind. Sie können sich das mit dem Akronym FIFO merken: „First In, First Out“ (Erstes rein, erstes raus).
Stapel: Jedes Mal, wenn Sie ein neues Element zum Stapel hinzufügen, wird es oben (oder vorne) platziert, anstatt hinten. Wenn Sie ein Element aus dem Stapel entfernen möchten, popen Sie das oberste Element ab. Da neue Elemente immer oben landen, werden die neuen zuerst entfernt, wenn Sie etwas entfernen möchten. Dies kann mit dem Akronym LIFO gemerkt werden: „Last In, First Out“ (Zuletzt rein, zuerst raus).
Hinweis: Der Rest dieses Tutorials wird die Begriffe „push“ und „pop“ für Stacks verwenden. Eine „push“-Aktion bezieht sich auf das Hinzufügen eines neuen Elements oben auf den Stack. Eine „pop“-Aktion bezieht sich auf das Entfernen des zuletzt hinzugefügten Elements oben auf dem Stack.
Für diesen Algorithmus gehen wir davon aus, dass Sie einen temporären Stapel für die Operatoren (Operator-Stapel) und eine Warteschlange haben, die das Endergebnis speichert.
Wie es funktioniert
Der Shunting Yard Algorithmus folgt vier grundlegenden Schritten:
- Analysieren Sie den Ausdruck von links nach rechts.
- Wenn Sie einen Operanden sehen, geben Sie ihn sofort in die Ergebnis-Warteschlange aus.
- Wenn Sie einen Operator sehen:
- Wenn der Operator-Stapel leer ist, fügen Sie den eintreffenden Operator zum Operator-Stapel hinzu.
- Wenn der eintreffende Operator eine höhere Priorität hat als das, was sich derzeit oben auf dem Operator-Stapel befindet, fügen Sie den eintreffenden Operator oben auf den Stapel hinzu.
- Wenn der eintreffende Operator die gleiche Priorität hat, entfernen Sie den obersten Operator vom Stapel, geben ihn in die Warteschlange aus und fügen Sie den eintreffenden Operator zum Stapel hinzu.
- Wenn der eintreffende Operator eine niedrigere Priorität hat, entfernen Sie den obersten Operator vom Stapel, geben Sie ihn in die Warteschlange aus und vergleichen Sie den eintreffenden Operator mit dem neuen obersten Element des Stapels.
- Sobald Sie den gesamten Ausdruck analysiert haben, entfernen Sie alle verbleibenden Symbole (Tokens) vom Operator-Stapel.
Auswertung eines Infix-Ausdrucks mit dem Shunting Yard Algorithmus
Es ist schwer, diese Schritte zu verstehen, ohne sie in Aktion zu sehen. Lassen Sie uns durch das obige Beispiel gehen und versuchen, es mit dem Algorithmus zu formatieren.
Konvertieren Sie diesen Ausdruck von Infix-Notation in Postfix-Notation:
5 + 10 * 3
Richten Sie Ihre beiden Arrays ein – eines für die Ergebnisausgabe und eines für den temporären Operator-Stapel:
Ausdruck = 5 + 10 * 3
Ergebnis = []
Operator-Stapel = []
Zuerst lesen Sie den Ausdruck von links nach rechts. Also haben Sie zuerst die 5. Da dies ein Operand ist, können Sie ihn sofort ausgeben:
Ausdruck = + 10 * 3
Ergebnis = [5]
Operator-Stapel = []
Als Nächstes sehen Sie das +. Der Operator-Stapel ist leer, also können Sie ihn dort hinzufügen:
Ausdruck = 10 * 3
Ergebnis = [5]
Operator-Stapel = [+]
Als Nächstes kommt die 10, also geben Sie sie sofort aus:
Ausdruck = * 3
Ergebnis = [5, 10]
Operator-Stapel = [+]
Jetzt treffen Sie einen weiteren Operator, *. Da der Operator-Stapel nicht leer ist, müssen Sie ihn mit dem aktuellen obersten Element des Operator-Stapels vergleichen, um zu sehen, welcher eine höhere Priorität hat.
Das aktuelle oberste Element ist +. Im Vergleich der beiden wissen Sie, dass die Multiplikation eine höhere Priorität als die Addition hat. Das bedeutet, dass Sie sie oben auf den Stapel legen können:
Ausdruck = 3
Ergebnis = [5, 10]
Operator-Stapel = [*, +]
Jetzt treffen Sie auf ihren letzten Wert, die 3. Da dies kein Operator ist, können Sie sie sofort ausgeben:
Der Ausdruck ist jetzt leer
Ergebnis = [5, 10, 3]
Operator-Stapel = [*, +]
Da der Ausdruck jetzt leer ist, bleibt nur noch, alle verbleibenden Symbole (Tokens) vom Operator-Stapel zu entfernen und sofort auszugeben. Beim Entfernen vom Stapel nehmen Sie immer das oberste Element, also nehmen Sie zuerst das * und dann das +.
Ergebnis = [5, 10, 3, *, +]
Und das war’s! Wie Sie sehen können, entspricht es der vorherigen Methode, bei der Sie Klammern hinzufügen, aber auf diese Weise ist es für einen Computer viel einfacher.
Prioritätsregeln
Sie haben vielleicht bemerkt, dass es einen Punkt gab, an dem Sie anstelle des Algorithmus eigene Kenntnisse verwendet haben, um eine Wahl zu treffen, welche Operation als nächstes durchgeführt wird: die Festlegung, welcher Operator eine höhere Priorität hat.
Es ist jetzt nicht wichtig, während Sie die Konzepte hinter dem Algorithmus verstehen, aber wenn Sie den tatsächlichen Code schreiben, um dies zu lösen, müssen Sie einige Prioritätsregeln festlegen.
Sie müssen ein Objekt erstellen, das jeden Operator im Grunde genommen bewertet. Sie geben den Multiplikations- und Divisionsoperatoren eine Bewertung von 2 und den Additions- und Subtraktionsoperatoren eine Bewertung von 1.
const prioritaet = {
"*": 2,
"/": 2,
"+": 1,
"-": 1
};
Auswertung eines Postfix-Ausdrucks
Sie haben nun den Ausdruck in Postfix-Notation. Jetzt können Sie dieses Format verwenden, um ihn auszuwerten
Algorithmus zur Auswertung des Ausdrucks
So funktioniert es:
- Beginnen Sie mit einem leeren Stapel.
- Analysieren Sie das erste Token im Ausdruck.
- Wenn es ein Operand ist, legen Sie es auf den Stapel.
- Wenn es ein Operator ist, entfernen Sie die entsprechende Anzahl von Operanden vom Stapel in temporäre Variablen. (Zum Beispiel ist die Multiplikation ein binärer Operator, also wissen Sie, dass Sie beim Parsen und Treffen eines Multiplikationsoperators zwei Operanden entfernen müssen.)
- Bewerten Sie diesen Ausdruck mit dem aktuellen Operator und den beiden entfernten Operanden.
- Legen Sie dieses Ergebnis oben auf den Stapel.
- Wiederholen Sie die Schritte 2-7, bis der Ausdruck leer ist.
Im Beispiel handelt es sich nur um binäre Operatoren, daher können Sie immer zwei Operanden entfernen, wenn Sie einen Operator sehen. Wenn Sie das Beispiel aufnehmen möchten, um alle Operatoren zu verarbeiten, müssen Sie auch unäre Operatoren wie ! behandeln.
Durchlaufen des Algorithmus
Lassen Sie uns einige Pseudocode verwenden, um den Algorithmus zur Auswertung des Beispiels in Postfix-Notation zu demonstrieren:
5 10 3 * +
Zuerst legen Sie jeden Operanden auf den Stapel, bis Sie auf einen Operator stoßen:
Ausdruck = [5, 10, 3, *, +]
Stapel = [3, 10, 5]
Jetzt kommen Sie zum ersten Operator, *, was bedeutet, dass es Zeit ist, mit dem Entfernen zu beginnen. Sie entfernen, bis Sie zwei Werte haben:
Ausdruck = [+]
Stapel = [30, 5]
tempOperand1 = 3
tempOperand2 = 10
tempOperator = *
eval(tempOperand1 + tempOperator + tempOperand2) // 3 * 10
Sie bewerten das und erhalten 30, und dann legen Sie dies wieder oben auf den Stapel. Jetzt haben Sie Folgendes:
Ausdruck = [+]
Stapel = [30, 5]
Jetzt fangen Sie an, den Ausdruck erneut zu analysieren, und stoßen sofort auf einen Operator. Wieder müssen Sie vom Stapel entfernen, bis Sie zwei Operanden haben:
Ausdruck = []
Stapel = []
tempOperand1 = 30
tempOperand2 = 5
tempOperator = +
eval(tempOperand1 + tempOperator + tempOperand2) // 30 + 5
Sie entfernen 30 und die 5 und sind bereit, erneut zu bewerten. 5 + 30 ergibt 35, und Sie können dies jetzt oben auf den Stapel legen. Wenn Sie zu Ihrem ursprünglichen Ausdruck zurückkehren, um das nächste Token zu parsen, stellen Sie fest, dass er leer ist!
Ausdruck = []
Stapel = [35]
Das bedeutet entweder, dass Sie fertig sind oder dass der ursprüngliche Ausdruck fehlerhaft war. Überprüfen Sie das, indem Sie sich den Stapel ansehen. Er enthält nur einen Wert, also sind Sie fertig, und 35 ist das endgültige Ergebnis des ursprünglichen Ausdrucks 5 + 10 * 3.
Verständnis der Präfix-Notation
Der Algorithmus zur Auswertung eines Ausdrucks in Präfix-Notation ist im Wesentlichen derselbe, außer dass Sie diesmal von rechts nach links lesen. Mit einer kleinen Modifikation des Codes können Sie auch Präfix-Notation auswerten.
Wenn Sie zu Ihrer ursprünglichen Methode zurückkehren und Klammern hinzufügen und Operatoren verschieben, können Sie Präfix-Notation auf die gleiche Weise wie Postfix umwandeln. Statt die Operatoren ans Ende ihrer Operanden zu verschieben, bewegen Sie sie an den Anfang. Nachdem Sie das getan haben, können Sie die Klammern einfach weglassen, und Sie haben Ihren Ausdruck in Präfix-Notation in der Programmierung!
5 + 10 * 3
(5 + (10 * 3))
(+ 5 (* 10 3))
+ 5 * 10 3
