Datenstrukturen - Ausdrucksanalyse
Die Ausdrucksanalyse ist das klassischste Anwendungsszenario des Stacks.
Die Ausdrucksanalyse zeigt, wie man Stacks verwendet, um Konvertierungen von Infix-, Präfix- und Postfix-Ausdrücken sowie Ausdrücke zu handhaben.
Drei Formen von Ausdrücken
Infix-Ausdruck A + B * C zu Postfix-Ausdruck — Schritt-für-Schritt-Demonstration
Schritt 1A lesenOperand, direkt ausgebenAusgabe: AStack: leer
Schritt 2+ lesenOperator, auf den Stack legenAusgabe: AStack: +
Schritt 3B lesenOperand, direkt ausgebenAusgabe: ABStack: +
Schritt 4* lesen* hat eine höhere Priorität als +, auf den Stack legenAusgabe: ABStack: +*
Schritt 5C lesenOperand, direkt ausgebenAusgabe: ABCStack: +*
Schritt 6EndeAlle Operatoren vom Stack nehmenAusgabe: ABC*+Stack: leer
Endergebnis: A + B * C → A B C * +
Bei der Verarbeitung mathematischer Ausdrücke in einem Computer gibt es drei Darstellungsmethoden:
| Type | Operatorposition | Beispiel | Auswertungsschwierigkeit | Klammerbedarf |
|---|---|---|---|---|
| Infix-Ausdruck | Zwischen Operanden (menschliche Konvention) | A + B * C | Präzedenz und Klammern müssen behandelt werden | Erforderlich |
| Präfixausdruck(Polnische Notation) | Vor den Operanden | + A * B C | Ein einzelner Durchlauf genügt | Nicht erforderlich |
| Postfix-Ausdruck(Umgekehrte Polnische Notation) | Nach den Operanden | A B C * + | Ein einzelner Durchlauf genügt | Nicht erforderlich |
Der größte Vorteil von Postfix- und Präfixausdrücken besteht darin, dass bei der Auswertung keine Operatorrangfolge oder Klammern berücksichtigt werden müssen; man muss nur sequenziell von links nach rechts scannen.
Infix-zu-Postfix-Algorithmus (Idee des Shunting-Yard-Algorithmus)
Der Kernalgorithmus zur Umwandlung eines Infix-Ausdrucks in einen Postfix-Ausdruck wird mit einem Stack implementiert. Der grundlegende Ablauf ist wie folgt:
- Den Infix-Ausdruck von links nach rechts scannen
- Beim Auftreffen aufeinen Operanden(Ziffer/Buchstabe), diesen direkt ausgeben
- Beim Auftreffen aufeinen Operator, dessen Priorität mit dem Operator oben auf dem Stack vergleichen:
- Wenn der oberste Operator auf dem Stack eine höhere oder gleiche Priorität hat, das oberste Element vom Stack nehmen und ausgeben
- Diesen Vorgang wiederholen, bis der aktuelle Operator auf den Stack gelegt werden kann
- Beim Auftreffen aufeine linke Klammer, diese direkt auf den Stack legen
- Wenn man aufeine schließende Klammerstößt, weiter Operatoren vom oberen Ende des Stapels entfernen und ausgeben, bis eine öffnende Klammer angetroffen wird (die öffnende Klammer wird entfernt, aber nicht ausgegeben)
- Nach dem Ende des Scans die verbleibenden Operatoren im Stapel einzeln entfernen und ausgeben
Beispiel
#include <stdio.h>
#include <ctype.h> /* isalnum-Funktion */
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }
/* Gibt die Operatorpriorität zurück: eine höhere Zahl bedeutet höhere Priorität */
int precedence(char op) {
if (op == '+' || op == '-') return 1; /* Addition und Subtraktion haben die niedrigste Priorität */
if (op == '*' || op == '/') return 2; /* Multiplikation und Division haben eine höhere Priorität */
if (op == '^') return 3; /* Potenzierung hat die höchste Priorität */
return 0; /* Kein Operator */
}
Infix-Ausdruck zu Postfix-Ausdruck
Parameter: infix - die Eingabezeichenkette des Infix-Ausdrucks
postfix - der Ausgabepuffer für den Postfix-Ausdruck */
void infixToPostfix(char* infix, char* postfix) {
int i = 0, j = 0;
char c;
while ((c = infix[i++]) != '\0') {
/* Operand (Buchstabe oder Ziffer): direkt ausgeben */
if (isalnum(c)) {
postfix[j++] = c;
}
/* Linke Klammer: direkt pushen */
else if (c == '(') {
push(c);
}
/* Rechte Klammer: Pop ausführen, bis linke Klammer angetroffen wird */
else if (c == ')') {
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
pop(); /* Linke Klammer '(' mit Pop entfernen, aber nicht ausgeben */
}
/* Operator: Präzedenz behandeln */
else {
while (top != -1 &&
precedence(stack[top]) >= precedence(c) &&
stack[top] != '(') {
postfix[j++] = pop();
}
push(c);
}
}
/* Alle verbleibenden Operatoren mit Pop aus dem Stack entfernen */
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0'; /* Ende der Zeichenkette */
}
int main() {
char infix[] = "A+B*C";
char postfix[MAX];
infixToPostfix(infix, postfix);
printf("Infix: %s\n", infix); /* Ausgabe: Infix: A+B*C */
printf("Postfix: %s\n", postfix); /* Ausgabe: Postfix: ABC*+ */
return 0;
}
#include <ctype.h> /* isalnum-Funktion */
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }
/* Gibt die Operatorpriorität zurück: eine höhere Zahl bedeutet höhere Priorität */
int precedence(char op) {
if (op == '+' || op == '-') return 1; /* Addition und Subtraktion haben die niedrigste Priorität */
if (op == '*' || op == '/') return 2; /* Multiplikation und Division haben eine höhere Priorität */
if (op == '^') return 3; /* Potenzierung hat die höchste Priorität */
return 0; /* Kein Operator */
}
Infix-Ausdruck zu Postfix-Ausdruck
Parameter: infix - die Eingabezeichenkette des Infix-Ausdrucks
postfix - der Ausgabepuffer für den Postfix-Ausdruck */
void infixToPostfix(char* infix, char* postfix) {
int i = 0, j = 0;
char c;
while ((c = infix[i++]) != '\0') {
/* Operand (Buchstabe oder Ziffer): direkt ausgeben */
if (isalnum(c)) {
postfix[j++] = c;
}
/* Linke Klammer: direkt pushen */
else if (c == '(') {
push(c);
}
/* Rechte Klammer: Pop ausführen, bis linke Klammer angetroffen wird */
else if (c == ')') {
while (top != -1 && stack[top] != '(') {
postfix[j++] = pop();
}
pop(); /* Linke Klammer '(' mit Pop entfernen, aber nicht ausgeben */
}
/* Operator: Präzedenz behandeln */
else {
while (top != -1 &&
precedence(stack[top]) >= precedence(c) &&
stack[top] != '(') {
postfix[j++] = pop();
}
push(c);
}
}
/* Alle verbleibenden Operatoren mit Pop aus dem Stack entfernen */
while (top != -1) {
postfix[j++] = pop();
}
postfix[j] = '\0'; /* Ende der Zeichenkette */
}
int main() {
char infix[] = "A+B*C";
char postfix[MAX];
infixToPostfix(infix, postfix);
printf("Infix: %s\n", infix); /* Ausgabe: Infix: A+B*C */
printf("Postfix: %s\n", postfix); /* Ausgabe: Postfix: ABC*+ */
return 0;
}
Auswertung von Postfix-Ausdrücken
Auswertung des Postfix-Ausdrucks 5 3 + 2 * — Schritt-für-Schritt-Demonstration
Schritt 1Lies 5Zahl, auf den Stack legenStack: 5
Schritt 2Lies 3Zahl, auf den Stack legenStack: 5 3
Schritt 3Lies +Nimm 3 und 5 vom Stack, berechne 5+3=8, lege das Ergebnis auf den StackStack: 85+3=8
Schritt 4Lies 2Zahl, auf den Stack legenStack: 8 2
Schritt 5Lies *Nimm 2 und 8 vom Stack, berechne 8*2=16, lege das Ergebnis auf den StackStack: 168*2=16
ErgebnisEndeNur 16 verbleibt auf dem Stack, was das berechnete Ergebnis istErgebnis = 16
Postfix 53+2* = 16 (entspricht Infix (5+3)*2)
Bei einem Postfix-Ausdruck ist die Auswertung mit einem Stack sehr einfach: Operanden auf den Stack legen; wenn ein Operator auftritt, zwei Operanden vom Stack nehmen, berechnen und das Ergebnis wieder auf den Stack legen.
Beispiel
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
/* Berechnet den Wert des Postfix-Ausdrucks
Parameter: postfix - Postfix-Ausdruck (Operanden sind einzelne Ziffern 0-9)
Rückgabewert: das berechnete Ergebnis des Ausdrucks */
int evaluatePostfix(char* postfix) {
int i = 0;
char c;
while ((c = postfix[i++]) != '\0') {
/* Operand: in eine Zahl umwandeln und auf den Stack legen */
if (isdigit(c)) {
push(c - '0'); /* '3' in Integer 3 umgewandelt */
}
/* Operator: zwei Operanden vom Stack nehmen, berechnen und wieder auf den Stack legen */
else {
int b = pop(); /* Zweiter Operand (rechter Operand) */
int a = pop(); /* Erster Operand (linker Operand) */
switch (c) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop(); /* Das letzte Element auf dem Stack ist das Endergebnis */
}
int main() {
/* Postfix-Ausdruck "23+5*" entspricht dem Infix-Ausdruck "(2+3)*5" = 25 */
char postfix[] = "23+5*";
int result = evaluatePostfix(postfix);
printf("Postfix %s = %d\n", postfix, result); /* Ausgabe: Postfix 23+5* = 25 */
return 0;
}
#include <ctype.h>
#include <stdlib.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
/* Berechnet den Wert des Postfix-Ausdrucks
Parameter: postfix - Postfix-Ausdruck (Operanden sind einzelne Ziffern 0-9)
Rückgabewert: das berechnete Ergebnis des Ausdrucks */
int evaluatePostfix(char* postfix) {
int i = 0;
char c;
while ((c = postfix[i++]) != '\0') {
/* Operand: in eine Zahl umwandeln und auf den Stack legen */
if (isdigit(c)) {
push(c - '0'); /* '3' in Integer 3 umgewandelt */
}
/* Operator: zwei Operanden vom Stack nehmen, berechnen und wieder auf den Stack legen */
else {
int b = pop(); /* Zweiter Operand (rechter Operand) */
int a = pop(); /* Erster Operand (linker Operand) */
switch (c) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop(); /* Das letzte Element auf dem Stack ist das Endergebnis */
}
int main() {
/* Postfix-Ausdruck "23+5*" entspricht dem Infix-Ausdruck "(2+3)*5" = 25 */
char postfix[] = "23+5*";
int result = evaluatePostfix(postfix);
printf("Postfix %s = %d\n", postfix, result); /* Ausgabe: Postfix 23+5* = 25 */
return 0;
}
Beim Auswerten eines Postfix-Ausdrucks ist die Pop-Reihenfolge der Operanden entscheidend: Der zuerst entnommene istrechter Operand(b), und der später entnommene istlinker Operand(a). Dies ist besonders wichtig bei nicht-kommutativen Operationen wie Subtraktion und Division; eine Umkehrung der Reihenfolge führt zu falschen Ergebnissen.
Vollständiges Beispiel: Infix-Auswertung
Die Verkettung der beiden obigen Schritte ergibt einen vollständigen Rechner: Infix → Postfix → Auswertung.
Beispiel
#include <stdio.h>
#include <ctype.h>
#define MAX 100
/* Hilfsfunktion für Operatorrangfolge (wie oben), Auswertungsfunktion (wie oben), Konvertierungsfunktion (wie oben) */
/* Der Kürze halber werden die oben definierten Funktionen hier weggelassen; fügen Sie sie bei tatsächlicher Verwendung ein */
int main() {
char infix[] = "5+3*2"; /* Infix-Ausdruck */
char postfix[MAX];
infixToPostfix(infix, postfix); /* Schritt 1: In Postfix umwandeln */
printf("Infix: %s\n", infix); /* Ausgabe: Infix: 5+3*2 */
printf("Postfix: %s\n", postfix); /* Ausgabe: Postfix: 532*+ */
int result = evaluatePostfix(postfix); /* Schritt 2: Auswerten */
printf("Ergebnis: %s = %d\n", infix, result);
/* Ausgabe: Ergebnis: 5+3*2 = 11 */
return 0;
}
#include <ctype.h>
#define MAX 100
/* Hilfsfunktion für Operatorrangfolge (wie oben), Auswertungsfunktion (wie oben), Konvertierungsfunktion (wie oben) */
/* Der Kürze halber werden die oben definierten Funktionen hier weggelassen; fügen Sie sie bei tatsächlicher Verwendung ein */
int main() {
char infix[] = "5+3*2"; /* Infix-Ausdruck */
char postfix[MAX];
infixToPostfix(infix, postfix); /* Schritt 1: In Postfix umwandeln */
printf("Infix: %s\n", infix); /* Ausgabe: Infix: 5+3*2 */
printf("Postfix: %s\n", postfix); /* Ausgabe: Postfix: 532*+ */
int result = evaluatePostfix(postfix); /* Schritt 2: Auswerten */
printf("Ergebnis: %s = %d\n", infix, result);
/* Ausgabe: Ergebnis: 5+3*2 = 11 */
return 0;
}