PKU 2246 Matrix Chain Multiplication
http://poj.org/problem?id=2246
行列の掛け算の時に、要素の掛け算は何回行われるかを数えるというような問題。
掛け算できない組み合わせの時はそれを検出する。
構文解析自体はそれほど難しくないほうだと思いました。
map<char,PI> mat; string in; int pos; int ans; bool ok; PI expr(){ PI ret; if(in[pos]=='('){ ++pos; ret=expr(); ++pos; }else ret=mat[in[pos++]]; while(pos<in.size() && in[pos]!=')'){ PI tt; if(in[pos]=='('){ ++pos; tt=expr(); ++pos; }else tt=mat[in[pos++]]; if(ret.S!=tt.F){ ok=false; return tt; } ans+=ret.F*tt.S*ret.S; ret=mp(ret.F,tt.S); } return ret; } main(){ int n; cin>>n; rep(i,n){ char c; int a,b; cin>>c>>a>>b; mat[c]=mp(a,b); } while(cin>>in){ pos=0; ans=0; ok=true; expr(); if(ok)cout<<ans<<endl; else cout<<"error"<<endl; } }