Notacion Infija-posfija Moo Mex

Instituto Tecnológico Superior de Escarcega Carrera: Ingeniería en sistemas Computacionales. Prof.: Ing. francisco salvador Ballina. Tema: algoritmo de conversión de notación infija-posfija. integrantes: Isai Cuj Catzin. Rolando Lopez Tzab. Cindy Camara martinez. Ramiro A. Magaña Rodriguez.

Conversión de notación infija-posfija • Tópicos selectos de programación

EXPRESIONES • Una expresión aritmética: – Conjunto de operadores, variables y paréntesis. Ejemplo: • A+B • Esta forma de escribir las expresiones: NOTACION INFIJA • El operador siempre va en medio de los operandos

• En una expresión, las operaciones se “ejecutan” en un cierto orden – A+B*C no es igual que (A+B)*C – Cada operador tiene su nivel de precedencia, recordemos: • • • •

Paréntesis : () Potencia : ^ Multiplicación/división: Suma/Resta : +,-*

Mayor prioridad *,/ Menor Prioridad

A+B*C

NOTACIONES 

Agrupar como establece la precedencia 

• La notación infija es la mas popular • No es la única forma, hay dos mas



• +AB Aquí el operador va antes que los operandos

• No son nada difíciles, pero – Siempre tener en cuenta la precedencia de los operadores

• Ejemplo. Pasar a postfija las siguientes expresiones:



 

(A+B)*

(A+B)*C

Convertir operación por operación La de mayor precedencia primero 



(AB+)*C

La que le sigue en precedencia 



A(BC*)+

Remover Paréntesis C  ABC*+ Agrupar como establece la precedencia 



A+(BC*)

La que le sigue en precedencia 



Ya no se necesitan paréntesis En postfija, el orden de los operadores es el verdadero orden de ejecución

La de mayor precedencia primero 

– NOTACION POSFIJA(POLACA INVERSA) • AB+ Aquí el operador va después que los operandos

Convertir operación por operación 

– NOTACION PREFIJA(POLACA)

A+(B*C)

(AB+)C*

Remover Paréntesis

EVALUACION DE EXPRESIONES POSFIJAS • Dadas – – – – –

AB+C* ABC*+ Evaluelas, cuando A = 3, B = 4 y C = 5 La primera, resultado : 35 La segunda, resultado: 23

• Que algoritmo siguió para evaluar estas expresiones? ABC*+ A20+ AB+C* 7C* A+B -> 7 7*C -> 35

B*C -> 20 -> 20+A 23

EVALUACION: ALGORITMO Podría ser un una • Con lo anterior, ya tenemos una idea de pilaque hacer

– Deberíamos poder “recordar” c/operando de la2 veces Pop expresion – Si encontramos un operador • Los dos últimos operandos recordados son los usados y del Push “olvidados” resultado en la pila • El resultado de la operación, debe ser también “recordado”

– Así, hastaABC*+ C * B +A que la expresión termine C B C*B A

EN PSEUDOCODIGO Pila s; PilaVacia(s); while(no hayamos revisados toda la expresion) { simbolo = siguiente elemento if(simbolo es un operando) Push(s,simbolo); else{ operando1 = Pop(s); operando2 = Pop(s); valor = resultado de operación simbolo entre operando1 y operando2 Push(s,valor); } } return(Pop(s));

CONVERSION DE INFIJA A POSFIJA El operador de mayor precedencia es el primero en aparecer en la expresión

A es un operando, es añadido directamente a la nueva expresión en postfija

A+B*CD

A B C*+ D -

El operador de mayor precedencia en la expresión será el primero en aparecer en la conversión

con el continuar. de Pero aun no podemos *Comparado Es un operador. Si mayor se + es un operador, Aquí terminamos de revisar prioridad hastaelahora(el Seguimos comparando el – con el *), de compara con ultimo pero, hasta lo que la expresión, símbolo por el prioridad – no tiene mayor hastamayor ahora, el +. recordado, el * tiene símbolo. vamos revisando, no esque Como el – no prioridad. tiene mayor prioridad mayor prioridad. Pero Ensi lapodemos pila, quedan el prioridad, Ahora decir,aun elde +, elmayor + ya puede ser añadido aque la no sabemos si tiene operadores. el *mejor, es elComo operador de mas mayor guardarlo expresion. ya no queda en la Todos seprioridad sacan y se añaden “la” mayor prioridad pila, a la nueva expresión de todos aun. Mejor Podemos añadir el *ahora, a la el El – es definitivamente hasta Así termina la conversión expresion, y denueva “mayor prioridad”, debemos guardarlo “olvidarnos” recordarlo de el

ABC*+D-

* + -

CONVERSION: ALGORITMO • •

Cada símbolo de la expresión es revisado Si el símbolo es un operando, – Se añade a la expresión

•

Si el símbolo es un operador – El símbolo es evaluado con respecto a su prioridad – Si tiene mayor prioridad que el ultimo operador almacenado • Aun no se puede decir nada, y se recuerda, es decir, se almacena en un pila

– Si tiene menor prioridad que el ultimo operador almacenado • Quiere decir, que el ultimo operador almacenado es el de mayor prioridad sin lugar a dudas • El ultimo operador almacenado, se saca y se añade a la nueva expresión • Esto sigue hasta que el operador que estamos revisando sea el de mayor prioridad de todos los almacenados en la pila

•

Una vez revisados todos los símbolos de la expresión – Si hay algo almacenado en la pila, se saca y se añade a la nueva expresión

EN PSEUDOCODIGO Pila s; PilaVacia(&s); while(no termine la expresion en infija) { simbolo = siguiente carácter de entrada; if(simbolo es un operando) añadir simbolo a la nueva expresion posfija else{ while(simbolo tenga menor o igual precedencia que el tope de la pila) { simb_tope = pop(s); añadir simb_tope a la nueva exp. } push(s,simbolo) } } /*le da salida a los operadores restantes*/ while(!EstaVacia(s)){ simb_tope = pop(s); añadir simb_tope a la nueva exp. posfija }

Y CON PARENTESIS • Lo anterior, es valido para conversión de expresiones sin paréntesis • Para resolver este problema, podemos seguir las siguientes reglas: – Los paréntesis izquierdos ( • Siempre van a ser añadidos a la pila, pase lo que pase

– Los paréntesis derechos ) • Significa que un ambiente de () ha sido terminado, • Todos los operadores de la pila, se sacan, hasta encontrar un (

CON PARENTESIS: ALGORITMO Pila s; PilaVacia(s); while(no termine la expresion en infija){ simbolo = siguiente carácter de entrada; if(simbolo es un operando) añadir simbolo a la nueva expresion posfija else{ if(simbolo == ‘)’){ while(TRUE){ simb_tope = pop(s); if (simb_tope == ‘)’ || EstaVacia(s)) break; añadir simb_tope a la nueva exp. } } else if(simbolo != ‘(‘){ while(simbolo tenga menor o igual precedencia que el tope de la pila) simb_tope = pop(s); añadir simb_tope a la nueva exp. } } push(s,simbolo) } } /*le da salida a los operadores restantes*/ while(!EstaVacia(s)){ simb_tope = pop(s); añadir simb_tope a la nueva exp. posfija }