MINT lernen

Algorithmen mit Stapeln

Zwei Abituraufgaben zu Klammerprüfung und Hilfsstapeln.

Dein Fortschritt:
0 / 0 Aufgaben
1

Klammern im Formeleditor

AFB I–II

Ein Formeleditor prüft Ausdrücke mit runden, eckigen und geschweiften Klammern mit dem bekannten Stapel-Algorithmus: öffnende Klammern werden gepusht, bei einer schließenden Klammer wird gepoppt und verglichen, am Ende muss der Stapel leer sein.

  1. Wenden Sie den Algorithmus auf den Ausdruck ( [ a ] { b ) } an. Geben Sie den Stapelinhalt nach jedem Klammerzeichen und das Ergebnis an.
  2. Begründen Sie, warum es nicht genügt, die öffnenden und schließenden Klammern jeder Art zu zählen.

Hinweise

Hinweis zu Aufgabe a)
Buchstaben werden übersprungen. Achten Sie beim fünften Klammerzeichen darauf, was oben liegt.
Hinweis zu Aufgabe b)
Suchen Sie ein Gegenbeispiel, bei dem die Anzahlen stimmen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

( → [(]; [ → [(, []; ] → pop [ passt → [(]; { → [(, {]; ) → pop liefert {, passt nicht zu ) → fehlerhaft, der Algorithmus bricht ab.

Erwartungshorizont zu Aufgabe b)

Zählen erfasst weder die Reihenfolge noch die Verschachtelung. Beim Ausdruck aus Teil a) gibt es je eine öffnende und schließende Klammer jeder Art, trotzdem ist er falsch. Auch )( hat gleich viele Klammern. Nur der Stapel merkt sich, welche Klammer als letzte geöffnet wurde und deshalb als erste geschlossen werden muss.

2

Das unterste Element

AFB II–III

Für einen Stapel Stack<Integer> s soll die Methode int unterstes(Stack<Integer> s) das unterste Element liefern. Danach muss der Stapel wieder genauso aussehen wie vorher. Ist er leer, soll −1 zurückgegeben werden.

  1. Entwerfen Sie einen Algorithmus für diese Methode und beschreiben Sie ihn in Worten oder als Struktogramm.
  2. Implementieren Sie die Methode.
  3. Überprüfen Sie Ihre Methode für einen leeren Stapel und für einen Stapel mit genau einem Element.

Hinweise

Hinweis zu Aufgabe a)
Das unterste Element ist das letzte, das man beim Umladen in die Hand bekommt.
Hinweis zu Aufgabe b)
Zwei Schleifen: umladen und zurückladen.
Hinweis zu Aufgabe c)
Verfolgen Sie für beide Fälle, wie oft jede Schleife durchlaufen wird.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Hilfsstapel anlegen. Solange s nicht leer ist: oberstes Element mit pop() nehmen, merken und auf den Hilfsstapel legen. Das zuletzt gemerkte Element ist das unterste. Danach alles vom Hilfsstapel zurück auf s laden und den gemerkten Wert zurückgeben; war s leer, −1.

Erwartungshorizont zu Aufgabe b)
public int unterstes(Stack<Integer> s) {
    Stack<Integer> hilf = new Stack<Integer>();
    int u = -1;
    while (!s.isEmpty()) {
        u = s.pop();
        hilf.push(u);
    }
    while (!hilf.isEmpty()) {
        s.push(hilf.pop());
    }
    return u;
}
Erwartungshorizont zu Aufgabe c)

Leerer Stapel: Keine Schleife wird durchlaufen, u bleibt −1 und wird zurückgegeben — korrekt, s bleibt leer. Ein Element x: Erste Schleife einmal, u = x, x liegt auf hilf; zweite Schleife legt x zurück. Rückgabe x, s ist wie vorher. (Einschränkung: Ist −1 selbst ein möglicher Inhalt, ist die Rückgabe mehrdeutig.)