Transformacion

Transformación de una expresión infija a postfija

Se parte de una expresión en notación infija que tiene operandos, operadores y puede tener

paréntesis. Los operandos vienen representados por letras, mientras los operadores son éstos:

^ (potenciación), *, /, +, - .

La transformación se realiza utilizando una pila en la que se almacenan los operadores y los

paréntesis izquierdos. La expresión aritmética se lee del teclado y se procesa carácter a carácter.

Los operandos pasan directamente a formar parte de la expresión en postfija, la cual se guarda

en un array. Un operador se mete en la pila si se cumple que:

La pila esta vacía.

• El operador tiene mayor prioridad que el operador cima de la pila.

• El operador tiene igual prioridad que el operador cima de la pila y se trata de la máxima

prioridad.

Si la prioridad es menor o igual, se saca el elemento cima de la pila, se pone la expresión en

postfija y se vuelve a hacer la comparación con el nuevo elemento cima.

El paréntesis izquierdo siempre se mete en la pila; ya en la pila, se les considera de mínima

prioridad para que todo operador que se encuentra dentro del paréntesis entre en la pila. Cuando

se lee un paréntesis derecho, hay que sacar todos los operadores de la pila y ponerlos en la

expresión postfija, hasta llegar a un paréntesis izquierdo, el cual se elimina, ya que los paréntesis

no forman parte de la expresión postfija.

El algoritmo termina cuando no hay más ítems de la expresión origen y la pila está vacía.

Por ejemplo, la expresión a*(b+c-(d/e^f)-g)-h está escrita en notación infija, la expresión    equivalente en postfija se va a ir formando paso a paso:

Expresión en postfija

a Operando a pasa a la expresión postfija; operador * a la pila.

ab Operador ( pasa a la pila; operando b a la expresión.

abc Operador + pasa a la pila; operando c

En este punto, el estado de la pila es:

El siguiente carácter de la expresión, -, tiene igual prioridad que el operador  de la cima (+) y da lugar a:

abc+

abc+d El operador ( se mete en la pila; el operando d a la expresión.

abc+de El operador / pasa a la pila; el operando e a la expresión.

abc+def El operador ^ pasa a la pila; el operando f a la expresión.

El siguiente ítem, ) (paréntesis derecho), produce que se vacíe la pila

hasta un '('. La pila, en este momento, dispone de estos operadores:

abc+def^/ El algoritmo saca operadores de la pila hasta un '(' y da lugar a la pila:

abc+def^/-  El operador – pasa a la pila y, a su vez, se extrae –; el siguiente carácter, el operando g, pasa a la expresión.

abc+def^/-g  El siguiente carácter es ')', por lo que son extraídos de la pila los operadores hasta un (, la pila queda :

abc+def^/-g- El siguiente carácter es el operador -, hace que se saque de la pila el operador * y se meta en la pila el operador –.

abc+def^/-g-* Por último, el operando h pasa directamente a la expresión.

abc+def^/-g-*h Fin de entrada, se vacía la pila pasando los operadores a la expresión:

abc+def^/-g-*h

En la descripción realizada se observa que el paréntesis izquierdo tiene la máxima prioridad

fuera de la pila; es decir, en la notación infija; sin embargo, cuando está dentro de la pila, la

prioridad es mínima. De igual forma, para tratar el hecho de que dos, o más, operadores de

potenciación se evalúan de derecha a izquierda, este operador tendrá mayor prioridad cuando todavía

no esté metido en la pila que cuando esté puesto en ella. Las prioridades son determinadas

según la Tabla 9.1.