Aufgabe 1
-
Entwerfen Sie einen einen Automaten, der arithmetische Ausdrücke
in polnischer Postfix-Notation akzeptiert.
-
Beschreiben Sie informell, welche zusätzlichen Aktionen
bei den Zustandsübergängen unternommen werden müssten, damit
die Ausdrücke auch berechnet würden.
-
Setzen Sie das ganze in einen Algorithmus um, programmieren
Sie es ggf.
Lösung
Ein einfacher endlicher Automat kann natürlich kein
PP-Kalkulator sein, schon deshalb, weil er sich keine
Zwischensummen merken kann. Man kann aber das Verhalten solch
eines Rechners gut mit einem Automaten modellieren, an dessen
Kanten noch Annotierungen über interne Abläufe angebracht sind,
und dies Modell dann sehr einfach programmieren.
Wir betrachten hier als Eingabealphabet Ziffer, Leerzeichen,
und als einzigen Operator (beispielhaft) das '+', und gehen
davon aus, das die Stackverwaltenden Funktionen
push und
pop in
den üblichen Bedeutungen zur Verfügung stehen:
Der entsprechende Programmcode ist dann eine
switch
bzw.
case-Anweisung, die
dei Zustandsnummer als Entscheidungstag verwendet. In den
Einzelfällen stehen dann die annotierten Aktionen.
Als Beispiel in C-ähnlicher Syntax das Programmfragment, das den
Automaten realisiert:
state = 1;
switch (state) {
case 0: /* q0 /
c = getchar();
if (c == '+') {
res = pop() + pop();
push(res);
}
if (isnumber(c)) {
wert = tonumber(c);
state = 1;
}
break;
case 1: /* q1 */
c = getchar();
if (c == '+') {
res = wert + pop();
push(res);
state = 0:
}
if (isnumber(c)) {
wert = wert*10 + tonumber(c);
}
if (c == ' ') {
push(wert);
state = 0;
}
break;
};
