APLICACIONES. Notación Polaca y Polaca Inversa. Notación infija A+B C-D E*F G/H Distinción entre (A+B)*C y A+(B*C) Con paréntesis y orden de prelación. Notación Polaca (Jan Lukasiewitz) (Notación prefija) +AB –CD *EF /GH Ejemplo: (A+B)*C [+AB]*C *+ABC A+(B*C) A+[*BC] +A*BC (A+B)/(C-D) [+AB]/[-CD] /+AB-CD Notación Polaca Inversa (Notación Postfija). AB+ CD- EF* GH/ Tampoco se necesitan paréntesis. Un computador normalmente convierte la expresión infija en postfija y después calcula la expresión. Ejemplo : Calculadora HP utiliza operaciones postfijas. Evaluación de expresiones Postfijas. 5* (6+2) -12/4 5* (6+2) -12/4 5*[6,2,+]-[12,4,/] [5,6,2,+,*]-[ 12,4,/] 5,6,2,+,*,12,4,/,-

Programa para la evaluación: En el programa pondremos un valor centinela para saber cuando acaba la expresión. Por ejemplo un paréntesis derecho. ALGORITMO: Encuentra el VALOR de una expresión aritmética P escrita en notación postfija.

1. Añadir un paréntesis derecho “)” al final de P (centinela).

2. Examinar P de izq. A der. Y repetir los pasos 3 y 4 para cada elemento de P hasta que se encuentre el centinela.

3. Si se encuentra un operando, ponerlo en PILA. 4. Si se encuentra un operador ⊗ entonces:

a. Sacar los dos operadores superiores de PILA, donde A es el elemento superior y B el siguiente.

b. Evaluar B ⊗ A. c. Poner el resultado de (b.) en PILA.

5. Fin del condicional de 4. 6. Fin del bucle de 2. 7. Hacer VALOR igual al elemento superior de PILA. 8. Salir.

5,6,2,+,*,12,4,/,-

Símbolo examinado Pila 5 5 6 5,6 2 5,6,2 + 5,8 * 40 12 40,12 4 40,12,4 / 40,3 - 37 ) Resultado

Pasar de notación infija a postfija (O a Prefija en otros casos.

ALGORITMO: POLACA(Q,P). Suponemos que Q es una expresión aritmética escrita en notación infija. Este algoritmo encuentra su expresión postfija P. 1.- Meter "(" en PILA y añadir ")" al final de Q. 2.- Examinar Q de izquierda a derecha y repetir los pasos 3

a 6 para cada elemento de Q hasta que la PILA esté vacia.

3.- Si se encuentra un operando, añadirlo a P. 4.- Si se encuentra paréntesis izquierdo, meterlo en PILA. 5.- Si se encuentra un operador ⊗ entonces: (a) Repetidamente sacar de PILA y añadir a P cada

operador (de la cima de PILA) que tenga la misma precedencia o mayor que ⊗.

(b) Añadir ⊗ a PILA. [FIN de condicional] 6.- Si se encuentra un paréntesis derecho, entonces: (a) Repetidamente sacar de PILA y añadir a P cada

operador (de la cima de PILA) hasta que se encuentre un paréntesis izquierdo.

(b) Eliminar el paréntesis izquierdo (no añadir el paréntesis izquierdo a P).

[Fin de condicional] [Fin del Bucle del Paso 2] 7.- Salir. EJEMPLO: A+(B*C-(D/E↑f)*g)*H A+([BC*]-[DEF↑/]*G)*H A+([BC*]-[DEF↑/G*])*H A+[(BC*DEF↑/G*-H*)] ABC*DEF↑/G*-H*+

SÍMBOLO EXAM. PILA EXPRESIÓN P

A ( A

+ (+ A

( (+( A

B (+( AB

* (+(* AB

C (+(* ABC

- (+(- ABC*

( (+(-( ABC*

D (+(-( ABC*D

/ (+(-(/ ABC*D

E (+(-(/ ABC*DE

↑ (+(-(/↑ ABC*DE

F (+(-(/↑ ABC*DEF

) (+(- ABC*DEF↑/

* (+(-* ABC*DEF↑/

G (+(-* ABC*DEF↑/G

) (+ ABC*DEF↑/G*-

* (+* ABC*DEF↑/G*-

H (+* ABC*DEF↑/G*-H

) ABC*DEF↑/G*-H*+

Evaluar expresiones: X=2, Y=5, Z=X+Y; obtener Z X=2, Y=5; Z=(((Y-1)/X)*(X+Y)) Problemas: - ¿Qué se evalúa primero? -> (paréntesis). - ¿Dónde guardamos resultados intermedios? -> En pilas. El proceso a seguir es tener dos pilas, una para operandos y otra para operadores, para su realización es necesario que esté bien parentizado, ya que, consiste en evaluar la expresión y si encontramos un paréntesis izquierdo no hacemos nada, si es un operando lo pasamos a la pila de operandos y si es un operador a la de operadores, de forma que cuando encontremos un paréntesis derecho, hay que realizar una operación, cuyos operandos y operador se encuentran en las pilas, y así sucesivamente. Si la expresión no está realizada con paréntesis hay que tener órdenes de prelación y el algoritmo es un poco más difícil (Ver Estructuras de Datos en JAVA de Weiss). Utilizamos pilas porque necesitamos albergar resultados intermedios pero no sabemos cuantos. La solución es utilizar pilas.

** Copiar una pila en otra. PROCEDURE Copia(VAR P1:Pila; VAR P2:Pila); VAR e:TipoElemento; BEGIN IF NOT EsVacia(P1) THEN BEGIN Cima(P1,e); Desapilar(P1); Copia(P1,P2); Apilar(P1,e); Apilar(P2,e) END ELSE PilaVacia(P2) END; ** Teniendo una pila ponerla al revés. PROCEDURE Invierte(VAR P1:Pila; VAR P2:Pila); VAR e:TipoElemento; BEGIN IF NOT EsVacia(P1) THEN BEGIN Cima(P1,e); Desapilar(P1); Apilar(P2,e); Invierte(P1,P2); Apilar(P1,e) END END;