Árboles Binarios para Representación de Expresiones Lógicas
Objetivos
Planteamiento del problema
Los árboles binarios pueden ser empleados para representar operaciones lógicas. En este tipo de uso de los árboles, el árbol contendrá en sus hojas (nodos terminales) operandos booleanos (True / False), constantes o variables, mientras que los nodos no terminales del árbol contendrán los operadores lógicos. Por ejemplo, el siguiente árbol representa la expresión "True OR False AND ( NOT True OR False ) XOR True":
La representación arborescente de una expresión permite representar adecuadamente las relaciones de dependencia entre las expresiones simples que forman la expresión total, es decir, qué expresiones son operandos de otras expresiones. Además, el árbol de la expresión no depende de la notación empleada, sino todo lo contrario, es posible cambiar la notación de la expresión sin más que recorrer el árbol con el criterio adecuado (prefijo, infijo o posfijo).
Para poder evaluar la expresión almacenada en el árbol bastará con realizar un recorrido del árbol realizando las operaciones indicas en los nodos no terminales. El criterio de recorrido más apropiado para realizar esta evaluación sería el criterio posfijo. Como se sabe, con este criterio y utilizando una pila como estructura auxiliar se puede calcular fácilmente el valor de la expresión. En nuestro ejemplo el valor obtenido será: True.
Realización de la práctica
En esta práctica se pide manipular un árbol del tipo del expuesto anteriormente. Los operadores a considerar serán: 'OR', 'AND', 'XOR', 'NOT'. La prioridad de los operadores será la que se emplea normalmente esto es: 'NOT' el de mayor prioridad, AND' a continuación y 'OR' y 'XOR' en el último nivel de prioridad. También estará permitido el uso de '(' y ')' con el fin de cambiar la prioridad en la evaluación de la expresión. Resaltar la existencia del operador unario NOT que, a diferencia de los operadores normales, sólo afecta a un operando. En cuanto a los valores de las constantes lógicas consideraremos los valores de True y False. Las tareas a realizar son las siguientes:
"True OR ( True AND ( False OR NOT ( True XOR False ) ) AND True",
en la que cada operador, operando o paréntesis está separado del resto de la expresión por un blanco. Para la generación del árbol que represente la expresión necesitaremos el uso de dos pilas: una que se empleará para ir acumulando los operadores y otra para almacenar las expresiones parciales que vayamos generando. Para la utilización de Pilas se empleará la unidad de manejo de pilas realizada en la práctica 2, realizando los cambios necesarios para contener el tipo de datos requerido en esta práctica. El algoritmo a seguir para la generación del árbol será el siguiente:
1. Si se lee un dato se guarda como árbol en la pila de expresiones.
2. Si se lee un operador hay que analizar la pila de operadores antes de almacenarlo en ella.
2.a. Si en dicha pila hay un operador con prioridad mayor entonces hay que desapilarlo y guardarlo como árbol de expresión en la otra pila. Este árbol tendrá como árbol derecho la primera expresión de la pila y como árbol izquierdo la segunda (Tener en cuanta el caso especial del operador NOT).
2.b. Si la prioridad es menor o igual, o la pila de operadores está vacía, guardaremos el operador en la pila.
2.c. En cuanto a los paréntesis, hay que tener en cuenta que todo '(' se apila en la pila de operadores y todo ')' implica desapilar operadores, según la idea anterior, hasta encontrar el '('. Además, considerar que los paréntesis no son operadores que se deban almacenar en el árbol de expresión.
"True OR ( X AND ( False OR NOT ( True XOR False ) ) AND True",
de manera, que se permita obtener el valor booleano de la expresión lógica para distintos valores de la variable 'X'.
Presentación de la práctica
Se entregarán al profesor tres programas en PASCAL. Uno Uni_Pila.pas con la implementación de las operaciones de PILAS (IniciarPila, VaciaPila, Apilar, Desapilar y CimaPila) y sólo esas operaciones, otro Uni_Arbol.pas con las operaciones de ÁRBOLES (IniciarArbol, VacioArbol, HacerArbol, HijoIzdo, HijoDcho, Informacion y EliminarNodo) y sólo esas operaciones y finalmente un programa principal Expresion.pas con las operaciones necesarias para llevar a termino las tareas planteadas en la práctica.
Se penalizará MUY SEVERAMENTE cualquier referencia en el programa Expresiones.pas a la estructura interna de los árboles y las pilas utilizadas en la práctica.
ENTREGA DE PROGRAMAS: Al finalizar la segunda sesión de prácticas correspondiente.