== include(page="template/taskheader" task_id="logic") ==

Poveste si cerinta...

Mircea cel Tanar trebuie sa imbunatateasca permanent performantele calculatoarelor pe care le are în gestiune. Se intâmpla cateodata, ca unele componente noi pe care le foloseste sa nu fie compatibile cu vechile calculatoare. Din acest motiv functionarea calculatoarelor „imbunatatite” poate sa nu fie corecta. Pentru a verifica corectitudinea functionarii acestor calculatoare, Mircea isi propune sa le testeze cu  ajutorul unui program care verifica echivalenta unor expresii logice.
Scrieti un program care determina daca doua expresii logice sunt echivalente sau nu.
Fiecare expresie este formata din:
*	variabile, cele 26 de litere mici ale alfabetului englez, de la ’a’ – ’z’;
*	operatori binari |, &, ^ (SAU, SI respectiv SAU EXCLUSIV);
*	operatorul unar ~ (NEGATIE);
*	paranteze rotunde.
Expresiile vor fi evaluate respectand regulile de prioritati ale operatorilor si parantezelor pentru evaluarea expresiilor logice in care intervin ca operanzi bitii 0 şi 1. Prioritatile in ordine descrescatoare sunt: parantezele rotunde ’(’, ’)’, operatorul unar ’~’, operatorii binari in ordine descrescatoare ’&’, ’^’, ’|’.
Doua expresii sunt echivalente daca:
*	contin acelasi set de variabile indiferent de numarul de aparitii a variabilei in expresie;
*	pentru orice set de date de intrare pentru variabile (valori 0, 1) rezultatul obtinut este acelasi.
 

h2. Date de intrare

...

Fisierul de intrare logic.in contine pe primul rand un numar natural n, ce reprezinta numarul testelor ce se vor evalua. Fiecare test reprezinta evaluarea a doua expresii. Pe urmatoarele 2*n linii sunt siruri de caractere ce constituie expresiile. Acestea sunt scrise pe cate o linie fiecare.
 

h2. Date de iesire

...
h2. Restrictii

Fisierul de iesire logic.out va contine n linii, pe fiecare linie k fiind mesajul „egale” sau „diferite” in functie de rezultatul evaluarii expresiilor de pe liniile 2*k si respectiv 2*k+1 din fisierul de intrare.

* $... ≤ ... ≤ ...$
h2. Exemplu

h2. Restrictii

table(example). |_. logic.in |_. logic.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

* $0<n &le; 50$
* n reprezinta numarul de perechi de expresii ce trebuie evaluate.
* O expresie contine cel mult 100 de operatii si maxim 10 variabile.
* O expresie poate avea cel mult 255 caractere. Spatiul nu este separator in interiorul unei expresii.
* Numele unei variabile este un singur caracter, litera mica a alfabetului englez.
* Expresiile date sunt corecte.

h3. Explicatie

h2. Exemplu

...

table(example). |_. logic.in |_. logic.out |_. Explicatie|
| 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)
|diferite
egale
diferite
egale
| Pentru ultimul set de expresii tabelul este:
 
a  b  ~a  a|~a  (a|~a)&(a|~a)&(a|~a) a|b  E
0  0  1    1       1                  0   0
0  1  1    1       1                  1   1
1  0  0    1       1                  1   1
1  1  0    1       1                  1   1
unde E=(a|~a)&(a|~a)&(a|~a)&(a|b)
|

== include(page="template/taskfooter" task_id="logic") ==