5872:Equivalence

問題文
https://icpcarchive.ecs.baylor.edu/external/58/5872.pdf

二つの四則演算のみの式a,bが与えられる。a=bであるかどうか判定せよ。

変数の値を乱数で適当に決めて、1000回判定をした。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cctype>
#include<map>

using namespace std;

typedef long long ll;
typedef unsigned int uint;

ll expression(string);
ll term(string);
ll factor(string);
ll number(string);

int now;
map<char,int>mp;

ll expression(string s){
  ll res=term(s);
  for(;;){
    if(s[now]=='+'){
      now++;
      res+=term(s);
    }
    else if(s[now]=='-'){
      now++;
      res-=term(s);
    }
    else break;
  }
  return res;
}

ll term(string s){
  ll res=factor(s);
  for(;;){
    if(s[now]=='*'){
      now++;
      res*=factor(s);
    }
    else break;
  }
  return res;
}

ll factor(string s){
  ll res=number(s);
  if(s[now]=='('){
    now++;
    res+=expression(s);
    now++;
  }
  return res;
}

ll number(string s){
  ll res=0;
  if('a'<=s[now] && s[now]<='z'){res=mp[s[now]]; now++;}
  if('0'<=s[now] && s[now] <= '9'){res=s[now]-'0'; now++;}
  return res;
}

uint xor128(void) { 
  static uint x=123456789;
  static uint y=362436069;
  static uint z=521288629;
  static uint w=88675123; 
  uint t;
  
  t=x^(x<<11);
  x=y;y=z;z=w;
  return w=(w^(w>>19))^(t^(t>>8)); 
}

int main(void){

  int tc;
  cin >> tc;
  cin.ignore();
  string a,b,A,B;
  while(tc--){
    getline(cin,a);
    getline(cin,b);
    A.clear();
    B.clear();
    
    for(int i=0;i<a.size();i++)if(a[i]!=' ')A+=a[i];
    for(int i=0;i<b.size();i++)if(b[i]!=' ')B+=b[i];

    bool fg=false;
    for(int i=0; i<1000; i++){
      for(char c='a';c<='z';c++)mp[c]=xor128();
      for(char c='A';c<='Z';c++)mp[c]=xor128();
      now = 0;
      ll resA=expression(A);
      now=0;
      ll resB=expression(B);
      if(resA!=resB){
	fg = true;
	break;
      }
    }
    if(fg) cout << "NO" << endl;
    else cout << "YES" << endl;
  }
  
  return 0;
}