Evaluate Reverse Polish Notation
Recibes una expresión aritmética en notación polaca inversa, como una matriz de tokens. Cada operador aparece justo después de sus dos operandos, así que 3 4 + significa 3 + 4 y 3 4 + 2 * significa (3 + 4) * 2, sin paréntesis. Cada token es un entero o uno de los operadores +, -, * y /.
Devuelve el valor de la expresión. La división trunca hacia cero: 7 / 2 es 3 y -7 / 2 es -3.
Función
- tokensstring-array
- los números y operadores de la expresión, en orden
- Devuelveinteger
- el valor de la expresión
Restricciones
1 ≤ tokens.length ≤ 104- Cada token es
+,-,*,/o un entero de-200a200escrito en notación decimal, con un signo menos inicial cuando es negativo. tokenses una expresión válida en notación polaca inversa.- No se produce ninguna división por cero, y todos los valores intermedios y finales son mayores que
-231y menores que231.
Ejemplos
- Entrada
- tokens = ["8", "3", "-", "4", "*"]
- Salida
- 20
- Explicación
-se aplica a 8 y después a 3, en ese orden, así que da 5, no -5. Después,*multiplica ese 5 por 4, lo que da 20.
- Entrada
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Salida
- -6
- Explicación
/usa los dos valores más recientes: 9 dividido entre 3 es 3. Después,-calcula 2 menos 3, que es -1, y*multiplica 6 por -1.
- Entrada
- tokens = ["10", "-7", "2", "/", "+"]
- Salida
- 7
- Explicación
- El token
-7es un número, no un operador. -7 dividido entre 2 es -3.5, que se trunca hacia cero a -3, no a -4, y 10 más -3 es 7.
Para ir más allá
¿Puedes reconstruir la expresión en notación habitual, como (3 + 4) * 2, añadiendo paréntesis solo donde cambien el significado?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Lee los tokens de izquierda a derecha. Cuando encuentres un operador, ¿a qué dos valores se aplica? Fíjate en el orden en que se produjeron esos valores.
Un operador siempre se aplica a los dos valores más recientes que ningún operador haya usado todavía, y su resultado se convierte en un nuevo valor para los operadores que siguen. «El más reciente que todavía no se ha usado» es exactamente lo que te proporciona una pila.
Inserta cada número. Ante un operador, saca primero el operando derecho y después el izquierdo, combínalos en ese orden e inserta el resultado. Cuando se agoten los tokens, la pila contendrá un valor: la respuesta. Asegúrate de que la división trunque hacia cero.
Solución
Cada operador se aplica a los dos valores que lo preceden inmediatamente, y cualquiera de ellos puede ser el resultado de un operador anterior. Así que una pila de valores evalúa la expresión en una sola pasada. Las dificultades son el orden de los operandos para - y /, distinguir el operador - del número -7 y la división con truncamiento.
Colapsa el primer operador y repite
Correcto, pero no termina con las pruebas más grandes
Intuición
Busca el operador situado más a la izquierda. No hay ningún operador antes de él, así que los dos tokens anteriores son números, sus operandos. Sustituye esos tres tokens por su resultado. Los operadores que vienen después ven ese valor donde estaba la parte, así que la expresión conserva su significado. Repite hasta que quede un solo número.
En cada ronda se vuelve a buscar desde el principio. Con 5,000 números seguidos de 4,999 operadores, el primer operador se encuentra aproximadamente a mitad de camino en cada ronda, así que solo las búsquedas leen unos 1.25 × 10^7 tokens.
Algoritmo
- Copia los tokens en una lista que puedas modificar.
- Busca desde el inicio hasta el primer operador, en la posición
k. - Aplícalo a los números en
k-2(izquierda) yk-1(derecha). - Reemplaza los tres tokens en
k-2,k-1ykpor el resultado. - Repite hasta que quede un token y devuélvelo como número.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])Una pasada con una pila de valores
Intuición
Mantén los valores a la izquierda del operador en una pila en lugar de volver a leerlos. Un número se coloca en la pila. Un operador extrae dos valores, los combina y coloca el resultado en la pila, donde espera al siguiente operador como cualquier otro valor. La pila siempre contiene, en orden, los valores de las partes completas leídas hasta el momento, por lo que un operador siempre se aplica a los dos valores superiores. El valor superior es el operando derecho, porque se produjo en último lugar.
En 6 2 9 3 / - *, / extrae 3 y después 9, y coloca 3 en la pila; - extrae 3 y después 2, y coloca -1 en la pila; y * coloca 6 × -1 = -6 en la pila. Cada token se procesa una sola vez: tiempo O(n) y espacio O(n).
Algoritmo
- Empieza con una pila vacía.
- Para cada token que sea un número, apila su valor.
- Para cada operador, desapila el operando derecho y después el izquierdo.
- Calcula
left op right, truncando hacia cero para/, y apila el resultado. - Después del último token, devuelve el único valor de la pila.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
Errores comunes y casos límite
- Intercambiar los operandos. El primer elemento extraído es el operando derecho:
["3", "5", "-"]es -2, y["2", "9", "/"]es 0, no 4. - Identificar los operadores por su primer carácter.
-7empieza con un signo menos, pero es un número, así que compara el token completo. - Redondear hacia abajo en lugar de truncar.
//de Python,/de Ruby,%/%de R ymath.floorde Lua convierten-7 / 2en -4 y-1 / 3en -1. - Imprimir
-0. En JavaScript y Lua,0 * -5yMath.trunc(-1 / 3)dan como resultado cero negativo. Suma 0 al valor final.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de evaluar la notación polaca inversa?
La solución con pila se ejecuta en tiempo O(n) para n tokens: cada número se apila una vez, y cada operador realiza dos extracciones y una inserción. La pila contiene hasta aproximadamente n/2 valores, por lo que el espacio es O(n).
¿Por qué la notación polaca inversa no necesita paréntesis?
En la notación habitual, 3 + 4 * 2 necesita una regla de precedencia o paréntesis para indicar qué operación va primero. En la notación polaca inversa, un operador siempre se aplica a los dos valores que lo preceden inmediatamente, así que el orden de los tokens determina el resultado: 3 4 2 * + es 11 y 3 4 + 2 * es 14.
¿Cómo se divide con truncamiento hacia cero en Python?
Usa int(a / b). El operador // redondea hacia abajo, así que -7 // 2 es -4, mientras que int(-7 / 2) es -3. La división de punto flotante es lo suficientemente precisa para valores de 32 bits. Para enteros más grandes, divide los valores absolutos con // y vuelve a poner el signo.
¿Cómo conviertes una expresión común en notación polaca inversa?
El algoritmo de shunting-yard lo hace en una sola pasada con una pila de operadores. Los números van directamente a la salida. Antes de insertar un operador, mueve a la salida todos los operadores apilados con una precedencia mayor o igual. Un paréntesis de cierre mueve los operadores hacia fuera hasta encontrar su par de apertura. Al final, el resto va a la salida.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def evalRPN(tokens):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumento
tokens = ["8", "3", "-", "4", "*"]
Salida Esperada
20