AOJ : 1012 - Operations with Finite Sets
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1012
集合演算を行うだけの問題.
カッコがない限りは, 左から順番に計算.
プログラム
int idx; string s; vector<int> v[128]; vector<int> op(char ch,vector<int> a,vector<int> b=vector<int>()){ vector<int> res(502); vector<int>::iterator it; if(ch == 'u') it = set_union(a.begin(),a.end(),b.begin(),b.end(),res.begin()); if(ch == 'i') it = set_intersection(a.begin(),a.end(),b.begin(),b.end(),res.begin()); if(ch == 'd') it = set_difference(a.begin(),a.end(),b.begin(),b.end(),res.begin()); if(ch == 's') it = set_symmetric_difference(a.begin(),a.end(),b.begin(),b.end(),res.begin()); if(ch == 'c') it = set_difference(v['U'].begin(),v['U'].end(),a.begin(),a.end(),res.begin()); res.resize(it-res.begin()); return res; } vector<int> solve(void){ if(s[idx] == ')'){ idx++; return vector<int>(); } bool flg = false; if(s[idx] == 'c'){ flg = true; idx++; } vector<int> res; if(s[idx] == '('){ idx++; res = solve(); } else{ res = v[s[idx++]]; } if(flg) res = op('c',res); while(idx < s.length() && s[idx] != ')'){ char ch = s[idx++]; flg = false; if(s[idx] == 'c'){ flg = true; idx++; } vector<int> tmp; if(s[idx] == '('){ idx++; tmp = solve(); } else{ tmp = v[s[idx++]]; } if(flg) tmp = op('c',tmp); res = op(ch,res,tmp); } idx++; return res; } int main(void){ while(1){ v['U'].clear(); for(int i=0;i<5;i++) v['A'+i].clear(); while(1){ char name; int n; if(!(cin>>name>>n)) return 0; if(name == 'R') break; v[name] = vector<int>(n); for(int i=0;i<n;i++){ cin>>v[name][i]; } sort(v[name].begin(),v[name].end()); v['U'] = op('u',v[name],v['U']); } cin>>s; idx = 0; vector<int> ans = solve(); if(ans.empty()){ cout<<"NULL\n"; continue; } for(int i=0;i<ans.size()-1;i++){ cout<<ans[i]<<" "; } cout<<ans[ans.size()-1]<<endl; } }