Evaluate Reverse Polish Notation

Q: ¿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 puede contener hasta aproximadamente n/2 valores, así que el espacio es O(n) . Reducir repetidamente el primer operador requiere un tiempo de O(n²) , porque en cada iteración se vuelve a buscar desde el principio.

Q: ¿Por qué la notación polaca inversa no necesita paréntesis?

En la notación ordinaria, 3 + 4 * 2 necesita una regla de precedencia o paréntesis para indicar qué operación se realiza primero. En la notación polaca inversa, un operador siempre se aplica a los dos valores que tiene justo antes, así que el orden de los tokens lo dice todo: 3 4 2 * + es 11 y 3 4 + 2 * es 14. Por eso una sola pila puede evaluarla sin necesidad de mirar hacia delante.

Q: ¿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 bastante exacta aquí porque los valores caben en 32 bits. Para enteros arbitrariamente grandes, divide los valores absolutos con // y vuelve a poner el signo después.

MedioPila

+10

Recibes una expresión aritmética en notación polaca inversa, como una matriz de tokens. En esta notación, 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 necesidad de paréntesis. Cada token es un número entero o uno de los operadores +, -, * y /.

Evalúa la expresión y devuelve su valor. La división conserva solo la parte entera y trunca hacia cero: 7 / 2 es 3 y -7 / 2 es -3.

Función

evalRPN(tokens: string-array) → integer

tokensstring-array: los números y operadores de la expresión, en orden
Devuelveinteger: el valor de la expresión

Restricciones

1 ≤ tokens.length ≤ 10⁴
Cada token es +, -, *, / o un entero de -200 a 200 escrito en formato decimal, con un signo menos inicial cuando es negativo.
tokens es 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 -2³¹ y menores que 2³¹.

Ejemplos

Entrada: tokens = ["8", "3", "-", "4", "*"]
Salida: 20
Explicación: - se aplica a los dos números que aparecen antes en ese orden, 8 y después 3, 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: El primer operador, /, usa los dos valores más recientes: 9 dividido entre 3 es 3. Después, - calcula 2 menos ese 3, que es -1, y * multiplica 6 por -1.

Entrada: tokens = ["10", "-7", "2", "/", "+"]
Salida: 7
Explicación: El token -7 es un número, no un operador. -7 dividido entre 2 es -3.5, que se trunca hacia cero a -3 en lugar de redondearse hacia abajo a -4, y 10 más -3 es 7.

+18 pruebas ocultas al enviar

Para ir más allá

¿Puedes reconstruir la expresión en notación ordinaria, como (3 + 4) * 2, añadiendo paréntesis solo donde cambien el significado?

Solución

La notación polaca inversa no necesita paréntesis porque el orden de los tokens ya determina el orden de las operaciones: cada operador se aplica a los dos valores que tiene justo antes, y cualquiera de esos valores puede ser el resultado de un operador anterior. Una pila de valores evalúa toda la expresión en un único recorrido de izquierda a derecha. Las dificultades están en los detalles: el orden de los operandos para - y /, distinguir el operador - del número -7 y la división que trunca hacia cero.

Contrae el primer operador, repite

Correcto, pero no termina con las pruebas más grandes

Intuición

Así es como lo resolverías en papel. Busca el operador situado más a la izquierda. No hay ningún operador antes de él, así que los dos tokens que están justo antes son números simples y son sus operandos. Calcula el resultado y sustituye esos tres tokens por un número. La expresión ahora es más corta y sigue significando lo mismo. Repite hasta que quede un solo número.

Toma ["6", "2", "9", "3", "/", "-", "*"]. El primer operador es /, así que 9 3 / se convierte en 3: ["6", "2", "3", "-", "*"]. Después, 2 3 - se convierte en -1: ["6", "-1", "*"]. Después, 6 -1 * se convierte en -6, la respuesta.

Es correcto porque cada ronda sustituye una pieza completa a b op por su valor, y los operadores que vienen después ven ese valor exactamente donde estaba la pieza. Es lento porque en cada ronda se vuelve a buscar desde el principio y luego se cierra un hueco en medio del array. Con 5,000 números seguidos de 4,999 operadores, el primer operador queda aproximadamente a mitad de camino durante las 4,999 rondas, así que solo las búsquedas comprueban alrededor de 1.25 × 10^7 tokens. Los números a la izquierda del operador apenas cambian de una ronda a la siguiente, pero en cada ronda se vuelven a leer.

Algoritmo

Copia los tokens en una lista que puedas modificar.
Recorre desde el inicio hasta el primer operador, en la posición k.
Aplícalo a los números en k-2 (izquierda) y k-1 (derecha).
Reemplaza los tres tokens en k-2, k-1 y k por 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

El enfoque de colapso vuelve a leer los números a la izquierda del operador. Guárdalos en una pila. Lee los tokens una sola vez, de izquierda a derecha. Un número se coloca en la pila. Un operador saca los dos valores superiores de la pila, los combina y vuelve a colocar el resultado, donde espera al siguiente operador como cualquier otro valor.

Recorre ["6", "2", "9", "3", "/", "-", "*"]. Los cuatro números se colocan en la pila: [6, 2, 9, 3]. El / saca 3 y después 9 y coloca 9 / 3 = 3: [6, 2, 3]. El - saca 3 y después 2 y coloca 2 - 3 = -1: [6, -1]. El * saca -1 y después 6 y coloca 6 * -1 = -6. Queda un valor, y esa es la respuesta.

Por qué funciona: en todo momento, la pila contiene los valores de las piezas completas leídas hasta ese momento, en orden, y un operador siempre se aplica a las dos últimas. La parte superior de la pila es el operando derecho, porque se produjo en último lugar, así que se saca primero. Si se invierte ese orden, solo se nota con - y /, donde 8 3 - debe dar 5 y no -5.

La división requiere cuidado en algunos lenguajes. La expresión trunca hacia cero, pero // de Python, / de Ruby y %/% de R redondean hacia abajo, lo que convierte -3.5 en -4. Cada número se coloca una vez y cada operador saca dos valores y coloca uno, así que el recorrido toma O(n) de tiempo, y la pila nunca contiene más de n valores.

Algoritmo

Comienza con una pila vacía.
Por cada token que sea un número, apila su valor.
Por 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

El bucle de pila es corto; la mayoría de las respuestas incorrectas se deben al orden de los operandos y a cómo divide un lenguaje.

Intercambiar los operandos. El primer elemento extraído de la pila es el operando derecho: ["3", "5", "-"] es -2, y ["2", "9", "/"] es 0, no 4.
Identificar los operadores por su primer carácter. -7 empieza con un signo menos, pero es un número. Compara el token completo o comprueba que tenga un solo carácter.
Redondear hacia abajo en lugar de truncar. -7 / 2 debe dar -3, y -1 / 3 debe dar 0. // de Python, / de Ruby, %/% de R y math.floor de Lua dan -4 y -1.
Imprimir -0. En JavaScript y Lua todos los números son de punto flotante, así que 0 * -5 y Math.trunc(-1 / 3) dan cero negativo, que se imprime como -0. Suma 0 al valor final para convertirlo en 0.
Leer un número dígito por dígito. Los tokens como 13 y -200 tienen varios caracteres; analiza el token completo.
Suponer que el último token es un operador. Un solo número, como ["7"], es una expresión válida cuyo valor es 7.

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 puede contener hasta aproximadamente n/2 valores, así que el espacio es O(n). Reducir repetidamente el primer operador requiere un tiempo de O(n²), porque en cada iteración se vuelve a buscar desde el principio.

¿Por qué la notación polaca inversa no necesita paréntesis?

En la notación ordinaria, 3 + 4 * 2 necesita una regla de precedencia o paréntesis para indicar qué operación se realiza primero. En la notación polaca inversa, un operador siempre se aplica a los dos valores que tiene justo antes, así que el orden de los tokens lo dice todo: 3 4 2 * + es 11 y 3 4 + 2 * es 14. Por eso una sola pila puede evaluarla sin necesidad de mirar hacia delante.

¿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 bastante exacta aquí porque los valores caben en 32 bits. Para enteros arbitrariamente grandes, divide los valores absolutos con // y vuelve a poner el signo después.

¿Cómo conviertes una expresión común en notación polaca inversa?

El algoritmo de ordenamiento de patio de maniobras lo hace en una sola pasada con una pila de operadores. Los números van directamente a la salida. Antes de apilar un operador, todos los operadores de la pila con precedencia mayor o igual se trasladan a la salida; se apila un paréntesis de apertura, y un paréntesis de cierre traslada operadores a la salida hasta encontrar su correspondiente. Al final, los operadores restantes van a la salida.

Python

def evalRPN(tokens):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tokens = ["8", "3", "-", "4", "*"]

Esperado