Klammerprüfung mit fehlerhaftem Stack
Ein Schülertandem entwickelt im Projekt ein Java-Programm, das die Klammerung arithmetischer Ausdrücke prüfen soll. Vorgabe: Betrachtet werden nur die drei Klammerpaare (), [] und {}; Operanden, Operatoren und Leerzeichen werden ignoriert. Der Stack ist als Array der festen Länge 100 implementiert, mit den Methoden push(char), pop(), top() und isEmpty(). Beim Testlauf meldet das Programm für den Ausdruck „([a+b)]“ fälschlich „korrekt“. Auch „a+b)“ wird akzeptiert, obwohl eine schließende Klammer ohne Gegenstück vorliegt. Bei mehr als 100 öffnenden Klammern bricht nichts ab: push überschreibt stillschweigend den letzten Eintrag, und das Programm liefert am Ende „korrekt“. Die Methode pop() gibt bei leerem Stack den Wert 0 zurück und lässt den Zeiger unverändert. Im Sitzungsprotokoll steht außerdem, dass die Variable top zwischen zwei Testläufen nicht zurückgesetzt wird, sodass der zweite Lauf sofort „inkorrekt“ ergab. Die Lehrkraft verlangt eine belastbare Begründung statt einer bloßen Fehlerliste.
1. Erklären Sie anhand der beiden Ausdrücke „([a+b)]“ und „a+b)“, welche Fehlentscheidung der Algorithmus trifft, und beschreiben Sie die korrekte Prüfung mit den Stack-Operationen.
Read the worked answer
Symptomdeutung. Beide Ausdrücke werden akzeptiert, obwohl die Typen nicht zusammenpassen bzw. der Stack bei einer schließenden Klammer leer ist. Das lässt sich nur so erklären, dass beim Lesen einer schließenden Klammer entweder gar kein Typvergleich mit top() stattfindet oder der Rückgabewert 0 von pop() als gültiges Gegenstück durchgeht. Beides ist plausibel, weil pop() bei Unterlauf keinen Fehler signalisiert, sondern 0 liefert – ein Wert, der in einem char-Stack wie ein Zeichen aussieht.
Durchlauf bei korrektem Algorithmus.
- „([a+b)]“: push '(' → push '[' → bei ')' liefert top() das Zeichen '['. Da '[' nicht das Gegenstück zu ')' ist, muss sofort „inkorrekt“ folgen. Das Programm popt stattdessen weiter, bei ']' ebenso, der Stack ist am Ende leer, und isEmpty() liefert true – daher „korrekt“.
- „a+b)“: Beim ')' ist der Stack leer. Der Unterlauf muss als Fehler behandelt werden, nicht als Treffer.
Korrekte Regel. Öffnende Klammer: push. Schließende Klammer: wenn isEmpty() → ablehnen; wenn top() nicht das passende Gegenstück ist → ablehnen; sonst pop. Am Ende akzeptieren genau dann, wenn isEmpty() gilt. Zusätzlich muss top vor jedem Lauf auf 0 gesetzt werden, sonst bleibt Restzustand aus dem Vorlauf erhalten. Diese vier Fälle sollte man vor dem Testen als Invariante formulieren.
2. Bewerten Sie die feste Array-Größe 100 und den Umgang mit Über- und Unterlauf. Schlagen Sie zwei Alternativen vor und begründen Sie, welche Sie für dieses Projekt wählen.
Read the worked answer
Bewertung. Die feste Länge 100 ist eine unbelegte Annahme über die maximale Schachtelungstiefe. Da push bei Überlauf stillschweigend überschreibt, entstehen falsche Ergebnisse statt Fehler – die schlechteste Variante, weil der Fehler unentdeckt bleibt. Ein Ausdruck mit 150 öffnenden Klammern ist syntaktisch zulässig, das Programm würde ihn aber als „korrekt“ ausgeben.
Zwei Alternativen.
- Dynamisches Array (z. B. ArrayList): push ist amortisiert O(1), die Kapazität wächst bei Bedarf. Einfache Umstellung, da die Stack-Logik erhalten bleibt.
- Verkettete Liste: push/pop in O(1) ohne Kapazitätsgrenze, aber höherer Speicherbedarf pro Element und schlechtere Cache-Lokalität.
Entscheidung. Für dieses Projekt ist das dynamische Array die bessere Wahl: Die maximale Tiefe ist zwar praktisch klein, aber nicht garantiert; der Aufwand für die Umstellung ist minimal, und die Amortisierung reicht aus. Wichtiger als die Struktur ist die Fehlerbehandlung: push muss bei voller Kapazität wachsen oder eine Ausnahme werfen, pop bei leerem Stack eine definierte Ausnahme (z. B. EmptyStackException) – nicht 0 zurückgeben. Ein Rückgabewert 0 ist hier besonders gefährlich, weil er mit dem Zeichen '\0' verwechselbar ist und der Aufrufer den Fehler nicht erkennen kann. Die Wahl sollte man mit einem Testfall über 100 Ebenen belegen.
3. Entwerfen Sie eine Testsuite nach Äquivalenzklassen mit mindestens vier Klassen und geben Sie zu jeder Klasse ein Beispiel mit erwartetem Ergebnis.
Read the worked answer
Vorgehen. Die Eingaben werden nach der Wirkung auf den Stack klassifiziert, nicht nach zufälligen Beispielen. Grenzfälle (leer, genau eine Klammer, Tiefe 100/101) werden zusätzlich betrachtet, weil dort die Implementierungsfehler sitzen.
| Klasse | Beispiel | Erwartung | Begründung |
|---|---|---|---|
| keine Klammern | „a+b“ | korrekt | Stack bleibt leer, isEmpty am Ende wahr |
| korrekt verschachtelt | „{[()]}“ | korrekt | jedes Gegenstück passt, Stack endet leer |
| Typfehler | „([a+b)]“ | inkorrekt | ')' trifft auf '[' |
| überzählig schließend | „a+b)“ | inkorrekt | Unterlauf beim pop |
| überzählig öffnend | „((a+b)“ | inkorrekt | Stack am Ende nicht leer |
| Grenze Tiefe | 100 bzw. 101 öffnende Klammern | korrekt bzw. korrekt (nach Umstellung) | prüft Überlaufverhalten |
Begründung der Auswahl. Die Klassen decken die vier möglichen Ausgänge des Algorithmus ab (leer, passend, Typfehler, Unterlauf) plus den Überlauf als Ressourcengrenze. „([a+b)]“ und „a+b)“ sind nicht redundant, weil sie unterschiedliche Zweige ansprechen: Typvergleich versus Leerprüfung. Ein Testfall mit Nicht-Klammer-Zeichen („a1+2“) prüft, dass diese korrekt ignoriert werden. Zusätzlich sollte ein Wiederholungstest zweimal hintereinander laufen, um den nicht zurückgesetzten top-Zeiger aufzudecken – genau dieser Fehler wäre sonst in keinem Einzeltest sichtbar geworden.