AOJ : 1012 - Operations with Finite Sets

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1012
集合演算を行うだけの問題.
カッコがない限りは, 左から順番に計算.

アルゴリズム

簡単に構文解析を書きました.
集合演算は, algorithmの中に入ってる集合演算の関数を利用すれば簡単です.
微妙に使い勝手が悪いですが.

プログラム

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;
  }
}