PKU 2911 Simplified λ-evaluations
http://poj.org/problem?id=2911
簡単なラムダ式を構文解析する問題。
変数の束縛という概念が最初よく分からなくてサンプルが合わなかったのですが、ようやく通せました。
string getch(const string&in,int idx){ int len=0; int arc=0; while(idx+len<SZ(in)){ if(in[idx+len]==')' && arc==0)break; if(in[idx+len]==')')--arc; if(in[idx+len]=='(')++arc; ++len; } return in.substr(idx,len); } string solve(string in){ if(in.find("(L")==string::npos)return in; rep(i,1000){ int L=in.find("(L"); string a=in.substr(0,L); string b=getch(in,L+4); string c=getch(in,L+5+SZ(b)); string d=in.substr(SZ(a)+SZ(b)+SZ(c)+5); //cout<<in<<endl; //cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl; bool bo=false; rep(i,SZ(b)){ if(i && b[i]==in[L+2] && b[i-1]=='L')bo=true; if(b[i]==in[L+2] && !bo)a+=c; else a+=b[i]; } a+=d; in=a; if(in.find("(L")==string::npos)return in; } return "unterminated"; } main(){ string in; while(cin>>in) cout<<solve(in)<<endl; }