LeetCode 224 Basic Calculator: Stack-Lösung in Python mit einem Trace

LeetCode 224, Basic Calculator, verlangt von dir, einen String aus Ziffern, +, -, Klammern und Leerzeichen auszuwerten, ohne eval zu verwenden. Es gibt keine Multiplikation oder Division, also musst du keine Operatorrangfolge beachten. Die einzige Schwierigkeit sind die Klammern, und ein Stack mit gespeicherten Zuständen löst das sauber in einem einzigen Durchlauf.

Das Problem

Gegeben ist ein String s, der einen Ausdruck mit nicht-negativen ganzen Zahlen, +, -, (, ) und Leerzeichen darstellt. Gib seinen Wert zurück. Das Minuszeichen kann auch ein unäres Operator sein, wie in -(2 + 3).

Beispiele:

Die Kernidee

Scanne von links nach rechts und behalte drei Dinge im Blick: das laufende Ergebnis, das aktuelle Vorzeichen und die Zahl, die gerade aufgebaut wird. Wenn du auf eine ( stößt, beginnst du einen Unterausdruck. Speichere das Ergebnis und das Vorzeichen vor der Klammer auf einem Stack und starte dann neu mit Ergebnis 0 und Vorzeichen +1. Wenn du auf eine ) stößt, schließe den Unterausdruck ab, multipliziere ihn mit dem gespeicherten Vorzeichen und addiere ihn zum gespeicherten Ergebnis.

Behandle jedes Zeichen:

Am Ende addierst du das letzte sign * num.

def calculate(s):
    result, sign, num = 0, 1, 0
    stack = []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            result += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif ch == ")":
            result += sign * num
            num = 0
            result *= stack.pop()   # the sign before the parenthesis
            result += stack.pop()   # the result before the parenthesis
    return result + sign * num

Die Pop-Reihenfolge ist wichtig: Das Vorzeichen wurde zuletzt gepusht, also wird es zuerst gepoppt.

Trace

Ausdruck: 1-(2+3).

1 - (2 + 3) = -4, was übereinstimmt.

Unäres Minus

Ein führendes Minus funktioniert ohne speziellen Code. Am Anfang ist num 0, also addiert das erste - sign * 0 zum Ergebnis und setzt dann das Vorzeichen auf -1. Dasselbe gilt nach einer (: Der gespeicherte Zustand setzt result auf 0 und sign auf +1 zurück, also wird (-2) genauso behandelt.

Komplexität

• Zeit: O(n), ein Durchlauf über den String.
• Speicher: O(n) im schlimmsten Fall bei tief verschachtelten Klammern, da der Stack zwei Werte pro geöffneter Klammer speichert.

Ich habe diese Funktion mit 4.000 zufälligen Ausdrücken mit verschachtelten Klammern und unären Minuszeichen getestet und mit Pythons eigener Auswertung verglichen – alle stimmten überein.

Alternative: Rekursion

Du kannst auch eine rekursive Funktion schreiben, die einen Ausdruck parst und sich selbst aufruft, wenn sie auf ( stößt. Das liest sich natürlich, birgt aber das Risiko, bei tief verschachtelter Eingabe das Rekursionslimit zu erreichen, daher ist die Stack-Version in Python sicherer.

Erweiterungen, nach denen Interviewer fragen

Randfälle

Häufige Fehler

1. Jede Ziffer als eigene Zahl behandeln.
2. Vergessen, am Ende das letzte sign * num zu addieren.
3. In der falschen Reihenfolge poppen.
4. num nach einem Operator nicht zurücksetzen.
5. Ein führendes Minus falsch behandeln.

Wie du es im Interview erklärst

1. Kläre die erlaubten Zeichen und ob unäres Minus vorkommt.
2. Sag, dass es kein Rangfolgeproblem gibt, also die Klammern die einzige Herausforderung sind.
3. Beschreibe die drei Variablen und was ein Stack speichert.
4. Gehe 1-(2+3) am Whiteboard durch.
5. Nenne die Komplexität und erwähne dann die Calculator-II-Erweiterung.

Verwandte Übungen

Sieh dir unseren Big-O-Spickzettel für die Komplexitätsbegriffe an, den AI-LeetCode-Tutor-Leitfaden und den Leitfaden zum Coding-Interview-Assistenten. Valid Parentheses und Decode String verwenden dieselbe Stack-Idee.

Sprich deinen Trace beim Üben laut mit. Ein Mock-Interview-Transkript zeigt, ob du den Zweck des Stacks erklärt hast. Befolge die Regeln des Arbeitgebers zu KI-Tools in jeder Live-Bewertung.