PKU 1460 Firefighters
http://poj.org/problem?id=1460
演算子が虫食い状態の式が与えられるので、それが与えられた答えとなることが可能かどうかを求めろというような問題。
演算子全探索して構文解析すればいいようです。
構文解析がまともに書けずに結構WAりました。
入力に変なものが含まれているのかと、オーバーフロー等を検出しようとしてみたのですが、ちゃんと実装すればちゃんと通るような入力なようです。
関数名と、BFN構文との関係は適当です。
char in[10000]; char op[]="+-*/"; vector<int> question; int idx; int num; bool ok; int expr(); int getnum(){ int ret=0; while(in[idx] && isdigit(in[idx]))ret=ret*10+in[idx++]-'0'; return ret; } int fact(){ int ret; if(in[idx]=='('){ ++idx; ret=expr(); }else ret=getnum(); while(in[idx] && (in[idx]=='*' || in[idx]=='/')){ int b; if(in[idx++]=='*'){ if(in[idx]=='('){ ++idx; ret*=expr(); }else ret*=getnum(); }else{ if(in[idx]=='('){ ++idx; b=expr(); }else b=getnum(); if(b==0){ ok=0; return ret; } ret/=b; } } return ret; } int expr(){ int ret=fact(); while(in[idx] && in[idx]!=')'){ if(in[idx++]=='+')ret+=fact(); else ret-=fact(); } ++idx; return ret; } bool dfs(int ne){ if(ne==SZ(question)){ idx=0; ok=true; int ex=expr(); return num==ex && ok; } rep(i,4){ in[question[ne]]=op[i]; if(dfs(ne+1))return true; } return false; } main(){ int t; cin>>t; while(t--){ question.clear(); scanf(" %s %d",in,&num); for(int i=0;in[i];++i) if(in[i]=='?')question.pb(i); if(dfs(0))cout<<"yes"<<endl; else cout<<"no"<<endl; } }