Mircea cel Tânăr trebuie să îmbunătăţească permanent performanţele calculatoarelor pe care le are în gestiune. Se întâmplă câteodată, ca unele componente noi pe care le foloseşte să nu fie compatibile cu vechile calculatoare. Din acest motiv funcţionarea calculatoarelor „îmbunătăţite” poate să nu fie corectă. Pentru a verifica corectitudinea funcţionării acestor calculatoare, Mircea îşi propune să le testeze cu ajutorul unui program care verifică echivalenţa unor expresii logice.
Cerința
Scrieţi un program care determină dacă două expresii logice sunt echivalente sau nu.
Fiecare expresie este formată din:
- variabile, cele
26
de litere mici ale alfabetului englez, de laa – z
; - operatori binari
&, ^, |
(ŞI, SAU EXCLUSIV respectiv SAU); - operatorul unar
~ (NEGAŢIE)
; - paranteze rotunde.
Expresiile vor fi evaluate respectând regulile de priorităţi ale operatorilor şi parantezelor pentru evaluarea expresiilor logice în care intervin ca operanzi biţii 0
şi 1
. Priorităţile în ordine descrescătoare sunt: parantezele rotunde (, )
, operatorul unar ~
, operatorii binari în ordine descrescătoare &, ^, |
.
Două expresii sunt echivalente dacă:
- conţin acelaşi set de variabile indiferent de numărul de apariţii a variabilei în expresie;
- pentru orice set de date de intrare pentru variabile (valori
0, 1
) rezultatul obţinut este acelaşi. Se daun
numere naturale. Calculați suma lor.
Date de intrare
Fişierul de intrare logic.in
conţine pe primul rând un număr natural n
, ce reprezintă numărul testelor ce se vor evalua. Fiecare test reprezintă evaluarea a două expresii. Pe următoarele 2 * n
linii sunt şiruri de caractere ce constituie expresiile. Acestea sunt scrise pe câte o linie fiecare.
Date de ieșire
Fişierul de ieşire logic.out
va conţine n
linii, pe fiecare linie k
fiind mesajul egale
sau diferite
în funcţie de rezultatul evaluării expresiilor de pe liniile 2*k
şi respectiv 2*k+1
din fişierul de intrare.
Restricții și precizări
0 < n ≤ 50
n
reprezintă numărul de perechi de expresii ce trebuie evaluate.- O expresie conţine cel mult
100
de operaţii şi maxim10
variabile. - O expresie poate avea cel mult
255
caractere. Spaţiul nu este separator în interiorul unei expresii. - Numele unei variabile este un singur caracter, literă mică a alfabetului englez.
- Expresiile date sunt corecte.
Exemplu:
logic.in
4 a&(c|~c) a ~(a|b|c|d) ~a&~b&~c&~d z&b a&b a|b (a|~a)&(a|~a)&(a|~a)&(a|b)
logic.out
diferite egale diferite egale
Explicație
Pentru ultimul set de expresii tabelul este:
unde E
= (a|~a)&(a|~a)&(a|~a)&(a|b)