Java – Der umfassende Programmierkurs

KAPITEL 27

Workshop: Kellerautomat

In diesem Kapitel:

• Klammerung und Kellerautomat

• Die Datenstruktur

• Die Verarbeitungslogik

In diesem Workshop wollen wir ein kleines Programm schreiben, das einen vollständig geklammerten arithmetischen Ausdruck auswertet, z. B.

((4 + (5 *(7 -3)) + 4))

Vollständig geklammert bedeutet im Prinzip, dass für jede öffnende Klammer eine korrespondierende schließende Klammer vorhanden sein muss. Etwas formaler kann man es induktiv definieren:

Jede Zahl ist ein vollständig geklammerter Ausdruck.

Wenn A und B vollständig geklammerte Ausdrücke sind, dann auch (A+B), (A-B), (A*B), (A/B).

Vollständig geklammerte Ausdrücke lassen sich elegant mit einem sogenannten Kellerautomaten realisieren.

Klammerung und Kellerautomat ...