A continuación se presentan algunas de las aplicaciones más representativas de una pila, cabe mencionar que esta selección es necesariamente incompleta.
Análisis básico de expresiones.
Considere la siguiente expresión:
Se insta al lector a que sea tan amable de contestar una por una, las siguientes preguntas:
- ¿Es clara?, es decir, ¿se entiende?
- Para valores concretos de x, y, y j, ¿podría evaluarla?
- ¿Puede escribir la misma expresión en una sola línea de texto, como lo haría para un programa?
7 – ( (x * ( (x + y) / (j - 3) ) + y) / (4 – 5/2) )
Observe que la expresión anterior contiene paréntesis, los cuales son indispensables para agrupar de manera apropiada las operaciones involucradas, mientras que la primera representación no los tiene, ya que son innecesarios. Ahora bien, en base a lo anterior considere lo siguiente:
- ¿Cómo saber que la expresión lineal está correctamente balanceada en cuanto a paréntesis se refiere, de tal forma que represente exactamente lo mismo que la expresión original?
- ¿Y si la expresión original fuera más grande y/o más compleja?
Cuya representación “lineal” está dada por:
{x + (y – [a + b]) * c – [ (d + e) ] } / (h – (j – (k – [l - n] ) ) )
Al igual que antes:
- ¿Cómo saber si la expresión lineal está correctamente balanceada en cuanto a símbolos de agrupación se refiere? Note que ahora se han introducido otros símbolos de agrupación de expresiones (corchetes y llaves) además de los paréntesis.
- Adicionalmente, ¿cómo saber que un símbolo de agrupación está cerrando a su correspondiente símbolo de apertura?, es decir, ¿cómo saber que los símbolos de agrupación están correctamente asociados?
Debería resultar claro que es mucho más fácil para las personas comprender expresiones denotadas como en las expresiones originales; sin embargo, las representaciones "lineales" son las que se utilizan en los lenguajes de programación, por lo que se requiere de un mecanismo que verifique de manera automática que una expresión esté bien escrita, al menos en cuanto a símbolos de agrupación se refiere; para ello, considere el siguiente Algoritmo de verificación de balanceo:
valida = true;
p = pila vacía;
while( no sea fin de cadena y la expresion sea válida ){
procesar el siguiente símbolo de la cadena;
if ( símbolo == ‘(’ | | símbolo == ‘[’ | | símbolo == ‘{’ )
p.push(símbolo);
else if ( símbolo == ‘)’ | | símbolo == ‘]’ | | símbolo == ‘}’ ){
if ( p.estaVacia( ) )
valida = false;
else{
char s = p.pop( );
if ( s no es equivalente a símbolo )
valida = false;
}
}
} // while
if ( !p.estaVacia( ) )
valida = false;
if ( valida )
println("La expresión es correcta y está balanceada.”);
else
println("Existe error en los símbolos de agrupación.”);
Algoritmo de verificación de balanceo.
Dada una expresión almacenada en una cadena, el Algoritmo de verificación de balanceo utiliza una pila para realizar la verificación de los símbolos de agrupación que se encuentren en dicha expresión.
Se deja como ejercicio para el lector realizar una implementación de dicho algoritmo, así como la resolución de los aspectos inherentes a la equivalencia de símbolos (vea el Ejercicio 9 de la entrada Ejercicios selectos para pilas Java y C++ respectivamente).
Se deja como ejercicio para el lector realizar una implementación de dicho algoritmo, así como la resolución de los aspectos inherentes a la equivalencia de símbolos (vea el Ejercicio 9 de la entrada Ejercicios selectos para pilas Java y C++ respectivamente).
Notación interfija, postfija y prefija.
Considere la suma de dos números cualesquiera A y B. Aplicar el operador “+” a los operandos A y B y representar la suma como A + B tiene el nombre de representación o notación interfija.
La notación interfija, aunque es la más común, no es la única. Existen al menos otras dos notaciones alternativas para expresar la suma de A y B utilizando los mismos símbolos A, B y +:
El llamado o invocación a una función en un lenguaje de programación gobernado por el paradigma estructurado, como el lenguaje C por ejemplo, utiliza notación prefija (considere por ejemplo la suma de dos números enviados a una función invocada mediante suma(a, b)), ya que el operador (suma) precede a los operandos (a, b).
La notación interfija, aunque es la más común, no es la única. Existen al menos otras dos notaciones alternativas para expresar la suma de A y B utilizando los mismos símbolos A, B y +:
- + A B representación o notación prefija.
- A B + representación o notación postfija.
El llamado o invocación a una función en un lenguaje de programación gobernado por el paradigma estructurado, como el lenguaje C por ejemplo, utiliza notación prefija (considere por ejemplo la suma de dos números enviados a una función invocada mediante suma(a, b)), ya que el operador (suma) precede a los operandos (a, b).
Conversión de interfija a postfija.
Considere la siguiente expresión:
A + B x C
la cual implícitamente indica:
A + (B x C)
Suponga que se desea convertir la expresión anterior a su representación en postfija ¿Cómo proceder?
Los ejemplos siguientes asumen una representación "lineal" de las expresiones. En base a lo anterior, es importante que el lector tenga presente que el proceso de conversión se basa en las reglas de precedencia de los operadores involucrados en la expresión a convertir.
Así, para convertir una expresión de su notación interfija a su notación postfija, se tienen lo siguientes pasos:
Los ejemplos siguientes asumen una representación "lineal" de las expresiones. En base a lo anterior, es importante que el lector tenga presente que el proceso de conversión se basa en las reglas de precedencia de los operadores involucrados en la expresión a convertir.
Así, para convertir una expresión de su notación interfija a su notación postfija, se tienen lo siguientes pasos:
- A + (B x C) forma interfija.
- A + (BC x) se convierte la multiplicación y el nuevo elemento se considera como un solo número (de hecho, después de aplicar el operador el resultado (producto) es en efecto, otro número).
- A (BC x) + se convierte la suma con las mismas consideraciones expuestas en el punto anterior.
- A B C x + se eliminan paréntesis para obtener la representación final en postfija.
Con base en lo anterior, es posible afirmar que las dos reglas que se siguen durante el proceso de conversión a postfija son las siguientes:
- Las operaciones con mayor precedencia se convierten primero. Si existe más de una operación con la misma precedencia, se resolverá primero la que esté más a la izquierda.
- Después de que una parte de la expresión se ha convertido a notación postfija, ésta se considerará como un operando único.
Ejemplo:
Dada la siguiente expresión (note que no es la misma que la expresión anterior):
Dada la siguiente expresión (note que no es la misma que la expresión anterior):
(A + B) x C
convierta dicha expresión a su notación postfija.
En base a lo expuesto con anterioridad, el proceso de solución está dado por los siguientes pasos:
- (A + B) x C forma interfija.
- (A B +) x C se convierte la adición.
- (A B +) C x se convierte la multiplicación.
- A B + C x se eliminan paréntesis: representación postfija.
Las reglas para convertir una expresión de su notación interfija a su notación prefija son idénticas a las de conversión de interfija a postfija. El único cambio a considerar es que ahora el operador se coloca antes de los operandos en lugar de colocarlo después de ellos.
Aspectos a considerar.
Finalmente, respecto a las notaciones prefija y postfija cabe hacer mención de un par de consideraciones:
Aspectos a considerar.
Finalmente, respecto a las notaciones prefija y postfija cabe hacer mención de un par de consideraciones:
- La representación prefija no siempre es una imagen reflejo de la representación postfija.
- El orden de los operadores en las expresiones postfijas determina el orden real de las operaciones al evaluar la expresión, haciendo en consecuencia innecesario el uso de paréntesis.
En la entrada correspondiente a los Ejercicios selectos para pilas Java y C++ respectivamente tendrá la oportunidad de practicar y de ampliar su experiencia al respecto.
Evaluación de expresiones.
Aunque para las personas en general es más fácil y natural comprender las expresiones interfijas (quizá porque en su mayoría así fuimos instruidos y así estamos acostumbrados pero, ¿qué pasaría si desde pequeños, en lugar de haber aprendido a realizar operaciones utilizando notación interfija, se nos hubiera enseñado a realizarlas utilizando notación prefija por ejemplo? ¿Qué sería entonces lo fácil y natural de comprender?), el procesamiento de dichas expresiones por medio de una computadora no es nada sencillo.
Considere lo siguiente: dada una expresión en notación interfija con valores específicos ¿Cómo evaluaría algorítmicamente dicha expresión? Piense y reflexione en ello antes de continuar.
Ahora bien, con valores específicos para una expresión en notación postfija ¿Cómo evaluaría algorítmicamente dicha expresión? Para esto último, considere el siguiente Algoritmo de evaluación de una expresión en notación postfija:
Considere lo siguiente: dada una expresión en notación interfija con valores específicos ¿Cómo evaluaría algorítmicamente dicha expresión? Piense y reflexione en ello antes de continuar.
Ahora bien, con valores específicos para una expresión en notación postfija ¿Cómo evaluaría algorítmicamente dicha expresión? Para esto último, considere el siguiente Algoritmo de evaluación de una expresión en notación postfija:
pilaOperandos = pila vacía;
while(no sea fin de cadena){
símbolo = siguiente carácter de la cadena;
if(símbolo es un operando)
pilaOperandos.push(símbolo);
else{
numero2 = pilaOperandos.pop( );
numero1 = pilaOperandos.pop( );
resultado = numero1 símbolo numero2;
pilaOperandos.push(resultado);
}
}
return pilaOperandos.pop();
Algoritmo de evaluación de una expresión en notación postfija.
La solución propuesta por el Algoritmo de evaluación de una expresión en notación postfija se basa, como es de esperarse, en una pila. Se deja como ejercicio al lector el análisis y comprensión de dicho algoritmo, así como su correspondiente implementación (consulte la entrada correspondiente a Ejercicios selectos para pilas Java y C++ respectivamente para obtener mayor información).
