Mit dem Stapel arbeiten
Wie bei der Schlange benutzt du den Stapel im Abitur nur über seine vier Methoden – push, top, pop und isEmpty aus der Dokumentation. In der Online-IDE steht die Abiturklasse Stack bereit, sobald ein Block die NRW-Bibliothek lädt.
Werkzeugkasten: zwei Muster
Das Abarbeiten nimmt oben herunter, bis nichts mehr da ist. Danach ist der Stapel leer.
while (!pStapel.isEmpty()) {
String oben = pStapel.top(); // erst nachsehen ...
pStapel.pop(); // ... dann entfernen
// oben verarbeiten
}Das Erhalten legt jedes Element zusätzlich auf einen Hilfsstapel und schichtet am Ende zurück. Danach ist der Stapel wie vorher.
Stack<String> hilf = new Stack<String>();
while (!pStapel.isEmpty()) {
String oben = pStapel.top();
pStapel.pop();
// oben verarbeiten
hilf.push(oben);
}
while (!hilf.isEmpty()) {
pStapel.push(hilf.top());
hilf.pop();
}Auf dem Hilfsstapel liegt alles verkehrt herum. Erst das Zurückschichten dreht die Reihenfolge noch einmal um – und damit wieder richtig.
Aufgabe 1: Abarbeiten
a) Sage voraus, was das Programm ausgibt. Führe es dann aus.
b) Vertausche die beiden Zeilen in der Schleife, sodass pop() vor top() steht. Sage voraus, was nun ausgegeben wird, und prüfe.
Aufgabe 2: Das unterste Element
Das Struktogramm beschreibt die Methode unterstes. Sie liefert das Element, das ganz unten liegt, bei einem leeren Stapel null. Der Stapel soll danach unverändert sein.
a) Verfolge das Struktogramm für einen Stapel, auf den nacheinander Anna, Ben und Cem gelegt wurden. Zeichne nach jeder Schleife, wie pStapel und hilf aussehen.
b) Setze das Struktogramm in der Klasse Stapelwerkzeug unten als Methode String unterstes(Stack<String> pStapel) in Java um. Prüfe mit dem Reiter Testrunner.
Aufgabe 3: Klammern prüfen – erst das Struktogramm
Ein Übersetzer muss feststellen, ob die Klammern eines Ausdrucks richtig gesetzt sind. Gültig sind (), [] und {}, beliebig geschachtelt: (a + [b * c]) - {d} ist in Ordnung, (a + [b * c)] nicht.
a) Begründe, warum ein Stapel dafür genau die richtige Struktur ist.
b) Beschreibe das Verfahren in Worten: Was tust du bei einer öffnenden, was bei einer schließenden Klammer? Woran erkennst du am Ende, dass der Ausdruck gültig war?
c) Entwirf im Editor ein Struktogramm für klammernOk(pText).
d) Setze es in der Klasse Stapelwerkzeug als boolean klammernOk(String pText) um, bis die Tests zu klammernOk grün sind.
Tipp 1: Das Verfahren
- Öffnende Klammer: auf den Stapel legen.
- Schließende Klammer: Der Stapel darf nicht leer sein, und oben muss die passende öffnende Klammer liegen. Dann wird sie heruntergenommen.
- Alle anderen Zeichen: nichts tun.
- Am Ende: Der Stapel muss leer sein.
Tipp 2: Einzelne Zeichen
pText.substring(i, i + 1) liefert das Zeichen an der Stelle i als String. So kann es direkt auf einen Stack<String> gelegt und mit equals verglichen werden.
Eine kleine Hilfsmethode macht den Vergleich übersichtlich:
boolean passt(String pOffen, String pZu) {
return pOffen.equals("(") && pZu.equals(")")
|| pOffen.equals("[") && pZu.equals("]")
|| pOffen.equals("{") && pZu.equals("}");
}Weiterdenken:
e) Stack<String> umgedreht(Stack<String> pStapel) liefert einen neuen Stapel mit denselben Elementen in umgekehrter Reihenfolge. Der übergebene Stapel bleibt unverändert.
f) void einfuegenUnten(Stack<String> pStapel, String pWert) legt pWert ganz unten in den Stapel.