LeetCode 224 Calculadora Básica: Solução com Pilha em Python com uma Execução Passo a Passo

O LeetCode 224, Basic Calculator, pede que você avalie uma string contendo dígitos, +, -, parênteses e espaços, sem usar eval. Não há multiplicação nem divisão, então não há precedência de operadores para tratar. A única dificuldade são os parênteses, e uma pilha de estados salvos resolve isso de forma limpa em uma única passada.

O problema

Dada uma string s que representa uma expressão com inteiros não negativos, +, -, (, ) e espaços, retorne seu valor. O sinal de menos também pode ser um operador unário, como em -(2 + 3).

Exemplos:

A ideia central

Percorra da esquerda para a direita mantendo três coisas: o resultado acumulado, o sinal atual e o número sendo construído. Quando você chega a um (, está prestes a iniciar uma subexpressão. Salve o resultado e o sinal à frente do parêntese em uma pilha, depois comece do zero com resultado 0 e sinal +1. Quando você chega a um ), finalize a subexpressão, multiplique-a pelo sinal salvo e some ao resultado salvo.

Trate cada caractere:

No final, some o último 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

A ordem do desempilhamento importa: o sinal foi empilhado por último, então é desempilhado primeiro.

Traço de execução

Expressão: 1-(2+3).

1 - (2 + 3) = -4, o que confere.

Menos unário

Um menos no início funciona sem código especial. No começo, num é 0, então o primeiro - soma sign * 0 ao resultado, depois define o sinal como -1. O mesmo vale depois de um (: o estado salvo reinicia result para 0 e sign para +1, então (-2) é tratado da mesma forma.

Complexidade

• Tempo: O(n), uma passada pela string.
• Espaço: O(n) no pior caso para parênteses profundamente aninhados, já que a pilha guarda dois valores por parêntese aberto.

Testei essa função em 4.000 expressões aleatórias com parênteses aninhados e sinais de menos unário, comparando com a avaliação do próprio Python, e todas bateram.

Alternativa: recursão

Você também pode escrever uma função recursiva que analisa uma expressão e chama a si mesma quando encontra (. Ela é natural de ler, mas corre o risco de estourar o limite de recursão em entradas profundamente aninhadas, então a versão com pilha é mais segura em Python.

Extensões que os entrevistadores pedem

Casos extremos

Erros comuns

1. Tratar cada dígito como um número próprio.
2. Esquecer de somar o último sign * num no final.
3. Desempilhar na ordem errada.
4. Não reiniciar num depois de um operador.
5. Tratar mal um menos no início.

Como explicar isso em uma entrevista

1. Esclareça os caracteres permitidos e se o menos unário aparece.
2. Diga que não há problema de precedência, então os parênteses são o único desafio.
3. Descreva as três variáveis e o que a pilha salva.
4. Percorra 1-(2+3) no quadro branco.
5. Dê a complexidade, depois mencione a extensão Calculator II.

Prática relacionada

Veja nosso Big O cheat sheet para os termos de complexidade, o guia de tutor de LeetCode com IA e o guia de assistente de entrevista de programação. Valid Parentheses e Decode String usam a mesma ideia de pilha.

Narre seu traço em voz alta enquanto pratica. Uma transcrição de entrevista simulada mostra se você explicou o propósito da pilha. Siga as regras da empresa sobre ferramentas de IA em qualquer avaliação ao vivo.