Notación Polaca Inversa: Una Alternativa Elegante para Evaluar Expresiones Matemáticas
La Notación Polaca Inversa (NPI) es un método eficiente para evaluar expresiones matemáticas, que se caracteriza por colocar los operadores después de sus operandos. Este enfoque permite omitir los paréntesis, simplificando y clarificando el proceso de cálculo. Aunque al principio pueda parecer diferente, usar la NPI acelera significativamente la ejecución de operaciones, especialmente en sistemas informáticos y calculadoras programables.
Existen numerosas formas de escribir expresiones matemáticas. La más común es la notación infija, donde los operadores se colocan entre los operandos, como en A + B o (C D) - E. Si bien esta notación puede parecernos intuitiva a los humanos, no es necesariamente la solución más óptima para ordenadores y calculadoras. En este artículo, examinaremos una alternativa menos conocida, pero posiblemente más elegante: la Notación Polaca Inversa (NPI), también conocida como notación postfija.
¿Qué es la Notación Polaca Inversa?
La NPI es una notación matemática donde los operadores siguen a sus operandos. En lugar de escribir A + B, en NPI lo denotamos como A B +. Puede parecer inusual a primera vista, pero sus ventajas se hacen evidentes rápidamente.
El concepto de NPI tiene su origen en el matemático polaco Jan Łukasiewicz, quien desarrolló la notación prefija (notación polaca) en la década de 1920, donde los operadores preceden a sus operandos. La notación postfija es una variación de esta, desarrollada posteriormente por el científico informático australiano Charles Hamblin en la década de 1950 para simplificar el procesamiento informático.
¿Por qué es útil la NPI?
Las principales ventajas de la NPI son la eliminación de la ambigüedad y la eficiencia computacional. La notación infija requiere paréntesis para aclarar el orden de las operaciones, y los ordenadores necesitan algoritmos de análisis sintáctico complejos para manejar correctamente la precedencia de los operadores. En la NPI, sin embargo, los paréntesis son innecesarios, y el orden de las operaciones se determina automáticamente por la estructura de la expresión.
Esto fue particularmente crucial para los primeros ordenadores y calculadoras de bolsillo donde los recursos de hardware eran limitados. Las calculadoras que usaban NPI podían realizar cálculos de forma más simple y rápida.
Dato histórico: La notación NPI fue popularizada por primera vez por Hewlett-Packard (HP) en las décadas de 1960 y 1970. La calculadora de escritorio HP-9100A (1968) fue una de las primeras calculadoras disponibles comercialmente en usar NPI. Más tarde, la legendaria HP-35 (1972), la primera calculadora de bolsillo científica, también empleó la NPI, y este método se convirtió en un sello distintivo de las calculadoras profesionales de HP durante mucho tiempo. Las calculadoras NPI eran famosas por sus cálculos rápidos y precisos, y ganaron gran popularidad entre ingenieros, científicos y profesionales financieros.
¿Cómo funciona la NPI?
Veamos un ejemplo de cómo funciona la NPI. Consideremos la expresión infija: (3 + 4) 2 - 5.
Primero, convertimos esto a NPI. Para la conversión, debemos considerar el orden de las operaciones. En este caso, primero realizamos la suma dentro de los paréntesis, luego multiplicamos por dos y finalmente restamos cinco. La expresión NPI será: 3 4 + 2 5 -.
Ahora, veamos cómo evaluar esta expresión NPI usando una pila. Una pila es una estructura de datos en la que se pueden colocar elementos (push) y retirar (pop), siempre sacando primero el último elemento insertado (LIFO - Último en entrar, Primero en salir).
Evaluación paso a paso de la expresión NPI:
3: Leer3. Es un operando, apilarlo en la pila. Estado de la pila:[3]4: Leer4. También un operando, apilarlo en la pila. Estado de la pila:[3, 4]+: Leer el operador+. Desapilar dos operandos de la pila (primero4, luego3). Realizar la suma:3 + 4 = 7. Apilar el resultado (7) de nuevo en la pila. Estado de la pila:[7]2: Leer2. Operando, apilarlo en la pila. Estado de la pila:[7, 2]: Leer el operador. Desapilar dos operandos de la pila (primero2, luego7). Realizar la multiplicación:72 = 14. Apilar el resultado (14) de nuevo en la pila. Estado de la pila:[14]5: Leer5. Operando, apilarlo en la pila. Estado de la pila:[14, 5]-: Leer el operador-. Desapilar dos operandos de la pila (primero5, luego14). Realizar la resta:14 - 5 = 9. Apilar el resultado (9) de nuevo en la pila. Estado de la pila:[9]
Dado que hemos llegado al final de la expresión NPI y solo queda un elemento en la pila, este elemento es el resultado final. Por lo tanto, el valor de la expresión (3 + 4) 2 - 5 evaluada en NPI es 9.
¿Cómo convertir expresiones infijas a NPI?
El algoritmo más común para convertir expresiones infijas a NPI es el algoritmo Shunting-yard, desarrollado por Edsger Dijkstra. Este algoritmo utiliza una pila (para operadores y paréntesis) y una cola de salida (que en la práctica puede ser simplemente una lista) para la conversión.
Pasos del algoritmo Shunting-yard:
- Tokenización: Dividir la expresión infija en tokens (números, operadores, paréntesis).
- Inicialización: Crear una pila vacía para almacenar operadores y una cola de salida vacía para construir la expresión NPI.
- Procesar tokens: Iterar a través de los tokens:
- Número: Si el token es un número, añadirlo a la cola de salida.
- Operador (op1): Si el token es un operador:
- Mientras haya un operador (op2) en el tope de la pila, Y ya sea:
- op2 tiene mayor precedencia que op1, O
- op2 tiene igual precedencia que op1 Y op1 es asociativo por la izquierda (en nuestro ejemplo, todos los operadores son asociativos por la izquierda),
- Desapilar op2 de la pila y añadirlo a la cola de salida.
- Apilar op1 en la pila.
- Mientras haya un operador (op2) en el tope de la pila, Y ya sea:
- Paréntesis izquierdo
(: Apilarlo en la pila. - Paréntesis derecho
):- Mientras el operador en el tope de la pila no sea un paréntesis izquierdo:
- Desapilar el operador de la pila y añadirlo a la cola de salida. (Si la pila se vacía antes de encontrar un paréntesis izquierdo, hay un desajuste).
- Si hay un paréntesis izquierdo en el tope de la pila, desapilarlo de la pila (pero no añadirlo a la cola de salida - los paréntesis no se incluyen en la expresión NPI).
- Si el tope de la pila no es un paréntesis izquierdo después de procesar el paréntesis derecho, entonces los paréntesis no coinciden.
- Mientras el operador en el tope de la pila no sea un paréntesis izquierdo:
- Vaciar la pila: Cuando no haya más tokens para leer, desapilar cualquier operador restante de la pila y añadirlo a la cola de salida.
- Resultado: La cola de salida ahora contiene la expresión NPI.
Precedencia y Asociatividad:
Es importante entender la precedencia y asociatividad de los operadores. El orden habitual de precedencia (de mayor a menor):
- Multiplicación (
), División (/) - Suma (
+), Resta (-)
Las cuatro operaciones aritméticas básicas son asociativas por la izquierda, lo que significa que los operadores con la misma precedencia se evalúan de izquierda a derecha (ej., a - b - c = (a - b) - c).
Ejemplo de conversión de la expresión infija (3 + 4) 2 - 5 a NPI usando el algoritmo Shunting-yard:
| Token | Cola de Salida | Pila de Operadores | Observación |
|---|---|---|---|
( | ( | Paréntesis izquierdo apilado. | |
3 | 3 | ( | Número añadido a la cola de salida. |
+ | 3 | (, + | Operador apilado. |
4 | 3, 4 | (, + | Número añadido a la cola de salida. |
) | 3, 4, + | ( | Paréntesis derecho: desapilar operadores (+) a la cola hasta encontrar paréntesis izquierdo. Desapilar paréntesis izquierdo. |
| 3, 4, + | | Operador apilado (la pila estaba vacía). |
2 | 3, 4, +, 2 | | Número añadido a la cola de salida. |
- | 3, 4, +, 2, | - | Operador: -. |
5 | 3, 4, +, 2, 5 | - | Número añadido a la cola de salida. |
| Fin | 3, 4, +, 2, 5, - | Fin de la entrada: desapilar operadores restantes (-) de la pila a la cola. |
Así, la forma NPI de la expresión infija (3 + 4) 2 - 5 es: 3 4 + 2 * 5 -.
Resumen
La Notación Polaca Inversa es un método elegante y eficiente para escribir y evaluar expresiones matemáticas. Aunque al principio pueda parecer menos intuitiva que la notación infija, la NPI ofrece varias ventajas, particularmente para el procesamiento informático. Elimina la ambigüedad, no requiere paréntesis y puede evaluarse eficientemente utilizando una pila simple. El algoritmo Shunting-yard proporciona un método ampliamente utilizado y eficaz para convertir expresiones infijas a NPI.
Su importancia histórica es innegable, habiendo jugado un papel importante en las primeras calculadoras de bolsillo, y sigue siendo un concepto relevante en la informática actual, utilizado en compiladores y máquinas virtuales. Aunque menos común en el uso diario, la NPI es una herramienta valiosa y una forma de pensar que proporciona una comprensión más profunda de la relación entre las expresiones matemáticas y las operaciones informáticas.