LeetCode 224 Calculadora Básica: Solución con Pila en Python con un Seguimiento

LeetCode 224, Basic Calculator, te pide evaluar una cadena que contiene dígitos, +, -, paréntesis y espacios, sin usar eval. No hay multiplicación ni división, así que no hay precedencia de operadores que manejar. La única dificultad son los paréntesis, y una pila de estados guardados lo resuelve limpiamente en una sola pasada.

El problema

Dada una cadena s que representa una expresión con enteros no negativos, +, -, (, ) y espacios, devuelve su valor. El signo menos también puede ser un operador unario, como en -(2 + 3).

Ejemplos:

La idea clave

Recorre de izquierda a derecha manteniendo tres cosas: el resultado acumulado, el signo actual y el número que estás construyendo. Cuando llegas a un (, estás a punto de empezar una subexpresión. Guarda el resultado y el signo que precede al paréntesis en una pila, y luego empieza de cero con resultado 0 y signo +1. Cuando llegas a un ), termina la subexpresión, multiplícala por el signo guardado y súmala al resultado guardado.

Maneja cada carácter:

Al final, suma el ú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

El orden de desapilado importa: el signo se apiló al último, así que se desapila primero.

Traza

Expresión: 1-(2+3).

1 - (2 + 3) = -4, lo cual coincide.

Menos unario

Un menos al inicio funciona sin código especial. Al comenzar, num es 0, así que el primer - suma sign * 0 al resultado y luego establece el signo a -1. Lo mismo aplica después de un (: el estado guardado reinicia result a 0 y sign a +1, así que (-2) se maneja de la misma forma.

Complejidad

• Tiempo: O(n), una sola pasada sobre la cadena.
• Espacio: O(n) en el peor caso para paréntesis muy anidados, ya que la pila guarda dos valores por cada paréntesis de apertura.

Probé esta función con 4.000 expresiones aleatorias con paréntesis anidados y signos menos unarios, comparando con la evaluación propia de Python, y todas coincidieron.

Alternativa: recursión

También puedes escribir una función recursiva que parsee una expresión y se llame a sí misma cuando encuentre un (. Se lee de forma natural, pero corre el riesgo de alcanzar el límite de recursión con entradas muy anidadas, así que la versión con pila es más segura en Python.

Extensiones que piden los entrevistadores

Casos límite

Errores comunes

1. Tratar cada dígito como su propio número.
2. Olvidar sumar el último sign * num al final.
3. Desapilar en el orden equivocado.
4. No reiniciar num después de un operador.
5. Manejar mal un menos al inicio.

Cómo explicarlo en una entrevista

1. Aclara los caracteres permitidos y si aparece el menos unario.
2. Di que no hay problema de precedencia, así que los paréntesis son el único desafío.
3. Describe las tres variables y qué guarda una pila.
4. Recorre 1-(2+3) en la pizarra.
5. Da la complejidad y luego menciona la extensión Calculator II.

Práctica relacionada

Consulta nuestra guía rápida de Big O para los términos de complejidad, la guía del tutor de LeetCode con IA y la guía del asistente para entrevistas de programación. Valid Parentheses y Decode String usan la misma idea de pila.

Narra tu traza en voz alta mientras practicas. Una transcripción de entrevista simulada muestra si explicaste el propósito de la pila. Sigue las reglas del empleador sobre herramientas de IA en cualquier evaluación en vivo.