AOJ 1012 Operations with Finite Sets

出典

Aizu Programming Contest, University of Aizu, Aizu-Wakamatsu, 7-8 June, 2003

問題概要

各要素が-100以上100以下の整数の集合（最大五つ）と、それを含む集合演算の式が与えられる。集合演算の結果を要素をスペースで区切って出力せよ。
演算結果が空集合の場合は"NULL"と出力せよ。

解法

構文解析+集合演算。集合演算はSTLの演算を使うと楽（ソース参照）

• 結果が空集合の場合にNULLって出力するんじゃなくてnull lineを出力してずっとハマってた……
• 演算子の結合方向が書いてないが全部左結合の模様

以下ソース

vi S[6];
string expr;

vi calc(vi a,vi b,char op)
{
	vi ret(a.size()+b.size());
	vi::iterator it;
	switch(op)
	{
	case 'u':
		it=set_union(all(a),all(b),ret.begin()); break;
	case 'i':
		it=set_intersection(all(a),all(b),ret.begin()); break;
	case 'd':
		it=set_difference(all(a),all(b),ret.begin()); break;
	case 's':
		it=set_symmetric_difference(all(a),all(b),ret.begin()); break;
	}
	ret.erase(it,ret.end());
	return ret;
}

vi eval(int s,int t)
{
	int d=0,p=t-1; char c;
	for(;p>s;p--)
	{
		c=expr[p];
		if(c=='(')d++;
		if(c==')')d--;
		if(d==0&&(c=='u'||c=='i'||c=='d'||c=='s'))break;
	}
	if(p==s)
	{
		if(expr[s]=='(')return eval(s+1,t-1);
		if(expr[s]=='c')return calc(S[5],eval(s+1,t),'d');
		return S[expr[s]-'A'];
	}
	return calc(eval(s,p),eval(p+1,t),c);
}

int main()
{
	char c; int n;
	while(cin>>c>>n)
	{
		rep(i,6)S[i].clear();
		do
		{
			rep(i,n)
			{
				int t; cin>>t;
				S[c-'A'].pb(t);
				S[5].pb(t);
			}
		}while(cin>>c>>n,c!='R');
		
		rep(i,6)
			sort(all(S[i])),S[i].erase(unique(all(S[i])),S[i].end());
		cin>>expr;
		
		vi ans=eval(0,expr.size());
		if(ans.empty())cout<<"NULL"<<endl;
		else rp(i,ans)cout<<ans[i]<<(i==ans.size()-1?"\n":" ");
	}
	return 0;
}