1233-Equals are Equals

問題概要

二つの数式が等しいか比較せよ

解法

構文解析．
非常にバグを作りやすい問題だった．

実装(C++)

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef map<string,int> expression;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
expression operator+(const expression &a,const expression &b){
	expression res(a);
	FOR(it,b){
		res[it->first]+=it->second;
	}
	return res;
}
expression operator-(const expression &a,const expression &b){
	expression res(a);
	FOR(it,b){
		res[it->first]-=it->second;
	}
	return res;
}
expression operator*(const expression &a,const expression &b){
	expression res;
	FOR(it1,a){
		FOR(it2,b){
			string t=(it1->first)+(it2->first);
			sort(t.begin(),t.end());
			res[t]+=(it1->second)*(it2->second);
		}
	}
	return res;
}
bool operator==(expression a,expression b){
	FOR(it,b){
		if(a[it->first]!=it->second)
			return false;
	}
	return true;
}
expression Expr(const string &s,int &p);
expression Factor(const string &s,int &p);
expression Term(const string &s,int &p);
expression Value(const string &s,int &p);
expression Expr(const string &s,int &p){
	expression res=Factor(s,p);
	while(s[p]=='+'||s[p]=='-'){
		char op=s[p];
		p++;
		expression right=Factor(s,p);
		if(op=='+')res=res+right;
		else res=res-right;
	}
	return res;
}
expression Factor(const string &s,int &p){
	expression res=Term(s,p);
	while(s[p]=='*'){
		p++;
		expression right=Term(s,p);
		res=res*right;
	}
	return res;
}
expression Term(const string &s,int &p){
	expression res=Value(s,p);
	if(s[p]=='^'){
		p++;
		expression right=Value(s,p);
		expression rv=res;
		res=expression();
		res[""]=1;
		REP(i,right[""]){
			res=res*rv;
		}
	}
	return res;
}
expression Value(const string &s,int &p){
	if(s[p]=='('){
		p++;
		expression res=Expr(s,p);
		p++;
		return res;
	}else if(isdigit(s[p])){
		int v=0;
		while(isdigit(s[p])){
			v=v*10+(s[p++]-'0');
		}
		expression res;
		res[""]=v;
		return res;
	}else if(isalpha(s[p])){
		expression res;
		string t;
		t+=s[p];
		res[t]=1;
		p++;
		return res;
	}else{
		exit(-1);
	}
}
string init(string a){
	string res;
	if(a[0]!=' ')res.push_back(a[0]);
	for(int i=1;i<(int)a.size();i++){
		if(isdigit(a[i-1])&&isalpha(a[i])){
			res.push_back('*');
		}else if(isalpha(a[i-1])&&isalnum(a[i])){
			res.push_back('*');
		}else if(isalnum(a[i-1])&&a[i]=='('){
			res.push_back('*');
		}else if(isalnum(a[i])&&a[i-1]==')'){
			res.push_back('*');
		}else if(a[i]=='('&&a[i-1]==')'){
			res.push_back('*');
		}else if(a[i-1]==' '&&a[i]==' ')continue;
		res.push_back(a[i]);
	}
	a="";
	for(int i=0;i<(int)res.size();i++){
		if(res[i]==' '){
			if(i+1<(int)res.size()){
				if(isalnum(res[i-1])&&isalnum(res[i+1])){
					a.push_back('*');
				}else if(isalnum(res[i-1])&&res[i+1]=='('){
					a.push_back('*');
				}else if(isalnum(res[i+1])&&res[i-1]==')'){
					a.push_back('*');
				}else if(res[i-1]==')'&&res[i+1]=='('){
					a.push_back('*');
				}
			}
		}else{
			a.push_back(res[i]);
		}
	}
	return a;
}
ostream& operator<<(ostream &os,const expression &a){
	FOR(it,a){
		os<<it->first<<","<<it->second<<endl;
	}
	return os;
}
int main() {
	string in;
	while(1){
		getline(cin,in);
		if(in==".")break;
		in=init(in);
		int q=0;
		expression left=Expr(in,q);
		while(1){
			string in2;
			getline(cin,in);
			if(in==".")break;
			in=init(in);
			q=0;
			expression right=Expr(in,q);
			if(left==right&&right==left){
				cout<<"yes"<<endl;
			}else{
				cout<<"no"<<endl;
			}

		}
		cout<<"."<<endl;
	}

	return 0;
}