Was ist Infix-Notation?
Eine Infix-Notation ist eine Notation, in der ein Ausdruck in einem üblichen oder normalen Format geschrieben wird. Es handelt sich um eine Notation, bei der die Operatoren zwischen den Operanden liegen. Beispiele für die Infix-Notation sind A+B, A*B, A/B usw.
Wie wir in den obigen Beispielen sehen können, existieren alle Operatoren zwischen den Operanden, es handelt sich also um Infix-Notationen. Daher kann die Syntax der Infix-Notation wie folgt geschrieben werden:
Parsen von Infix-Ausdrücken
Um einen Ausdruck zu analysieren, müssen wir uns um zwei Dinge kümmern, nämlich Vorrang des Operators Und Assoziativität . Unter Operatorpriorität versteht man den Vorrang eines Operators vor einem anderen Operator. Zum Beispiel:
Zeichenfolge Java hinzufügen
A + B * C → A + (B * C)
Da der Multiplikationsoperator einen höheren Vorrang vor dem Additionsoperator hat, wird der B * C-Ausdruck zuerst ausgewertet. Das Ergebnis der Multiplikation von B * C wird zu A addiert.
Rangfolge
| Betreiber | Symbole |
|---|---|
| Klammer | { }, ( ), [ ] |
| Exponentielle Notation | ^ |
| Multiplikation und Division | *, / |
| Addition und Subtraktion | +, - |
Assoziativität bedeutet, dass im Ausdruck Operatoren mit derselben Priorität vorhanden sind. Beispielsweise haben im Ausdruck A + B – C die Operatoren „+“ und „-“ die gleiche Priorität und werden daher mithilfe der Assoziativität ausgewertet. Da sowohl „+“ als auch „-“ linksassoziativ sind, würden sie als (A + B) – C ausgewertet.
Assoziativitätsordnung
| Betreiber | Assoziativität |
|---|---|
| ^ | Rechts nach links |
| *, / | Links nach rechts |
| +, - | Links nach rechts |
Lassen Sie uns die Assoziativität anhand eines Beispiels verstehen.
1 + 2*3 + 30/5
Da im obigen Ausdruck * und / die gleiche Priorität haben, wenden wir die Assoziativitätsregel an. Wie wir in der obigen Tabelle sehen können, haben die Operatoren * und / eine Links-Rechts-Assoziativität, sodass wir vom ganz linken Operator aus scannen. Der Operator, der zuerst kommt, wird zuerst bewertet. Der Operator * erscheint vor dem /-Operator und die Multiplikation würde zuerst durchgeführt.
1+ (2*3) + (30/5)
Java konvertiert char in int
1+6+6 = 13
Was ist Präfixnotation?
Eine Präfixnotation ist eine andere Ausdrucksform, erfordert jedoch keine weiteren Informationen wie Vorrang und Assoziativität, wohingegen eine Infixnotation Informationen zu Vorrang und Assoziativität erfordert. Es ist auch bekannt als polnische Notation . In der Präfixschreibweise steht ein Operator vor den Operanden. Die Syntax der Präfixnotation ist unten angegeben:
Zum Beispiel, Wenn der Infix-Ausdruck 5+1 ist, ist der Präfix-Ausdruck, der diesem Infix-Ausdruck entspricht, +51.
Wenn der Infix-Ausdruck lautet:
a * b + c
↓
*ab+c
String-Array
↓
+*abc (Präfixausdruck)
Betrachten Sie ein anderes Beispiel:
Java-Blasensortierung
A + B * C
Erster Scan: Im obigen Ausdruck hat der Multiplikationsoperator eine höhere Priorität als der Additionsoperator; die Präfixnotation von B*C wäre (*BC).
A + *BC
Zweiter Scan: Im zweiten Scan wäre das Präfix:
+A *BC
Im obigen Ausdruck verwenden wir zwei Scans, um den Infix-Ausdruck in einen Präfix-Ausdruck umzuwandeln. Wenn der Ausdruck komplex ist, benötigen wir eine größere Anzahl von Scans. Wir müssen die Methode verwenden, die nur einen Scan erfordert und das gewünschte Ergebnis liefert. Wenn wir die gewünschte Ausgabe durch einen Scan erreichen, wäre der Algorithmus effizient. Dies ist nur durch die Verwendung eines Stapels möglich.
Konvertierung von Infix in Präfix mithilfe von Stack
K + L - M * N + (O^P) * W/U/V * T + Q
Wenn wir den Ausdruck vom Infix in das Präfix umwandeln, müssen wir den Ausdruck zunächst umkehren.
Der umgekehrte Ausdruck wäre:
Q + T * V/U/W * ) P^O(+ N*M - L + K
Java-Lambda-Ausdrücke
Um den Präfixausdruck zu erhalten, haben wir eine Tabelle erstellt, die aus drei Spalten besteht, nämlich Eingabeausdruck, Stapel und Präfixausdruck. Wenn wir auf ein Symbol stoßen, fügen wir es einfach dem Präfixausdruck hinzu. Wenn wir auf den Operator stoßen, schieben wir ihn in den Stapel.
| Eingabeausdruck | Stapel | Präfixausdruck |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| IN | +* | QTV |
| / | +*/ | QTV |
| IN | +*/ | QTVU |
| / | +*// | QTVU |
| IN | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| Ö | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
Der obige Ausdruck, d. h. QTVUWPO^*//*NM*LK+-++, ist kein endgültiger Ausdruck. Wir müssen diesen Ausdruck umkehren, um den Präfixausdruck zu erhalten.
Regeln für die Konvertierung von Infix- in Präfixausdrücke:
- Kehren Sie zunächst den in der Aufgabe angegebenen Infix-Ausdruck um.
- Scannen Sie den Ausdruck von links nach rechts.
- Wenn die Operanden eintreffen, drucken Sie sie aus.
- Wenn der Bediener eintrifft und feststellt, dass der Stapel leer ist, schieben Sie den Bediener einfach in den Stapel.
- Wenn der eingehende Operator eine höhere Priorität als der TOP des Stapels hat, schieben Sie den eingehenden Operator in den Stapel.
- Wenn der eingehende Operator die gleiche Priorität wie ein TOP des Stapels hat, schieben Sie den eingehenden Operator in den Stapel.
- Wenn der eingehende Operator eine niedrigere Priorität als die oberste Stufe des Stapels hat, wird die oberste Stufe des Stapels eingefügt und gedruckt. Testen Sie den eingehenden Operator erneut am oberen Ende des Stapels und entfernen Sie den Operator vom Stapel, bis der Operator mit einer niedrigeren oder derselben Priorität gefunden wird.
- Wenn der eingehende Operator die gleiche Priorität wie der obere Teil des Stapels hat und der eingehende Operator ^ ist, wird der obere Teil des Stapels entfernt, bis die Bedingung wahr ist. Wenn die Bedingung nicht wahr ist, drücken Sie den ^-Operator.
- Wenn wir das Ende des Ausdrucks erreicht haben, öffnen und drucken Sie alle Operatoren oben im Stapel.
- Wenn der Operator „)“ ist, schieben Sie ihn in den Stapel.
- Wenn der Operator „(“ ist, entfernen Sie alle Operatoren aus dem Stapel, bis die öffnende Klammer ) im Stapel gefunden wird.
- Wenn die Oberseite des Stapels „)“ ist, schieben Sie den Operator auf den Stapel.
- Am Ende kehren Sie die Ausgabe um.
Pseudocode der Infix-zu-Präfix-Konvertierung
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>