Logic1

#include <stdio.h>
# include <string.h>

# define _fin  "logic.in"
# define _fout "logic.out"

# define maxs  512   // lungimea maxima
# define maxv  20    // numarul de variabile
# define sigma 26    // literele mici ale alfabetului englez


char e1[maxs], e2[maxs];
int  var[maxv], nv, vv[sigma], l1, l2;
int  ec=1, poz;

 ///   var[i] = xi; => xi+'a' este simbolul variabilei i
 ///   nv = numarul de variabile,
 ///   vv = valoarea fiecarei variabile existente


void readf(FILE *fin)
{
    int i;
    int aux[maxs];

# define rem_endl(a) ( a[strlen(a)-1] = '\0' )

    fgets(e1, maxs, fin), rem_endl(e1);
    fgets(e2, maxs, fin), rem_endl(e2);

# undef rem_endl

    for(i=0; i<strlen(e1); i++)
        if ( e1[i] == ' ' )
            memmove( e1+i, e1+i+1, sizeof(int) * ( strlen(e1)-i ) ),
            --i;

    for(i=0; i<strlen(e2); i++)
        if ( e2[i] == ' ' )
            memmove( e2+i, e2+i+1, sizeof(int) * ( strlen(e2)-i ) ),
            --i;
}

void writef(FILE *fout)
{
    fprintf(fout, "%s\n", ec==1 ? "egale" : "diferite" );
}

# define isalpha(x) ( (x) >= 'a' && (x) <= 'z' )

void pre_compute()
{
    int i;
    memset(vv, 0, sizeof(vv));
    memset(var, 0, sizeof(var));
    nv = poz = 0;
    ec = 1;

    l1 = strlen(e1), l2 = strlen(e2);

    for(i=0; i<l1; i++)
        if ( isalpha( e1[i] ) && ! vv[ e1[i] - 'a' ])
            ++vv[ var[ ++nv ] = e1[i] - 'a' ];

    for(i=0; i<l2; i++)
        if ( isalpha( e2[i] ) && vv[ e2[i] - 'a' ] & 1 )
            ++vv[ e2[i] - 'a' ];

    for(i=0; i<sigma; i++)  if ( vv[i] & 1 ) ec = 0;
    // daca o variabila nu se gaseste in ambele expresii
    // cele doua nu sunt echivalente

    memset(vv, 0, sizeof(vv));
}

inline int getlvalue(char ch)   // valoarea logica a variabilei ch | nu
                // se verifica existenta acesteia
{
    return ( vv[ ch - 'a' ] );
}

inline int variable(const char e[])
{
    if ( e[poz] == '~' )
    {
        ++poz;
        return ( !variable(e) );
    }
    else
        return (  getlvalue( e[ poz++ ] ) );
}

int evaluate(const char e[], int l);

int log_and(const char e[], int l)
{   // evaluez o secventa care contine or sau xor
    int v, neg=0;

    while ( e[poz] == '~' && poz < l )
    {
       ++poz, neg = !neg;
    }

    if ( e[poz] == '(' )
    {
        ++poz;  // (
        v = evaluate( e, l );
        if ( e[poz] != ')' )
            ec = -1;
        // nu ar trebui sa se intample daca expresia este corecta
        ++poz;  // )
    }
    else
        v = variable( e );      // valoarea primei variabile

    if ( neg ) v = !v;          // negam NUMAI prima valoare

    while ( e[ poz ] == '&' && poz < l )    // AND are cea mai mare prioritate
        ++poz, v &= log_and( e, l );

    return v;
}

int evaluate(const char e[], int l)
{
    // XOR, OR
    int v = log_and( e, l );

    while ( e[ poz ] == '|' || e[ poz ] == '^' && poz < l )
        if ( e[ poz ] == '|' )
            ++poz, v |= evaluate( e, l );
        else
            ++poz, v ^= evaluate( e, l );

    return v;
}

void solve()
{
    int max, i, j, vi;  // valoarea initiala

    max = ( 1 << nv ) - 1;  // 111...1 de nv ori

# define getbit(a, bit) ( ( (a) >> (bit) ) & 1 )

    // evaluam cele doua expresii cand toate variabilele sunt setate false
    vi = evaluate(e1, l1), poz = 0;
    if ( evaluate(e2, l2) != vi ) ec = 0;

    for(i=1; i<=max && ec==1; i++)
    {
        for(j=0; j<nv; j++)
            vv[ var[j+1] ] = getbit(i, j);

        poz = 0, vi = evaluate(e1, l1);
        poz = 0;
        if ( vi != evaluate(e2, l2) )
        {
           ec = 0, poz = 0;
           evaluate(e2, l2);
        }
    }
}

int main()
{
    int t;
    FILE *fin = fopen(_fin, "r");
    FILE *fout= fopen(_fout,"w");

    for(fscanf(fin, "%d\n", &t); t; --t)
    {
    readf(fin);
    pre_compute();
    solve();
    writef(fout);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}