立命館合宿2012 day1 問題D Dimensional Analysis (AOJ 1087)

問題

日本語なので本文参照(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1087

制約条件

n≦5
m≦10
p≦15
-10≦dij≦10

方針

構文解析する。特に工夫は必要ない。

ソースコード

int n,m,p;
string name[10], in;
vi d[10];
map<string,vi> ntod, v;

vi rec(int l,int r){
	int d=0, i;
	for(i=r-1;i>=l;i--){
		if(in[i]==')')d++;
		if(in[i]=='(')d--;
		if(d==0&&(in[i]=='+'||in[i]=='-'))break;
	}
	if(i>=l){
		vi a=rec(l,i), b=rec(i+1,r);
		if(a!=b)return vi(0);
		return a;
	}
	for(i=r-1;i>=l;i--){
		if(in[i]==')')d++;
		if(in[i]=='(')d--;
		if(d==0&&(in[i]=='*'||in[i]=='/'))break;
	}
	if(i>=l){
		vi a=rec(l,i), b=rec(i+1,r);
		if(a.size()!=b.size())return vi(0);
		rep(j,a.size())a[j]+=in[i]=='*'?b[j]:-b[j];
		return a;
	}
	if(in[l]=='('&&in[r-1]==')')return rec(l+1,r-1);
	return v[in.substr(l,r-l)];
}

int main(){
	while(cin>>n>>m>>p,n){
		v.clear();
		ntod.clear();
		rep(i,m){
			cin>>name[i];
			d[i].clear(); d[i].resize(n);
			rep(j,n)cin>>d[i][j];
			ntod[name[i]]=d[i];
		}
		cin>>in;
		
		rep(i,p){
			string nm, dim;
			cin>>nm>>dim;
			rep(j,m)if(dim==name[j])v[nm]=d[j];
		}
		vi ans=rec(0,in.size());
		bool ok=0;
		if(ans.empty())cout<<"error"<<endl;
		else{
			for(int i=m-1;i>=0;i--)if(d[i]==ans){
				cout<<name[i]<<endl;
				ok=1; break;
			}
			if(!ok)cout<<"undefined"<<endl;
		}
	}
	return 0;
}