AOJ 1233 Equals are Equals

問題

文字列からなる式が与えられる。
最初の式と、二つ目以降の式が等しいかをyesまたはnoで出力せよ。

制約条件

式の長さ≦80
係数はintの範囲に収まる
指数部は自然数

方針

構文解析した結果をmap<vector<int> >に入れて比較する。

ソースコード

typedef map<vi, ll> E;
E operator*(const E &a, const E &b){
	E res;
	fr(i, a) fr(j, b){
		vi v(26);
		rep(k, 26) v[k] = (i->first)[k] + (j->first)[k];
		res[v] += i->second * j->second;
	}
	return res;
}
E expr(), term(), factor(), primary();
int p, len;
string in, token;
void next(){
	token = "";
	while(p < len && isspace(in[p])) p++;
	if(p < len){
		if(isdigit(in[p])) while(isdigit(in[p])) token += in[p++];
		else token += in[p++];
	}
}
ll number(){
	ll res = 0;
	rep(i, token.size()){
		res *= 10, res += token[i] - '0';
	}
	next();
	return res;
}
E expr(){
	E res;
	do{
		bool plus = token != "-";
		if(!res.empty()) next();
		E t = term();
		if(plus){
			fr(i, t) res[i->first] += i->second;
		}
		else{
			fr(i, t) res[i->first] -= i->second;
		}
	}while(token == "+" || token == "-");
	return res;
}
E term(){
	E res;
	vi v(26);
	res[v] = 1;
	do{
		E f = factor();
		res = res * f;
	}while(!token.empty() && token != "+" && token != "-" && token != ")");
	return res;
}
E factor(){
	E p = primary();
	if(token != "^") return p;
	next();
	ll n = number();
	E res;
	res[vi(26)] = 1;
	rep(i, n) res = res * p;
	return res;
}
E primary(){
	E res;
	if(isdigit(token[0])){
		ll n = number();
		res[vi(26)] = n;
		return res;
	}
	if(isalpha(token[0])){
		vi v(26);
		v[token[0] - 'a'] = 1;
		res[v] = 1;
		next();
		return res;
	}
	next();
	res = expr();
	next();
	return res;
}

E parse(){
	p = 0;
	len = in.size();
	next();
	E e = expr(), f;
	fr(i, e) if(i->second) f[i->first] = i->second;
	return f;
}
int main()
{
	while(getline(cin, in), in != "."){
		E e = parse();
		while(getline(cin, in), in != ".") puts(e == parse() ? "yes" : "no");
		puts(".");
	}
	return 0;
}