4.1.2.3 Ejemplo de
Aplicación 02
Ejemplo de utilización de pilas:
Evaluación de expresiones algebraicas
Sabemos que, para evitar ambigüedad y saber en qué
orden se deben evalúar las expresiones, se define en los lenguajes de
programación una prioridad para cada posible operador. Además, si dos
operadores tienen la misma prioridad se evita el conflicto evaluando éstos de
izquierda a derecha. También está permitido el uso de paréntesis para
establecer un orden concreto de evaluación, independientemente de la
precedencia de los operadores. Todos estos condicionamientos son debidos al
tipo de notación empleada, la llamada notación infija, donde los operadores se
sitúan entre los operandos sobre los que actúa. De manera que, según sabemos,
la siguiente expresión:
x ←
A/B-C+D*E-A*C
se evaluaría como sigue:
x ←
( ( (A/B) - C ) + (D*E) ) - (A*C)
El problema es cómo genera el compilador el código
necesario para calcular esta expresión. La solución se facilita si se modifica
el tipo de notación empleada para representar la expresión. Es conveniente
pasar a notación posfija (el operador se sitúa detrás de los operandos sobre
los que actúa) durante el proceso de compilación. Las ventajas de la notación
posfija son varias: no hace falta paréntesis; no hace falta definir prioridad
de operadores; y la evaluación final de la expresión se realiza fácilmente con
un simple recorrido de izquierda a derecha de la expresión.
Siguiendo la notación posfija, la expresión del
ejemplo anterior se podría escribir como:
x ←
A B / C – D E * + A C * -
Para realizar el cálculo de las expresiones en
notación posfija, hay que tener en cuenta que al leerlas de izquierda a
derecha, lo primero que se lee es la información (operandos) y después el tipo
de acción (operador) que se realiza con ella. Por ello, es necesario almacenar
la información leida hasta que se determine que operador hace uso de ella.
Además, los operadores actúan sobre los últimos
operandos leidos. De manera que, conviene recuperar la información en sentido
inverso a como se almacena. Por esa razón, parece natural emplear una pila como
estructura de almacenamiento de información.
El esquema algorítmico para la evaluación de
expresiones dadas en notación posfija consistiría en ir analizando
secuencialmente la expresión. Si se detecta un operando, se inserta en la pila
y si se detecta un operador, éste se evalúa utilizando los operandos necesarios
de la pila y situando, de nuevo, el resultado en la pila, puesto que será un
operando para otro operador posterior. Este proceso es mucho más simple que
intentar la evaluación directa a partir de la expresión en notación infija.
Algoritmo
para evaluar expresiones:
Inicio leer
la expresión
Mientras haya
elementos en la expresión hacer
Obtener
el siguiente elemento de la expresión Si(1)
el elemento es un identificador de operando entonces
Apilar (elemento)
Sino(1) {* es un operador *}
op
← número de operandos del operador
Repetir op
veces
Desapilar y
Almacenar
Fin_repetir
aplicar
el operador sobre los operandos desapilados
Apilar (resultado
de la operación)
Fin_si(1)
Fin_mientras
Si(2) Pila_Vacia entonces
"Error. Demasiados operadores"
Sino(2)
Si(3) la
Pila tiene más de un valor apilado entonces
"Error.
Demasiados operandos"
Sino(3)
Devolver ( Desapilar )
Fin_si(3)
Fin_si(2)
Fin
Este algoritmo plasmado en código C++ sería:
٭
int Evaluar (Expresion exp)
{
Pila s;
int res;
Elemento token, e1_aux, e2_aux;
while (!exp.ExpresionVacia() )
{
token = exp.SigElemento ();
if (token.EsOperando() )
s.Apilar (token);
else
{
s.CimaPila (e1_aux);
s.Desapilar ();
s.CimaPila (e2_aux);
s.Desapilar ();
res = token.Operar (e1_aux, e2_aux);
s.Apilar (res);
}
}
if (s.PilaVacia () )
{
res = 0;
cerr << “Error: Demasiados operadores”;
}
else
{
s.CimaPila (res);
s.Desapilar ();
if (!s.PilaVacia() )
cerr << “Error: Demasiados operandos”;
}
return res;
}