Equivalence

#include <cstdio>
#include <stack>
#include <string>
#include <cstdlib>

using namespace std;
typedef long long ll;

const int N(100);
const ll MOD(9999991);

char A[N], B[N];
int val[128];

string postorder(string s){
    string res;
    stack<int> S;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '*'){
            while(not S.empty() and S.top() == '*'){
                res += S.top();
                S.pop();
            }
            S.push(s[i]);
        }else if(s[i] == '+' or s[i] == '-'){
            while(not S.empty() and (S.top() == '+' or S.top() == '-' or S.top() == '*')){
                res += S.top();
                S.pop();
            }
            S.push(s[i]);
        }else if(s[i] == '('){
            S.push('(');
        }else if(s[i] == ')'){
            while(S.top() != '('){
                res += S.top();
                S.pop();
            }
            S.pop();
        }else{
            res += s[i];
        }
    }
    while(not S.empty()){
        res += S.top();
        S.pop();
    }
    return res;
}

ll eval(const string& s){
    stack<ll> S;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '+'){
            ll b = S.top();
            S.pop();
            ll a = S.top();
            S.pop();
            S.push((a + b) % MOD);
        }else if(s[i] == '-'){
            ll b = S.top();
            S.pop();
            ll a = S.top();
            S.pop();
            S.push((a - b + MOD) % MOD);
        }else if(s[i] == '*'){
            ll b = S.top();
            S.pop();
            ll a = S.top();
            S.pop();
            S.push((a * b) % MOD);
        }else if('0' <= s[i] and s[i] <= '9'){
            S.push(s[i] - '0');
        }else{
            S.push(val[s[i]]);
        }
    }
    return S.top() % MOD;
}

string trim(string s){
    string t;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '+' or s[i] == '-' or s[i] == '*' or s[i] == '(' or s[i] == ')')
            t += s[i];
        else if('A' <= s[i] and s[i] <= 'Z')
            t += s[i];
        else if('a' <= s[i] and s[i] <= 'z')
            t += s[i];
        else if('0' <= s[i] and s[i] <= '9')
            t += s[i];
    }
    return t;
}

void prob(){
    gets(A);
    gets(B);
    string AA = postorder(trim(A));
    string BB = postorder(trim(B));
    for(int t = 0; t < 10; ++t){
        for(int i = 'a'; i <= 'z'; ++i) val[i] = rand() % (MOD - 1) + 1;
        for(int i = 'A'; i <= 'Z'; ++i) val[i] = rand() % (MOD - 1) + 1;
        ll a = eval(AA);
        ll b = eval(BB);
        if(a != b){
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}

int main(){
    srand(101);
    int n;
    scanf("%d", &n);
    char tmp[101];
    gets(tmp);
    for(int i = 0; i < n; ++i) prob();
    return 0;
}