Expresiones Aritméticas en Notación Postfija (I)

La Notación Polaca Inversa, Notación Posfija o RPN (Reverse Polish Notation) no es más que una forma de representación de expresiones aritméticas. Se trata de una notación que permite omitir los paréntesis en las expresiones, pero manteniendo el orden o prioridad de los distintos operadores y los cálculos se van realizando de forma secuencial en el momento en que se introduce un operador.

Si quieres programar una calculadora, un interprete, un evaluador de expresiones, un compilador, etc., sin duda te resultará muy interesante.

A modo de ejemplo, consideremos la siguiente expresión aritmética simple para obtener su notación en postfijo:

(9 - (5 + 2)) * 3

En primer lugar evaluamos el paréntesis interior, obteniendo la siguiente expresión:

(9 - (52+)) * 3

Ahora evualuamos el paréntesis exterior:

(952+-)

y finalmente el producto:

952+-3*

Con lo que finalmente hemos obtenido la notación posfija 952+-3* correspondiente a la expresión (9 - (5 + 2)) * 3

Ni que decir tiene, que para poder evaluar una expresión en notación postfija, tenemos que recorrerla de izquierda a derecha en busca del primer operador y posteriormente obtener los operandos inmediatamente a su izquierda:

952+-3* => 97-3* => 23* => 6

Como vemos, en el primer paso se llega al operador '+' y se hace la suma de 5+2=7, quedando la expresión como 97-3*. A continuación llegamos al operador resta '-', y hacemos la resta de 9-7=2 con lo que ya tenemos 23*. Y por último nos queda el operador del producto '*' obteniendo el valor 6 como resultado de la expresión.

Desde el punto de vista de la programación y de la estructura de datos necesaria para evaluar una expresión en postfijo, nos bastará con una simple PILA en la que iremos depositando los distintos operandos y en el momento de entrar un operador, lo que haremos será extraer de la pila los operandos correspondientes, aplicar la operación indicada por el operador y guardar el resultado en la pila.

Obviamente si lo que queremos es programar un "conversor" de expresiones algebraicas (en Infijo) a expresiones en Postfijo, podremos emplear una estructura de datos arbórea (AST - Arbol de Sintaxis Abstracta) y haciendo un recorrido del árbol en Postorden. También podríamos hacer uso del "Algoritmo Shunting Yard" inventado por Edsger Dijkstra, sin duda un gran físico y científico en materia computacional, por desgracia falleció en 2002 pero nos dejó un gran legado:

•  Algoritmo de Dijkstra (Solución al problema del camino más corto)
•  Algoritmo Shunting Yard (Notación Polaca Inversa - Postfijo)
•  El Algoritmo del banquero (interbloqueo en Sistemas Operativos)
•  Propuso el problema de la cena de filósofos (Sincronización de procesos en un Sistema Operativo)
•  etc.