Arbres lògics P63634

Considerem arbres lògics on cada node intern correspon a una operació lògica (AND, OR o NOT) i on les fulles corresponen a variables booleanes (paraules en minúscules). Per exemple, l’arbre següent correspon a l’expressió lògica AND(OR(a,b),NOT(c)):

Les expressions lògiques s’escriuen en una línia en forma de funcions completament parantitzades, separant els paràmetres amb comes, amb els operadors en majúscules, i amb les variables en minúscules. Els operadors AND i OR tenen dues subexpressions lògiques; els operadors NOT només una. Aquests són alguns exemples d’expressions lògiques:

AND(OR(a,b),NOT(c)) parell OR(parell,senar) NOT(AND(OR(a,b),AND(b,NOT(c))))

Avaluar un arbre lògic correspon a calcular el valor que conté la seva expressió lògica per a un conjunt de variables certes (la resta de variables es consideren falses). Per exemple, amb el conjunt de variables certes {a}, l’arbre de la figura s’avalua a cert, i amb el conjunt de variables certes {c, a}, l’arbre de la figura s’avalua a fals.

Descarregeu-vos el codi proposat code.cc i completeu-lo per tal que llegeixi una expressió lògica, construeixi el seu arbre, l’escrigui, i escrigui el resultat de la seva avaluació per a diferents conjunts de variables certes (una per línia).

Pistes

• Ja teniu molt de codi escrit, aprofiteu-lo!

• Per tal de convertir un text que conté una expressió lògica a un arbre lògic, primer podeu substituir-li tots els parèntesis i comes per espais. A continuació podeu processar en pre-ordre la seqüència de paraules resultants a través d’un istringstream.

  Per exemple, AND(OR(a,b),NOT(c)) es transforma primer en AND␣OR␣a␣b␣␣NOT␣c␣␣ i, a continuació, es processa la seva seqüència de paraules AND, OR, a, b, NOT, c a través d’un istringstream.

  Al main() teniu un exemple d’ús del istringstream.

• Evidentment, si us calen, podeu afegir noves funcions.

• Cap al final de la funció main() falta un detallet...