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

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

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))

(5 (10 3 *) +)

5 10 3 * +

8 * 4 + 2

((8 * 4) + 2)

((8 4 *) 2 +)

8 4 * 2 +

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:

1. Analysieren Sie den Ausdruck von links nach rechts.
2. Wenn Sie einen Operanden sehen, geben Sie ihn sofort in die Ergebnis-Warteschlange aus.
3. 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.
4. 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

Ausdruck = 5 + 10 * 3

Ergebnis = []

Operator-Stapel = []

Ausdruck = + 10 * 3

Ergebnis = [5]

Operator-Stapel = []

Ausdruck = 10 * 3

Ergebnis = [5]

Operator-Stapel = [+]

Ausdruck = * 3

Ergebnis = [5, 10]

Operator-Stapel = [+]

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 = [*, +]

Der Ausdruck ist jetzt leer

Ergebnis = [5, 10, 3]

Operator-Stapel = [*, +]

Ergebnis = [5, 10, 3, *, +]

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:

1. Beginnen Sie mit einem leeren Stapel.
2. Analysieren Sie das erste Token im Ausdruck.
3. Wenn es ein Operand ist, legen Sie es auf den Stapel.
4. 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.)
5. Bewerten Sie diesen Ausdruck mit dem aktuellen Operator und den beiden entfernten Operanden.
6. Legen Sie dieses Ergebnis oben auf den Stapel.
7. 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 * +

Ausdruck = [5, 10, 3, *, +]
Stapel = [3, 10, 5]

Ausdruck = [+]
Stapel = [30, 5]

tempOperand1 = 3
tempOperand2 = 10
tempOperator = *

eval(tempOperand1 + tempOperator + tempOperand2) // 3 * 10

Ausdruck = [+]
Stapel = [30, 5]

Ausdruck = []
Stapel = []

tempOperand1 = 30
tempOperand2 = 5
tempOperator = +

eval(tempOperand1 + tempOperator + tempOperand2) // 30 + 5

Ausdruck = []
Stapel = [35]

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