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) de prelación.

Con paréntesis y orden

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. 2.

3. 4.

5. 6. 7. 8.

Añadir un paréntesis derecho “)” al final de P (centinela). Examinar P de izq. A der. Y repetir los pasos 3 y 4 para cada elemento de P hasta que se encuentre el centinela. Si se encuentra un operando, ponerlo en PILA. 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. Fin del condicional de 4. Fin del bucle de 2. Hacer VALOR igual al elemento superior de PILA. Salir.

5,6,2,+,*,12,4,/,Símbolo examinado 5 6 2 + * 12 4 / )

Pila 5 5,6 5,6,2 5,8 40 40,12 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;