Algoritmo Para Analizar Expresiones Con Pilas

La evaluaci´n de expresiones algebraicas utilizando pilas se realiza en dos
o
fases: 1) se transforma la expresi´n en notaci´n infija a posfija y 2) se eval´a
oo
u
la expresi´n en posfija. Como precondici´n de los algoritmos supondremos que
o
o
las expresiones est´n bien formadas.
a
Conversi´n de una expresi´ninfija a posfija
o
o
1. Repetir hasta que no haya caracteres en la expresi´n de entrada:
o
a ) Leer un car´cter de la expresi´n.
a
o
b ) Si es un operando secoloca en la expresi´n posfija de salida
o
c ) Si es un operador:
1) Si la pila est´ vac´ se coloca en la pila
a
ıa,
2) Si la pila no est´ vac´
a
ıa:
Si tienemayor prioridad que el de la cima, se coloca en la pila.
Si tiene menor o igual prioridad que el de la cima de la pila, se
saca el operador de la cima y se colocaen la expresi´n posfija
o
de salida. Volver a c.
d ) Si es un par´ntesis:
e
1) Si es izquierdo se mete en la pila
2) Si es derecho se sacan y se colocan enla expresi´n posfija de
o
salida todos los operadores de la pila hasta llegar a un par´ntesis
e
izquierdo, que se elimina.
2. Si quedan elementos en la pilapasarlos a la expresi´n posfija de salida
o

Evaluaci´n de una expresi´n posfija
o
o
1. Inicializar la pila
2. Repetir hasta que no haya caracteres en laexpresi´n a evaluar:
o
a ) Obtener el siguiente ´
ıtem de la expresi´n
o
b ) Si es un operando se mete en la pila
c ) Si es un operador,
Sacar los dos elementossuperiores de la pila
Aplicar el operador a estos dos valores
Meter el resultado en la pila
3. Obtener el valor de la expresi´n de la cima de la pila
o