Übungen zu Stapeln

Inhalt

4.2. Übungen zu Stapeln#

4.2.1. Höhe des Stapels bestimmen#

In der folgenden Zelle siehst du die Klasse Stapel, die wir bereits entwickelt haben. Schau dir nun insb. die Methode anzahl_elemente an, mit der man die “Höhe” des Stapels bestimmen kann.

Warum ist diese Lösung ineffizient?

Weil zur Ermittlung der Höhe alle Elemente des Stapels durchlaufen werden müssen.

Es geht natürlich besser - weißt du wie?

Antwort nur anschauen, wenn du nicht allein darauf kommst!

Man kann die aktuelle Höhe des Stapels als Attribut hoehe speichern und dieses in anzahl_elemente einfach zurückgeben.

Man muss dabei allerdings darauf achten, dass…

…bei jedem push und pop das Attribut hoehe hoch- bzw. heruntergezählt wird.

Aufgabe: Ändere die Klasse Stapel und insb. die Methode anzahl_elemente, so dass die Höhe des Stapels nun geschickt verwaltet und ohne Aufwand zurückgegeben wird.

class Stapel:

    class Knoten:
        def __init__(self, inhalt, naechster=None):  # Wenn für naechster kein Wert angegeben wird, ist er None (Standardwert)
            self.inhalt = inhalt
            self.naechster = naechster

    def __init__(self):
        self.anfang: Stapel.Knoten|None = None

    def push(self, daten):
        """legt ein neues Element auf den Stapel"""
        neuer_knoten = Stapel.Knoten(daten, self.anfang)  # Der neue Knoten zeigt auf den bisherigen Anfang
        self.anfang = neuer_knoten  # Der neue Knoten ist jetzt der Anfang

    def pop(self):
        """entfernt das oberste Element vom Stapel und gibt es zurück"""
        if self.anfang is None:
            raise IndexError("Pop-Operation auf leerem Stapel nicht möglich")
        inhalt = self.anfang.inhalt  # Inhalt des ersten Knotens merken
        self.anfang = self.anfang.naechster  # Anfang auf den nächsten Knoten setzen
        return inhalt

    def top(self):
        """gibt das oberste Element des Stapels zurück, ohne es zu entfernen"""
        if self.anfang is None:
            raise IndexError("Top-Operation auf leerem Stapel nicht möglich")
        return self.anfang.inhalt

    def ist_leer(self):
        """gibt True zurück, wenn der Stapel leer ist, sonst False"""
        return self.anfang is None  # Kurzform für if self.anfang is None: return True else: return False
    
    def anzahl_elemente(self):
        """gibt die Anzahl der Elemente auf dem Stapel zurück"""
        # ACHTUNG: Diese Methode ist ineffizient, da sie die gesamte interne Liste durchlaufen muss!
        anzahl = 0
        knoten = self.anfang
        while knoten is not None:
            anzahl += 1
            knoten = knoten.naechster
        return anzahl
    
# Test
s = Stapel()
for i in range(100000):
    s.push(i)
print(s.anzahl_elemente())  # Bei der schlechten Implementierung dauert das lange

Lösung:

4.2.2. Aufgabe: Umgekehrte polnische Notation (UPN)#

In der umgekehrten polnischen Notation (UPN) für Rechenausdrücke werden die Operanden vor den Operatoren geschrieben.

Beispiel: 3 4 + 5 * bedeutet (3 + 4) * 5 = 35

Aufgabe: Schreibe eine Funktion, die einen String in UPN auswertet.

Hinweis

Umgangsprachlich kann man die Berechnung so beschreiben:

Man durchläuft nacheinander alle Elemente des Ausdrucks (jeweils durch Leerzeichen getrennt)
Trifft man auf eine Zahl, legt man sie auf den Stack
Trifft man auf einen Operator op
- nimmt man die beiden obersten Elemente vom Stack
- und verrechnet sie mit dem Operator op.
- Das Ergebnis legt man wieder auf den Stack
Zum Schluss gibt man das oberste Element des Stacks zurück.

Hinweise:

Zerlege den Eingabe-String zuerst mit der split-Methode in Einzelelemente. (Hier findest du eine Erklärung zu split.)
Dann bearbeite mit einer Schleife jedes Element.
Nutze die unten definierte Funktion ist_zahl, um zwischen Zahlen und Operatoren zu unterscheiden.
Ach ja, und falls das noch nicht offensichtlich war: Nutze einen Stapel!

def ist_zahl(string: str):
    """prüft, ob ein String eine Zahl ist. Bsp. ist_zahl("-123") -> True, ist_zahl("abc") -> False"""
    try:
        int(string)
        return True
    except ValueError:
        return False

def berechne_upn(eingabe_im_upn_format: str) -> int:
    """berechnet den Wert eines UPN-Ausdrucks und gibt ihn zurück.
    Beispiel: berechne_upn("3 4 + 6 *") liefert 42"""

    ... # Hier kommt dein Code hin
    
    return None  # Hier musst du den berechneten Wert des Term zurückgeben


# Test: Liste mit Beispielen (jeweils UPN-Ausdruck und erwartetes Ergebnis)
print("Tests für die Funktion berechne_upn:")
beispiele = [
    ("3 4 +", 7),
    ("3 4 -", -1),
    ("3 4 *", 12),
    ("8 4 //", 2),
    ("3 4 + 6 *", 42),
    ("6 7 * 0 *", 0),
    ("2 3 + 4 * 14 + 2 // 20 - 0 3 - *", 9),
    ("2 3 + 4 * 14 + 2 // 20 - -3 *", 9),
    ("42 1 1 - //", "Fehler: Division durch 0"),
]
for upn, erwartet in beispiele:
    try:
        ergebnis = berechne_upn(upn)
        if ergebnis == erwartet:
            print(f"Richtig: {upn} ergibt {ergebnis}")
        else:
            print(f"Falsch: {upn} ergibt {ergebnis}, erwartet war {erwartet}")
    except Exception as e:
        if str(e) == erwartet:
            print(f"Richtig: {upn} wirft {e}")
        else:
            print(f"Falsch: {upn} wirft {e}, erwartet war {erwartet}")

Tests für die Funktion berechne_upn:
Falsch: 3 4 + ergibt None, erwartet war 7
Falsch: 3 4 - ergibt None, erwartet war -1
Falsch: 3 4 * ergibt None, erwartet war 12
Falsch: 8 4 // ergibt None, erwartet war 2
Falsch: 3 4 + 6 * ergibt None, erwartet war 42
Falsch: 6 7 * 0 * ergibt None, erwartet war 0
Falsch: 2 3 + 4 * 14 + 2 // 20 - 0 3 - * ergibt None, erwartet war 9
Falsch: 2 3 + 4 * 14 + 2 // 20 - -3 * ergibt None, erwartet war 9
Falsch: 42 1 1 - // ergibt None, erwartet war Fehler: Division durch 0

Lösung: