Notacion polaca inversa

[isaac]

Quisiera compartir este metodo de parsear una cadena que contiene una expresion algebraica con el objetivo de buscar su valor no importando lo complicada que sea. Puede ser desde 3+4 hasta ((32 + 4) ^ 2 - 34 * (1 - (53 ^ 3 * 2 - 14 + 2 * 5))). Esta herramienta es la mas potente que he encontrado para hacer este tipo de cosas. Primero hay que tener ciertas condiciones:

1-> Una pila donde se van a guardar los operadores.
2-> Una pila donde se van a consolidar los resultados.

PASOS:

1-> Insertamos en la cola (1), un parentesis abierto '(' y en la cadena uno cerrado ')'.
2-> Hacemos un recorrido y verificamos las siguientes condiciones:
1-> Si es un parentesis abierto, lo insertamos en la primera cola.
2-> Si es un numero, lo insertamos en la segunda cola.
3-> Si es un operador hacemos lo siguiente:
A-> Mientras el operador que esta en el tope de la cola (1) tenga mayor o igual prioridad, hago el paso "CALCULO" y saco ese operador de la pila.
B-> Inserto el operador analizado.
4-> Si es un parentesis cerrado:
A-> Mientras el caracter tope de la pila no sea un parentesis abierto, realizamos el paso "CALCULO" con el operador del tope de la pila y lo eliminamos.
B-> Si ya llegamos al parentesis abierto, lo eliminamos de la cola.

3-> "CALCULO" -> Para efectuar el cálculo, extraemos los dos numeros del tope de la cola (2) en orden b, a y guardamos en su lugar a operador b.
4-> Al final, en el tope de la pila (2) va a quedar el resultado.

NOTA: Vease que el parentesis tiene como precedencia cero para este algoritmo.

Por ejemplo:

3 + 4 * (2 - 4)

Nos queda 3 + 4 * (2 - 4)) (agregamos un parentesis cerrado al final)

Primero nos encontramos con un numero, lo insertamos en (2).

(1) = {'('}
(2) = {3}

Ahora tenemos el operador +, como el operador tope de la pila (1) tiene menor precedencia que este, entonces insertamos el + en (1).

(1) = {'(', '+'}
(2) = {3}

Ahora nos encontramos con el 4 y lo ponemos en (2)

(1) = {'(', '+'}
(2) = {3, 4}

Nos encontramos con el *, pero como el tope de (1) (el cual es '+'), tiene menor prioridad, insertamos el *.

(1) = {'(', '+', '*'}
(2) = {3, 4}

El siguiente es un parentesis abierto, asi que lo insertamos en (1). Aqui no necesitamos comprobar la prioridad de los operadores, cuando es parentesis, va directo a la cola sin mas.

(1) = {'(', '+', '*', '('}
(2) = {3, 4}

Luego viene el 2, el cual ponemos en (2)

(1) = {'(', '+', '*', '('}
(2) = {3, 4, 2}

Llega el - y como es un parentesis el tope, entonces lo ponemos en (1)

(1) = {'(', '+', '*', '(', '-'}
(2) = {3, 4, 2}

Nos encontramos al 4 y lo ponemos en (2)

(1) = {'(', '+', '*', '(', '-'}
(2) = {3, 4, 2, 4}

Viene el parentesis cerrado, el cual se lleva primero al '-', por lo que tenemos que seleccionar los dos numeros tope de la pila (2) de la forma b, a, o sea b=4, a=2 y efectuar la operacion a operador b, lo que equivale a 2 - 4 y lo guardamos en (2). Eliminamos el operador '-' de (1).

(1) = {'(', '+', '*', '('}
(2) = {3, 4, -2}

Vemos que el siguiente operador en el tope de (1) es un parentesis abierto, asi que simplemente lo eliminamos.

(1) = {'(', '+', '*'}
(2) = {3, 4, -2}

Finalmente, aparece el parentesis final que es el encargado de barrer con todos los operadores que quedaron pendientes en el proceso. Comenzamos con *
b = -2 y a = 4. 4 * (-2) = -8

(1) = {'(', '+',}
(2) = {3, -8}

Le sigue el '+', b = -8, a = 3. 3 + (-8) = -5


(1) = {'(',}
(2) = {-5}

Y finalmente eliminamos el parentesis abierto que introdujimos al inicio en (1) y en el tope de (2) nos queda el resultado que es -5.

Como vemos, son solo algunos pasos que hay que tener en cuenta y toma solamente una pasada a la cadena que estemos analizando. Este ejemplo fue para algo trivial, pero se puede incluso hacerlo para que acepte operadores unarios como el '-' delante indicando que es un numero negativo, parsear funciones, trabajar con numeros de mas de un digito y como vemos, la complejidad no importa. Incluso se pueden detectar errores por exceso de operadores o por falta de ellos. Espero que les sirva de algo. En otro momento les mando la implementacion en C++ para que vean como se hace mas o menos.