LABORATORIO DE ESTRUCTURAS DE DATOS

PRÀCTICA Nº 5: 2 sessions (Setmanes del 4 al 15 de Maig de 1996)

Arbres Binaris per a la Representació d’Expressions llógiques
Objectius

Utilització i aplicació de l’estructura de dades arbre binari per a la representació i avaluació d’expressions lògiques.

Reutilització de codi (reutilització de la llibreria de funcions sobre Piles).

Plantejament del problema

Els arbres binaris poden ser empleats per a representar operacions lògiques. En este tipus d’aplicació l’arbre contindrà en les seues fulles (nodes terminals) operands booleans (True / False), constans o variables, mentre que els nodes no terminals del arbre contenen els operadors lògics. Per exemple, el següent arbre representa l’expressió "True OR False AND ( NOT True OR False ) XOR True":

La representació arborescent permet representar de manera adequada les relacions de dependència entre les expressions simples que formen l’expressió total, es a dir, quines expressions son operands d’atres expressions. A més a més, l’arbre de l’expressió no depèn de la notació empleada, sinó tot lo contrari, es possible canviar la notació de l’expressió tan sols canviant el criteri de recorregut del arbre (prefix, infix o posfix)

Per a poder avaluar l’expressió emmagatzemada en l’arbre tindrem prou en recórrer l’arbre realitzant les operacions indicades en els node no terminals. El criteri de recorregut mes apropiat per a realitzar esta avaluació serà el criteri posfix. Com ja sabeu amb este criteri i la utilització de una pila auxiliar es pot calcular fàcilment el valor de l’expressió. En el exemple el valor de l’expressió serà: True.

Realització de la pràctica

En esta pràctica es demana manipular un arbre del tipus del descrit. Els operadors a considerar seran: 'OR', 'AND', 'XOR', 'NOT'. La prioritat del operadors serà la que s’empra normalment:: 'NOT' el de major prioritat, ‘AND' a continuació i 'OR' i 'XOR' en l’últim nivell de prioritat. També estarà permitit l’ús de '(' i ')' amb la finalitat de canviar la prioritat en avaluació de l’expressió. Ressaltar l’existència del operador ‘unari’ NOT, que a diferencia dels operadors ‘normals’, tan sols afecta a un operand. En quant als valors de les constants lògiques considerarem els valors de True i False. Les tasques a realitzar son les següents:

Generar l’arbre binari que represente una expressió lògica introduïda pel teclat. Les expressions introduïdes s’emmagatzemaran en una cadena de caràcters. Les cadenes seran del tipus:

"True OR ( True AND ( False OR NOT ( True XOR False ) ) AND True",

en la que cada operador, operand o parèntesi està separat de la resta de expressió per un blanc. Per a la generació del arbre que representa expressió necessitarem dos piles: una que se emprarà per acumular els operadors i un atra per emmagatzemar les expressions parcials que anirem generant. Per a la utilització de Piles s’utilitzarà la unitat de manipulació de piles realitzada en la pràctica 2, realitzant els canvis necessaris per a contindre el tipus de dades requerits en esta pràctica. L’algorisme a seguir per a la generació del arbre és el següent:

1. si es llegís una data s’emmagatzema com a arbre en la pila de expressions.

2. Si es llegís un operador hi a que analitzar la pila de operadors abans de emmagatzemar en ella cap cosa:

2.a. Si en la pila hi a un operador amb prioritat major aleshores hi a que desapilar-lo i emmagatzemar-lo com a arbre en l’atra pila. Este arbre tindrà com arbre dret la primera expressió de la pila expressions i com arbre esquerre la segon (tingueu en conte el cas especial del operador NOT).

2.b. Si la prioritat es menor o igual, o la pila de operadors és buida, emmagatzemarem l’operador en la pila.

2.c En relació als parèntesi, hi a que tindre en conte que tot '(' s’apila en la pila de operadors i tot ')' implica desapilar operadors, segons l’idea anterior, fins trobar el '('. A més a més, considereu que els parèntesi no son operadors que es tinguen emmagatzemar en l’arbre de expressió.

Escriure expressió emmagatzemada en notació prefixa i posfixa.

Realitzar un recorregut del arbre que permitisca obtindre el resultat de avaluació de expressió lògica representada en l’arbre.

Realitzar una extensió del programa anterior que permitisca la inclusió de operands booleans variables. Es a dir, que admitisca expressions del tipus de:

"True OR ( X AND ( False OR NOT ( True XOR False ) ) AND True",

de tal manera, que es puga obtindre el valor de l’expressin lògica per a distints valors de la variable 'X'.

Presentació de la pràctica

Es lliuraran al professor tres programes en PASCAL. Un ‘Uni_Pila.pas’ amb l’implementació de les operacions de PILES (IniciarPila, VaciaPila, Apilar, Desapilar y CimaPila) i tan sols eixes operacions, un atre ‘Uni_Arbol.pas’ amb les operacions d’ARBRES (IniciarArbol, VacioArbol, HacerArbol, HijoIzdo, HijoDcho, Informacion y EliminarNodo) i tan sols eixes operacions finalment un programa principal ‘Expresion.pas’ amb les operacions necessàries per a realitzar les tasques proposades en la pràctica

Se penalitzarà MOLT RIGUROSAMENT qualsevol referència en el programa Expresiones.pas a l’estructura interna dels arbres i les piles utilitzades en la pràctica.

LLIURAMENT DE PROGRAMES: En acabar la segona sessió de pràctiques corresponent.