1275.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1275 on 2005-11-11 at 18:19:29 */ 
#include <cstdio>
#include <cstring>
#include <iterator>
#include <set>
using namespace std;

const int L_MAX = 128;
const int MAX = 32;
const int N_MAX = 10;
const int LIMIT = 1 << N_MAX;

char line[L_MAX];
char *l;
int used[MAX], vn;
set<int> var[N_MAX], all;

set<int> build();
int logic(char);
int prior(char);
set<int> compute(set<int>, char, set<int>);

int main()
{
	int T, t, i, j;
	set<int> n, m;

	for(i = 0; i < LIMIT; i++) {
		all.insert(i);
		for(j = 0; j < N_MAX; j++) {
			if((i & (1 << j)) != 0) {
				var[j].insert(i);
			}
		}
	}
	scanf("%d", &T);
	getchar();
	for(t = 1; t <= T; t++) {
		gets(line);
		l = line;
		memset(used, -1, sizeof(used));
		vn = 0;
		n = build();
		m = build();
		printf("Data set %d: ", t);
		if(n == m) {
			printf("Equivalent\n");
		} else {
			printf("Different\n");
		}
	}
	
	return 0;
}

set<int> build() 
{
	int ntop = 0, otop = 0;
	set<int> nstack[L_MAX], a, b;
	char ostack[L_MAX], op;
	bool complete = false;
	
	for(; l[0] != 0 && l[0] != ')'; l++) {
		if(l[0] == '(') {
			if(!complete) {
				complete = true;
				l++;
				nstack[ntop++] = build();
			} else {
				break;
			}
		} else if(l[0] >= 'a' && l[0] <= 'z') {
			if(!complete) {
				complete = true;
			} else {
				break;
			}
			nstack[ntop++] = var[logic(l[0])];
		} else if(l[0] != ' ') {
			if(complete && l[0] == '~') {
				break;
			}
			while(otop > 0 && prior(l[0]) <= prior(ostack[otop-1])) {
				if(l[0] == ostack[otop-1] && l[0] == '~') {
					break;
				} else {
					op = ostack[--otop];
					a = nstack[--ntop];
					if(op == '~') {
						b = all;
					} else {
						b = nstack[--ntop];
					}
					nstack[ntop++] = compute(b, op, a);
				}
			}
			ostack[otop++] = l[0];
			complete = false;
		}
	}
	while(otop > 0) {
		op = ostack[--otop];
		a = nstack[--ntop];
		if(op == '~') {
			b = all;
		} else {
			b = nstack[--ntop];
		}
		nstack[ntop++] = compute(b, op, a);
	}
	
	return nstack[0];
}
int logic(char c)
{
	if(used[c-'a'] == -1) {
		used[c-'a'] = vn++;
	}
	return used[c-'a'];
}
int prior(char op)
{
	switch(op) {
	case '|':
		return 0;
	case '^':
		return 1;
	case '&':
		return 2;
	case '~':
		return 3;
	default:
		return -1;
	}
}
set<int> compute(set<int> a, char op, set<int> b)
{
	set<int> S;
	switch(op) {
	case '|':
		set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(S, S.begin()));
		break;
	case '^':
		set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(S, S.begin()));
		break;
	case '&':
		set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(S, S.begin()));
		break;
	default:
		set_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(S, S.begin()));
		break;
	}
	return S;
}