Wikipedia's Kellerautomat Beispiel in C ist total falsch (Stand 11.03.2015).
Nicht nur, dass es im feinsten C programmiert ist, was kein Mensch versteht. Es wird nicht mal ein Kellerautomat implementiert. Die Konfiguration eines Kellerautomats hängt von seinem Zustand, dem zu lesenden Zeichen und dem Zeichen auf dem Stack (Keller) ab.
In dem Beispiel wird aber nur das zu lesende Zeichen und der Stack benutzt. Es gibt kein expliziten Zustand des Automaten. Vielmehr wird der Zustand in dem Kellerspeicher gespeichert. Was nicht Sinn der Sache ist. Das Beispiel verwirrt also mehr, als dass es nutzt.
Ich habe den Beispielcode nach C++ Qt übersetzt und so auch den Fehler gefunden.
#include < QCoreApplication >
#include < QTextStream >
#include < QString >
#include < QDebug >
#include < QStack >
#include < QMap >
int main(int argc, char *argv[]) {
QCoreApplication a(argc, argv);
QStack stack;
QTextStream ss(stdin);
QByteArray s;
/* Eingabestring */
qDebug() << "Bitte Ausdruck eingeben:";
ss >> s;
// Wir benutzen in der Zustandsuebergangsfunktion das Null Byte als Indikator fuer das Ende vom String.
// Fuege es manuell in den String ein.
s += '\0';
/* Start-state auf Stack pushen */
stack.push(0);
/*
Ein einfacher Kellerautomat ("pushdown automaton")
Symbol | ( | ) | \0
---------+---------+--------+-----------
State 0 | PUSH 1 | ERROR | ACCEPT
State 1 | PUSH 1 | POP | ERROR
*/
enum class Actions {PUSH, POP, ERROR, ACCEPT};
QMap< QPair< int, char>, Actions> states;
states.insert(qMakePair(0, '('), Actions::PUSH);
states.insert(qMakePair(0, ')'), Actions::ERROR);
states.insert(qMakePair(0, '\0'), Actions::ACCEPT);
states.insert(qMakePair(1, '('), Actions::PUSH);
states.insert(qMakePair(1, ')'), Actions::POP);
states.insert(qMakePair(1, '\0'), Actions::ERROR);
/* Ausführungsschleife */
bool finish = false;
for(int i=0; i < s.size() && finish == false ; i++) {
/* Aktion auf Basis des Eingabesymbols ermitteln */
auto key = qMakePair(stack.top(), s.at(i));
Actions action = states.value(key, Actions::ERROR);
/* Ausführen der Aktionen */
switch(action) {
case Actions::ERROR: {
qDebug() << "Unerwartetes Zeichen \"" << s.at(i) << "\"an Position" << i+1;
finish = true;
break;
}
case Actions::ACCEPT: {
qDebug() << "Ausdruck akzeptiert!";
finish = true;
break;
}
case Actions::POP: {
stack.pop();
break;
}
case Actions::PUSH: {
stack.push(1);
break;
}
default:
qDebug() << "internal error";
}
}
return 0;
}