LeetCode 224 Basic Calculator: soluzione con stack in Python con una traccia

LeetCode 224, Basic Calculator, ti chiede di valutare una stringa che contiene cifre, +, -, parentesi e spazi, senza usare eval. Non ci sono moltiplicazioni né divisioni, quindi non devi gestire la precedenza degli operatori. L'unica difficoltà sono le parentesi, e uno stack di stati salvati le gestisce in modo pulito con una sola passata.

Il problema

Data una stringa s che rappresenta un'espressione con numeri interi non negativi, +, -, (, ) e spazi, restituisci il suo valore. Il segno meno può anche essere un operatore unario, come in -(2 + 3).

Esempi:

L'idea chiave

Scorri da sinistra a destra tenendo traccia di tre cose: il risultato corrente, il segno corrente e il numero che stai costruendo. Quando incontri una (, stai per iniziare una sotto-espressione. Salva il risultato e il segno che precede la parentesi su uno stack, poi riparti da zero con risultato 0 e segno +1. Quando incontri una ), chiudi la sotto-espressione, moltiplicala per il segno salvato e sommala al risultato salvato.

Gestisci ogni carattere:

Alla fine, aggiungi l'ultimo 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

L'ordine di pop è importante: il segno è stato messo sullo stack per ultimo, quindi viene estratto per primo.

Traccia

Espressione: 1-(2+3).

1 - (2 + 3) = -4, che torna.

Meno unario

Un meno iniziale funziona senza codice speciale. All'inizio, num è 0, quindi il primo - aggiunge sign * 0 al risultato, poi imposta il segno a -1. Lo stesso vale dopo una (: lo stato salvato riporta result a 0 e sign a +1, quindi (-2) viene gestito allo stesso modo.

Complessità

• Tempo: O(n), una sola passata sulla stringa.
• Spazio: O(n) nel caso peggiore con parentesi molto annidate, dato che lo stack contiene due valori per ogni parentesi aperta.

Ho testato questa funzione su 4.000 espressioni casuali con parentesi annidate e segni meno unari, confrontandole con la valutazione nativa di Python, e tutte coincidevano.

Alternativa: la ricorsione

Puoi anche scrivere una funzione ricorsiva che analizza un'espressione e chiama se stessa quando incontra una (. Si legge in modo naturale ma rischia di raggiungere il limite di ricorsione su input molto annidati, quindi in Python la versione con lo stack è più sicura.

Estensioni che gli intervistatori chiedono

Casi limite

Errori comuni

1. Trattare ogni cifra come un numero a sé.
2. Dimenticare di aggiungere l'ultimo sign * num alla fine.
3. Estrarre dallo stack nell'ordine sbagliato.
4. Non azzerare num dopo un operatore.
5. Gestire male un meno iniziale.

Come spiegarlo in un colloquio

1. Chiarisci i caratteri ammessi e se compare il meno unario.
2. Di' che non c'è un problema di precedenza, quindi le parentesi sono l'unica difficoltà.
3. Descrivi le tre variabili e cosa salva lo stack.
4. Traccia 1-(2+3) alla lavagna.
5. Fornisci la complessità, poi accenna all'estensione Calculator II.

Esercizi correlati

Consulta il nostro Big O cheat sheet per i termini di complessità, la guida al tutor AI per LeetCode e la guida all'assistente per colloqui di programmazione. Valid Parentheses e Decode String usano la stessa idea di stack.

Racconta la tua traccia ad alta voce mentre ti eserciti. La trascrizione di un colloquio simulato mostra se hai spiegato lo scopo dello stack. Segui le regole del datore di lavoro sugli strumenti di AI in qualsiasi valutazione dal vivo.