Arbres lògics P63634


Statement
 

pdf   zip   main.cc

thehtml

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...

Public test cases
  • Input

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

    Output

    AND
     OR
      a
      b
     NOT
      c
    ----------
    true
    false
    
  • Input

    NOT(AND(OR(a,b),AND(b,NOT(c))))
    a 
    c a
    b x

    Output

    NOT
     AND
      OR
       a
       b
      AND
       b
       NOT
        c
    ----------
    true
    true
    false
    
  • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python