LeetCode 224 Basic Calculator: Stack-oplossing in Python met een trace

LeetCode 224, Basic Calculator, vraagt je een string met cijfers, +, -, haakjes en spaties te evalueren zonder eval te gebruiken. Er is geen vermenigvuldiging of deling, dus je hoeft geen operatorprioriteit te regelen. De enige moeilijkheid zijn de haakjes, en een stack met opgeslagen toestanden lost dat netjes op in één pass.

Het probleem

Gegeven een string s die een expressie voorstelt met niet-negatieve gehele getallen, +, -, (, ) en spaties, geef de waarde terug. Het minteken kan ook een unaire operator zijn, zoals in -(2 + 3).

Voorbeelden:

Het kernidee

Scan van links naar rechts en houd drie dingen bij: het lopende resultaat, het huidige teken en het getal dat je opbouwt. Wanneer je een ( tegenkomt, begin je aan een subexpressie. Sla het resultaat en het teken vóór het haakje op een stack op, en begin opnieuw met resultaat 0 en teken +1. Wanneer je een ) tegenkomt, rond je de subexpressie af, vermenigvuldig je die met het opgeslagen teken en tel je die op bij het opgeslagen resultaat.

Behandel elk teken:

Tel aan het einde de laatste sign * num erbij op.

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

De pop-volgorde is belangrijk: het teken is als laatste gepusht, dus wordt als eerste gepopt.

Trace

Expressie: 1-(2+3).

1 - (2 + 3) = -4, dat klopt.

Unaire min

Een minteken aan het begin werkt zonder speciale code. Aan het begin is num 0, dus de eerste - telt sign * 0 op bij het resultaat en zet dan het teken op -1. Hetzelfde geldt na een (: de opgeslagen toestand reset result naar 0 en sign naar +1, dus (-2) wordt op dezelfde manier behandeld.

Complexiteit

• Tijd: O(n), één pass over de string.
• Ruimte: O(n) in het slechtste geval bij diep geneste haakjes, omdat de stack twee waarden per open haakje bevat.

Ik heb deze functie getest op 4.000 willekeurige expressies met geneste haakjes en unaire mintekens, vergeleken met Python's eigen evaluatie, en alles kwam overeen.

Alternatief: recursie

Je kunt ook een recursieve functie schrijven die een expressie parseert en zichzelf aanroept wanneer die een ( tegenkomt. Het leest natuurlijk, maar het risico bestaat dat je de recursielimiet raakt bij diep geneste invoer, dus de stack-versie is veiliger in Python.

Uitbreidingen die interviewers vragen

Randgevallen

Veelgemaakte fouten

1. Elk cijfer als een apart getal behandelen.
2. Vergeten de laatste sign * num aan het einde op te tellen.
3. In de verkeerde volgorde poppen.
4. num niet resetten na een operator.
5. Een minteken aan het begin verkeerd behandelen.

Hoe je het uitlegt in een interview

1. Verduidelijk de toegestane tekens, en of unaire min voorkomt.
2. Zeg dat er geen prioriteitsprobleem is, dus haakjes zijn de enige uitdaging.
3. Beschrijf de drie variabelen en wat een stack opslaat.
4. Loop 1-(2+3) door op het whiteboard.
5. Geef de complexiteit, en noem dan de Calculator II-uitbreiding.

Gerelateerde oefening

Zie onze Big O cheat sheet voor de complexiteitstermen, de AI LeetCode tutor guide, en de coding interview assistant guide. Valid Parentheses en Decode String gebruiken hetzelfde stack-idee.

Vertel je trace hardop terwijl je oefent. Een mock-interviewtranscript laat zien of je het doel van de stack hebt uitgelegd. Volg de regels van de werkgever over AI-tools bij elke live assessment.