POJ 1686 Lazy Math Instructor
問題文
二つの式が与えられる。
式は、変数または数字と、足し算、引き算、掛け算からなる。
二つの式が恒等であるかどうかを判定せよ。
制約条件
式の文字数≦80
式中には空白またはタブが任意に入る
式の係数は16bitに収まる
方針
構文解析+文字式の計算。
文字式はmap<string,int>にそれぞれの係数を入れる(定数項はキーが空白文字列)という愚直なことをしたが、0msで通った。
文字式はどういうデータ構造にするのが良いのだろう。
ソースコード
typedef map<string,int> mat; mat operator+(const mat &a,const mat &b){ mat res=a; fr(i,b){ res[i->first]+=i->second; if(res[i->first]==0)res.erase(i->first); } return res; } mat operator-(const mat &a,const mat &b){ mat res=a; fr(i,b){ res[i->first]-=i->second; if(res[i->first]==0)res.erase(i->first); } return res; } mat operator*(const mat &a,const mat &b){ mat res; if(a.size()==0||b.size()==0)return res; fr(i,a)fr(j,b){ string str=i->first+j->first; sort(all(str)); res[str]+=i->second*j->second; } return res; } char in[100],tmp[100]; mat parse(int l,int r){ int i=r-1,d=0; for(;i>=l;i--){ if(in[i]==')')d++; else if(in[i]=='(')d--; if(d==0&&(in[i]=='+'||in[i]=='-'))break; } if(i>=l){ mat a=parse(l,i), b=parse(i+1,r); return in[i]=='+'?a+b:a-b; } i=r-1; d=0; for(;i>=l;i--){ if(in[i]==')')d++; else if(in[i]=='(')d--; if(d==0&&in[i]=='*')break; } if(i>=l){ mat a=parse(l,i), b=parse(i+1,r); return a*b; } if(in[l]=='(')return parse(l+1,r-1); mat res,str; if(isalpha(in[l])){ string str(1,in[l]); res[str]=1; return res; } int num=0; for(i=r-1;i>=l;i--)num*=10, num+=in[i]-'0'; if(num!=0)res[""]=num; return res; } int main() { int n; scanf("%d ",&n); while(n--){ gets(tmp); int len=0; for(int i=0;tmp[i];i++)if(!isspace(tmp[i]))in[len++]=tmp[i]; mat A=parse(0,len); gets(tmp); len=0; for(int i=0;tmp[i];i++)if(!isspace(tmp[i]))in[len++]=tmp[i]; mat B=parse(0,len); puts(A==B?"YES":"NO"); } return 0; }