Evaluar tokens en notación posfija
La misión
Problema
Una calculadora de bolsillo guarda fórmulas en orden posfijo, donde cada operador va después de sus dos operandos, así que “3 4 +” significa 3 + 4 y nunca se necesitan paréntesis. Dada la fórmula como una lista de tokens, cada uno un entero o uno de +, -, * y /, devuelve su valor. La división trunca hacia cero, así que 7 / -2 es -3. La fórmula siempre es válida, tiene entre 1 y 10 000 tokens, nunca divide por cero, y todo valor intermedio cabe en un entero con signo de 32 bits.
Ejemplos
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Por qué: (2 + 1) * 3
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Por qué: 4 + (13 / 5), y 13 / 5 se trunca a 2
Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Por qué: los números negativos como -11 son operandos, no operadores
Pistas
0 / 3
Cuando llega un operador, sus operandos son los dos valores más recientes que todavía no se usaron.
Haz push de los números en una pila. Con un operador, haz pop primero del operando derecho y después del izquierdo, aplica el operador y haz push del resultado.
El orden importa para - y /. El // de Python redondea hacia menos infinito, así que divide los valores absolutos y vuelve a poner el signo tú mismo para truncar hacia cero.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- 1 ≤ tokens.length ≤ 10⁴
- the formula is valid and never divides by zero
- values fit in a 32-bit signed integer
- division truncates toward zero
Solución
En orden posfijo, un operador siempre se aplica a los dos valores más recientes sin usar, que es exactamente lo que guarda el tope de una pila (stack). Los números se apilan; un operador hace pop del operando derecho, luego del izquierdo, y hace push del valor combinado, así que al final el único valor que queda es la respuesta. La única trampa es la división: la división entera de Python redondea -7 // 2 hacia abajo, a -4, así que el cociente se calcula sobre los valores absolutos y después se restaura su signo, lo que trunca hacia cero. Un token es un operador solo si es exactamente uno de los cuatro símbolos, así que “-11” se lee como un número. El tiempo y el espacio son O(n).
def eval_postfix(tokens):
stack = []
for tok in tokens:
if tok not in ("+", "-", "*", "/"):
stack.append(int(tok))
continue
right, left = stack.pop(), stack.pop() # right operand is on top
if tok == "+":
stack.append(left + right)
elif tok == "-":
stack.append(left - right)
elif tok == "*":
stack.append(left * right)
else:
q = abs(left) // abs(right) # truncate toward zero
stack.append(q if (left < 0) == (right < 0) else -q)
return stack[0]
print(eval_postfix(["2", "1", "+", "3", "*"])) # -> 9
print(eval_postfix(["4", "13", "5", "/", "+"])) # -> 6
print(eval_postfix(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # -> 22¿Lo que te frena es la idea y no el código? Fundamentos de la pila lo explica.