Saltar al contenido

Evaluar tokens en notación posfija

Fácil#stack#expression-evaluation~15 min

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

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

¿Lo que te frena es la idea y no el código? Fundamentos de la pila lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio