Bevor wir die Konvertierung von der Infix- in die Postfix-Notation verstehen, sollten wir die Infix- und Postfix-Notationen separat kennen.

Ein Infix und ein Postfix sind die Ausdrücke. Ein Ausdruck besteht aus Konstanten, Variablen und Symbolen. Symbole können Operatoren oder Klammern sein. Alle diese Komponenten müssen nach einem Regelwerk angeordnet sein, damit alle diese Ausdrücke anhand des Regelwerks ausgewertet werden können.

Beispiele für Ausdrücke sind:

5 + 6

A - B

(P * 5)

Alle oben genannten Ausdrücke haben eine gemeinsame Struktur, d. h. wir haben einen Operator zwischen den beiden Operanden. Ein Operand ist ein Objekt oder ein Wert, für den die Operation ausgeführt werden soll. In den obigen Ausdrücken sind 5, 6 die Operanden, während „+“, „-“ und „*“ die Operatoren sind.

Was ist Infix-Notation?

Wenn der Operator zwischen die Operanden geschrieben wird, wird er als bezeichnet Infix-Notation . Operand muss nicht immer eine Konstante oder eine Variable sein; es kann auch selbst ein Ausdruck sein.

Zum Beispiel,

(p + q) * (r + s)

Im obigen Ausdruck sind beide Ausdrücke des Multiplikationsoperators die Operanden, d. h. (p + q) , Und (r + s) sind die Operanden.

Im obigen Ausdruck gibt es drei Operatoren. Die Operanden für den ersten Plusoperator sind p und q, die Operanden für den zweiten Plusoperator sind r und s. Während der Durchführung der Bei Operationen am Ausdruck müssen wir einige Regeln befolgen, um das Ergebnis auszuwerten. Im Im obigen Ausdruck würde eine Additionsoperation für die beiden Ausdrücke, d. h. p+q und r+s, durchgeführt, und dann würde die Multiplikationsoperation durchgeführt.

Die Syntax der Infix-Notation ist unten angegeben:

Wenn der Ausdruck nur einen Operator enthält, müssen wir keine Regel anwenden. Zum Beispiel 5 + 2; In diesem Ausdruck kann eine Additionsoperation zwischen den beiden Operanden (5 und 2) durchgeführt werden, und das Ergebnis der Operation wäre 7.

Wenn der Ausdruck mehrere Operatoren enthält, müssen bestimmte Regeln befolgt werden, um den Ausdruck auszuwerten.

Wenn der Ausdruck lautet:

4+6*2

Wenn der Plus-Operator zuerst ausgewertet wird, würde der Ausdruck wie folgt aussehen:

10 * 2 = 20

Wenn der Multiplikationsoperator zuerst ausgewertet wird, würde der Ausdruck wie folgt aussehen:

4 + 12 = 16

Das obige Problem kann durch Befolgen der Operator-Prioritätsregeln gelöst werden. Im algebraischen Ausdruck ist die Rangfolge der Operatoren in der folgenden Tabelle angegeben:

Der erste Vorzug wird der Klammer gegeben; Dann wird den Exponenten als nächstes der Vorzug gegeben. Bei mehreren Exponentenoperatoren wird die Operation von rechts nach links angewendet.

sind Musterbeispiele

Zum Beispiel:

2^2^3 = 2^8

= 256

Anschließend werden Exponenten-, Multiplikations- und Divisionsoperatoren ausgewertet. Wenn beide Operatoren im Ausdruck vorhanden sind, wird die Operation von links nach rechts angewendet.

Als nächstes werden Addition und Subtraktion bevorzugt. Wenn beide Operatoren im Ausdruck verfügbar sind, gehen wir von links nach rechts vor.

Die Operatoren, die die gleiche Priorität haben, werden als bezeichnet Operator-Assoziativität . Wenn wir von links nach rechts gehen, spricht man von Linksassoziativ. Wenn wir von rechts nach links gehen, spricht man von rechtsassoziativ.

Problem mit der Infix-Notation

Um den Infix-Ausdruck auszuwerten, sollten wir über Folgendes Bescheid wissen Vorrang des Operators Regeln, und wenn die Operatoren die gleiche Priorität haben, sollten wir die befolgen Assoziativität Regeln. Die Verwendung von Klammern ist in der Infix-Notation sehr wichtig, um die Reihenfolge zu steuern, in der die Operation ausgeführt werden soll. Klammern verbessern die Lesbarkeit des Ausdrucks. Ein Infix-Ausdruck ist die gebräuchlichste Art, einen Ausdruck zu schreiben, es ist jedoch nicht einfach, den Infix-Ausdruck ohne Mehrdeutigkeit zu analysieren und auszuwerten. Also untersuchten Mathematiker und Logiker dieses Problem und entdeckten zwei andere Möglichkeiten, Ausdrücke zu schreiben: Präfix und Postfix. Beide Ausdrücke erfordern keine Klammern und können ohne Mehrdeutigkeit analysiert werden. Es sind keine Operatorprioritäts- und Assoziativitätsregeln erforderlich.

Postfix-Ausdruck

Der Postfix-Ausdruck ist ein Ausdruck, bei dem der Operator nach den Operanden geschrieben wird. Beispielsweise kann der Postfix-Ausdruck der Infix-Notation ( 2+3) als 23+ geschrieben werden.

Einige wichtige Punkte bezüglich des Postfix-Ausdrucks sind:

• Im Postfix-Ausdruck werden Operationen in der Reihenfolge ausgeführt, in der sie geschrieben wurden, von links nach rechts.
• Es sind keine Klammern erforderlich.
• Wir müssen keine Operatorprioritätsregeln und Assoziativitätsregeln anwenden.

Algorithmus zur Auswertung des Postfix-Ausdrucks

• Scannen Sie den Ausdruck von links nach rechts, bis wir auf einen Operator stoßen.
• Führen Sie den Vorgang aus
• Ersetzen Sie den Ausdruck durch seinen berechneten Wert.
• Wiederholen Sie die Schritte 1 bis 3, bis keine weiteren Operatoren vorhanden sind.

Lassen Sie uns den obigen Algorithmus anhand eines Beispiels verstehen.

Infix-Ausdruck: 2 + 3 * 4

Wir beginnen mit dem Scannen ganz links im Ausdruck. Der Multiplikationsoperator ist ein Operator, der beim Scannen von links nach rechts zuerst erscheint. Der Ausdruck wäre nun:

Ausdruck = 2 + 34*

= 2 + 12

Auch hier scannen wir von links nach rechts und der Ausdruck wäre:

Ausdruck = 2 12 +

= 14

Auswertung des Postfix-Ausdrucks mithilfe des Stacks.

• Scannen Sie den Ausdruck von links nach rechts.
• Wenn wir im Ausdruck auf einen Operanden stoßen, verschieben wir den Operanden in den Stapel.
• Wenn wir im Ausdruck auf einen Operator stoßen, entfernen wir die entsprechenden Operanden vom Stapel.
• Wenn wir mit dem Scannen des Ausdrucks fertig sind, verbleibt der Endwert im Stapel.

Lassen Sie uns die Auswertung des Postfix-Ausdrucks mithilfe des Stapels verstehen.

Beispiel 1: Postfix-Ausdruck: 2 3 4 * +

Das Ergebnis des obigen Ausdrucks ist 14.

Beispiel 2: Postfix-Ausdruck: 3 4 * 2 5 * +

Das Ergebnis des obigen Ausdrucks ist 22.

Algorithmus zur Auswertung des Postfix-Ausdrucks

1. Lies einen Charakter
2. Wenn das Zeichen eine Ziffer ist, konvertieren Sie das Zeichen in int und legen Sie die Ganzzahl in den Stapel.
3. Wenn das Zeichen ein Operator ist,
   • Entfernen Sie die Elemente zweimal vom Stapel, um zwei Operanden zu erhalten.
   • Führen Sie den Vorgang aus
   • Schieben Sie das Ergebnis in den Stapel.

Konvertierung von Infix in Postfix

Hier verwenden wir die Stapeldatenstruktur für die Konvertierung des Infix-Ausdrucks in den Präfix-Ausdruck. Immer wenn ein Operator auftritt, schieben wir den Operator in den Stapel. Wenn wir auf einen Operanden stoßen, hängen wir den Operanden an den Ausdruck an.

Regeln für die Konvertierung vom Infix- in den Postfix-Ausdruck

1. Drucken Sie den Operanden aus, sobald er eintrifft.
2. Wenn der Stapel leer ist oder oben eine linke Klammer enthält, verschieben Sie den eingehenden Operator auf den Stapel.
3. Wenn das eingehende Symbol „(“ ist, schieben Sie es auf den Stapel.
4. Wenn das eingehende Symbol „)“ ist, öffnen Sie den Stapel und geben Sie die Operatoren aus, bis die linke Klammer gefunden wird.
5. Wenn das eingehende Symbol eine höhere Priorität als das oberste Symbol im Stapel hat, schieben Sie es auf den Stapel.
6. Wenn das eingehende Symbol eine niedrigere Priorität als die Oberseite des Stapels hat, wird die Oberseite des Stapels eingefügt und gedruckt. Testen Sie dann den eingehenden Operator mit der neuen Oberseite des Stapels.
7. Wenn der eingehende Operator die gleiche Priorität wie der oberste Operator im Stapel hat, verwenden Sie die Assoziativitätsregeln. Wenn die Assoziativität von links nach rechts erfolgt, öffnen und drucken Sie den oberen Teil des Stapels und drücken Sie dann den eingehenden Operator. Wenn die Assoziativität von rechts nach links erfolgt, drücken Sie den eingehenden Operator.
8. Fügen Sie am Ende des Ausdrucks alle Operatoren des Stapels ein und drucken Sie sie aus.

Lassen Sie es uns anhand eines Beispiels verstehen.

Infix-Ausdruck: K + L - M*N + (O^P) * W/U/V * T + Q

Der letzte Postfix-Ausdruck des Infix-Ausdrucks (K + L - M*N + (O^P) * W/U/V * T + Q) ist KL+MN*-OP^W*U/V/T*+Q+ .