Problem 1012 : Operations with Finite Sets

Problem D: Operations with Finite Sets
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1012

• 問題概要

集合の演算を構文解析して出力せよ。
カッコがない場合は基本的に左側から計算していく。

• 解法

かくだけ。
setで集合をもって、それぞれの演算を関数で実装した。

空集合の場合はNULLを出せというのを見逃していた。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

map<char, set<int> > index;


set<int> Uni(const set<int> &F, const set<int> &S){
  set<int> V = S;
  FOR(it, F){
    V.insert(*it);
  } 
  return V;
}

set<int> Inter(set<int> &F, set<int> &S){
  set<int> V;
  FOR(it, F){
    if(S.find(*it) != S.end()){
      V.insert(*it);
    }
  }
  return V;
}

set<int> Diff(const set<int> &F, const set<int> &S){
  set<int> V;
  FOR(it, F){
    if(S.find(*it) == S.end()){
      V.insert(*it);
    }
  }
  return V;
}

set<int> Sym(const set<int> &F, const set<int> &S){
  return Uni(Diff(F, S), Diff(S, F));
}

set<int> Comp(const set<int> &F){
  return Diff(index['U'], F);
}

set<int> parse(string &s, int &pos){
  set<int> F, S;
  if(s[pos] == '('){
    pos++;
    F = parse(s, pos);
  }
  else if(s[pos] == 'c'){
    pos++;
    if(s[pos] == '('){
      pos++;
      F = Comp(parse(s, pos));
    }
    else F = Comp(index[s[pos]]);
  }
  else F = index[s[pos]];
  pos++;
  while(1){
    if(pos >= s.length() || s[pos] == ')'){
      return F;
    }
    char ope = s[pos];
    pos++;
    if(s[pos] == '('){
      pos++;
      S = parse(s, pos);
    }
    else if(s[pos] == 'c'){
      pos++;
      if(s[pos] == '('){
	pos++;
	S = Comp(parse(s, pos));
      }
      else S = Comp(index[s[pos]]);
    } 
    else S = index[s[pos]];
    pos++;
    if(ope == 'u'){
      F = Uni(F, S);
    }
    if(ope == 'i'){
      F = Inter(F, S);
    }
    if(ope == 'd'){
      F = Diff(F, S);
    }
    if(ope == 's'){
      F = Sym(F, S);
    } 
  }
  return F;
}


main(){

  char c;
  int n;
  while(cin >> c >> n){
    index.clear();
    rep(i, n){
      int tmp;
      cin >> tmp;
      index[c].insert(tmp);
      index['U'].insert(tmp);
    }
    while(cin >> c >> n){
      if(c == 'R')break; 
      rep(i, n){
	int tmp;
	cin >> tmp;
	index[c].insert(tmp);
	index['U'].insert(tmp);
      }
    }
    string s;
    cin >> s;
    int pos = 0;
    set<int> ans = parse(s, pos);
    if(ans.size() == 0){
      cout << "NULL" << endl;
      continue;
    }
    vector<int> v;
    FOR(it, ans){
      v.push_back((*it));
    }
    sort(ALL(v));
    FOR(it, v){
      if(it != v.begin()){
	cout << ' ';
      }
       cout << (*it);
    }
    cout <<endl;
  }
}