4.1.2.3 Ejemplo de
Aplicación 03
Ejemplo de utilización de pilas:
Paso de una
expresión en notación infija a notación postfija Asociado con el problema de
las expresiones, ya comentado, estaría el problema de cambiar de notación la
expresión. Cómo pasar de la notación infija empleada durante la escritura del
programa (que es cómoda y habitual para el usuario) a la notación posfija, más
conveniente para automatizar los procesos de cálculo. Para realizar este
proceso, de nuevo resulta adecuada la utilización de una pila.
Para el proceso de traducción de la expresión hay
que tener en cuenta una serie de aspectos: los operandos aparecen en el mismo
orden en la notación infija y en la posfija, con lo que no hay que realizar
ningún tipo de acción específica cuando, al leer la expresión, se detecta un
operando, simplemente proporcionarlo como salida; los operandos; por su parte,
sí que cambian de posición al cambiar la notación. En la notación infija, el
operador se sitúa antes que uno de los operandos, mientras que en la notación
posfija siempre va detrás. Por esa razón, ahora es conveniente almacenar los
operadores, no los operandos, hasta el momento en que halla que proporcionarlos
como salida. Además, hay que tener en cuenta que la entrada de datos es una expresión
en la que los operadores tienen asignadas distintas prioridades, estas
prioridades también se deben tener en cuenta en el momento de la traducción.
El siguiente algoritmo permite traducir una
expresión escrita en notación infija a notación posfija. Para simplificar la
tarea, se ha supuesto que la expresión de entrada no tiene paréntesis (lo que
complicaría ligeramente el proceso) y que tenemos un proceso paralelo que
permite extraer cada uno de los elementos de la expresión (identificadores de
variable, constantes, funciones, etc...):
Algoritmo Infija_A_Posfija
(sin paréntesis)
Entrada
expresion:
cadena
Inicio
Iniciar_Pila ( stack )
Mientras haya
elementos en la expresión hacer
Obtener
el siguiente elemento de la expresión
Si(1) (el
elemento es un operando) entonces
Añadimos
el elemento a la expresión traducida
Sino(1) {* x es operador, entonces se apila pero... *}
fin
← FALSO
{* ...antes de apilar, analizar prioridades de
operadores *}
Mientras(2) ( no Pila_Vacia
( stack ) ) y ( no fin ) hacer
Si(2) (la
prioridad del elemento es menor que la prioridad del
elemento
que está en la cima de la pila) entonces
y ←
Desapilar ( stack )
Añadimos
‘y’ a la expresión traducida
Sino(2)
fin
← CIERTO
Fin_si(2)
Fin_mientras(2)
Apilar (
stack, x )
Fin_si(1)
fin_mientras(1)
{* se ha terminado la expresión, vaciar la pila *}
Mientras(3) ( no Pila_Vacia ( stack ) ) hacer
y ←
Desapilar ( stack )
Añadimos
‘y’ a la expresión traducida
Fin_mientras(3)
Fin
Al igual que hicimos en el ejemplo anterior, el
algoritmo escrito en código C++:
٭
Expresion Infijo2Posfijo (Expresion e)
{
Pila s;
Expresion traduccion;
Elemento token, x;
bool fin;
while (!e.ExpresionVacia () )
{
token = e.SigElemento ();
if (token.EsOperando () )
traduccion.Concatenar (token);
else
{
fin = false;
while ( (!s.PilaVacia () ) && (!fin) )
{
s,CimaPila (x);
if (token.Prioridad () <= x.Prioridad () )
{
s.Desapilar ();
traduccion.Concatenar (x);
}
else
fin = true;
}
s.Apilar (token);
}
}
while (!s.PilaVacia () )
{
s.CimaPila (x);
s.Desapilar ();
traduccion.Concatenar (x);
}
return traduccion;
}
٭