Datenstruktur - Ausdrucksanalyse

Die Art und Weise, einen arithmetischen Ausdruck zu schreiben, ist als a bekannt notation. Ein arithmetischer Ausdruck kann in drei verschiedenen, aber äquivalenten Notationen geschrieben werden, dh ohne das Wesen oder die Ausgabe eines Ausdrucks zu ändern. Diese Notationen sind -

• Infix-Notation
• Präfix (polnisch) Notation
• Postfix (Reverse-Polish) Notation

Diese Notationen werden so benannt, wie sie den Operator im Ausdruck verwenden. Das werden wir hier in diesem Kapitel lernen.

Infix-Notation

Wir schreiben Ausdruck in infix Notation, zB a - b + c, wo Operatoren verwendet werden in-zwischen Operanden. Es ist für uns Menschen leicht, in Infix-Notation zu lesen, zu schreiben und zu sprechen, aber das gleiche gilt nicht für Computergeräte. Ein Algorithmus zur Verarbeitung der Infixnotation kann hinsichtlich Zeit- und Raumverbrauch schwierig und kostspielig sein.

Präfixnotation

In dieser Notation ist der Operator prefixIn Operanden geschrieben, dh der Operator wird vor die Operanden geschrieben. Zum Beispiel,+ab. Dies entspricht der Infix-Notationa + b. Die Präfixnotation wird auch als bezeichnetPolish Notation.

Postfix-Notation

Dieser Notationsstil ist bekannt als Reversed Polish Notation. In diesem Notationsstil ist der Operatorpostfixzu den Operanden, dh der Operator wird nach den Operanden geschrieben. Zum Beispiel,ab+. Dies entspricht der Infix-Notationa + b.

Die folgende Tabelle versucht kurz, den Unterschied in allen drei Notationen zu zeigen -

Sr.Nr.	Infix-Notation	Präfixnotation	Postfix-Notation
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	a ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Analysieren von Ausdrücken

Wie wir bereits besprochen haben, ist es keine sehr effiziente Möglichkeit, einen Algorithmus oder ein Programm zum Parsen von Infix-Notationen zu entwerfen. Stattdessen werden diese Infixnotationen zuerst in Postfix- oder Präfixnotationen konvertiert und dann berechnet.

Um einen arithmetischen Ausdruck zu analysieren, müssen wir uns auch um die Priorität und Assoziativität des Operators kümmern.

Vorrang

Wenn sich ein Operand zwischen zwei verschiedenen Operatoren befindet, wird durch den Vorrang eines Operators vor anderen entschieden, welcher Operator zuerst den Operanden übernimmt. Zum Beispiel -

Da die Multiplikationsoperation Vorrang vor der Addition hat, wird zuerst b * c ausgewertet. Eine Tabelle mit der Priorität des Operators wird später bereitgestellt.

Assoziativität

Assoziativität beschreibt die Regel, nach der Operatoren mit derselben Priorität in einem Ausdruck erscheinen. Zum Beispiel haben im Ausdruck a + b - c sowohl + als auch - die gleiche Priorität. Welcher Teil des Ausdrucks zuerst ausgewertet wird, wird durch die Assoziativität dieser Operatoren bestimmt. Hier bleiben sowohl + als auch - assoziativ, sodass der Ausdruck als ausgewertet wird(a + b) − c.

Vorrang und Assoziativität bestimmen die Reihenfolge der Bewertung eines Ausdrucks. Es folgt eine Operator-Prioritäts- und Assoziativitätstabelle (höchste bis niedrigste) -

Sr.Nr.	Operator	Vorrang	Assoziativität
1	Potenzierung ^	Höchste	Richtig assoziativ
2	Multiplikation (∗) & Division (/)	Zweithöchster	Linker Assoziativer
3	Addition (+) & Subtraktion (-)	Am niedrigsten	Linker Assoziativer

Die obige Tabelle zeigt das Standardverhalten von Operatoren. Zu jedem Zeitpunkt der Ausdrucksbewertung kann die Reihenfolge mithilfe von Klammern geändert werden. Zum Beispiel -

Im a + b*c, der Ausdrucksteil b* *cwird zuerst bewertet, wobei die Multiplikation Vorrang vor der Addition hat. Wir verwenden hier Klammern füra + b zuerst ausgewertet werden, wie (a + b)*c.

Postfix-Bewertungsalgorithmus

Wir werden uns nun den Algorithmus zur Bewertung der Postfix-Notation ansehen -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Um die Implementierung in der Programmiersprache C zu sehen, klicken Sie bitte hier .