Notacion polaca inversa

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
isaac
Posts: 83
Joined: 2 years ago
Gender: None specified

Notacion polaca inversa

Post by isaac » 2 years ago

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.



Post Reply

Return to “Algorithms”