PKU演習問メモ(8/30)

PKU

PKU落ちてて更新できない……

No. 問題名 問題の種類および解法 難易度
2269 Friends 構文解析・集合演算 ★★★☆☆

2269 Friends

問題概要
{ABC}
{ABC}+{DEFG}+{Z}+{}
{ABE}*{ABCD}
{ABCD}-{CZ}
{ABC}+{CDE}*{CEZ}
({ABC}+{CDE})*{CEZ}

のような集合の式が与えられる。これらを計算せよ。
ただし

+
集合の結びを表す
*
集合の交わりを表す
-
集合差を表す

また、演算子は左結合で、優先順位は'*'＞'+' = '-'の順とする。

解法

構文解析苦手ー。
よくわからないが定石にしたがってやればよい（もはや解説ではない


集合の元はアルファベット一文字だったのでビット演算を使うと手軽にできるっぽい。

ソースコード
char str[300];

int eval(int s,int t)
{
	int p=t-1,q,d=0;
	
	for(;p>=s;p--)//項をみる
	{
		if(str[p]=='(')d++;
		if(str[p]==')')d--;
		if(d==0&&(str[p]=='+'||str[p]=='-'))break;
	}
	if(p>=s)//項が複数
	{
		int l=eval(s,p),r=eval(p+1,t);
		if(str[p]=='+')return l|r;
		return l&~r;
	}
	for(p=t-1;p>=s;p--)//因数をみる
	{
		if(str[p]=='(')d++;
		if(str[p]==')')d--;
		if(d==0&&str[p]=='*')break;
	}
	if(p>=s)//因数が複数
	{
		int l=eval(s,p),r=eval(p+1,t);
		return l&r;
	}
	if(str[s]=='(')return eval(s+1,t-1);
	
	int ret=0;
	for(p=s;p<t;p++)if('A'<=str[p]&&str[p]<='Z')ret|=1<<str[p]-'A';
	return ret;
}

int main()
{
	while(gets(str))
	{
		int a=eval(0,strlen(str));
		
		putchar('{');
		rep(i,26)if(1<<i&a)putchar('A'+i);
		putchar('}'); puts("");
	}
	return 0;
}