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;
}