1466.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1466 on 2005-11-11 at 00:46:44 */ 
#include <cstdio>

const int L_MAX = 256;

char line[L_MAX];
char *l;

int buildSet();
int prior(char);
int compute(int, char, int);

int main()
{
	int n, i;

	while(gets(line) != NULL) {
		l = line;
		n = buildSet();
		putchar('{');
		for(i = 0; n != 0; i++) {
			if(n % 2 != 0) {
				putchar(i + 'A');
			}
			n >>= 1;
		}
		printf("}\n");
	}
	
	return 0;
}

int buildSet()
{
	int n, ntop = 0, otop = 0;
	int nstack[L_MAX], a, b;
	char ostack[L_MAX];
	
	while(l[0] != 0 && l[0] != ')') {
		if(l[0] == '(') {
			l++;
			nstack[ntop++] = buildSet();
		} else if(l[0] == '{') {
			l++;
			n = 0;
			for(; l[0] != '}'; l++) {
				n |= 1 << l[0] - 'A';
			}
			nstack[ntop++] = n;
			l++;
		} else {
			while(otop > 0 && prior(l[0]) <= prior(ostack[otop-1])) {
				a = nstack[--ntop];
				b = nstack[--ntop];
				nstack[ntop++] = compute(b, ostack[--otop], a);
			}
			ostack[otop++] = l[0];
			l++;
		}
	}
	l++;
	while(otop > 0) {
		a = nstack[--ntop];
		b = nstack[--ntop];
		nstack[ntop++] = compute(b, ostack[--otop], a);
	}
	
	return nstack[0];
}
int prior(char c)
{
	switch(c) {
	case '+': case '-':
		return 1;
	default:
		return 2;
	}
}
int compute(int a, char op, int b)
{
	switch(op) {
	case '+':
		return a | b;
	case '*':
		return a & b;
	default:
		return a & (~b);
	}
}