立命館合宿2012 day1 問題D Dimensional Analysis (AOJ 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; }