题目链接：
题目简介：
（1）题目中的集合由 A-Z 的大写字母组成，例如 "{ABC}" 的字符串表示 A，B，C 组成的集合。
（2）用运算符三种集合运算，'+' 表示两个集合的并集，'*' 表示两个集合的交集， '-' 表示从第一个集合中排除第二个集合包含的元素。
（3）给出这样的表达式，求出表达式结果（按照字母顺序）。运算符优先级和编程语言中的规定相同，即优先级从高到低为括号，乘号，加/减号；相同优先级时从左向右。
例如： "{ABC}+{BCD}" = "{ABCD}";
题目分析：
属于常规的表达式求值，方法是借助两个栈来解析。本质上来讲，这是一个简单题目，但是细节比较繁琐，要写对需要耐心。集合可以用 bitset 来表示这个集合，由于集合的元素数目不会超过 26，因此用 uint32 整数即可表示集合，这样可以把集合运算转换为整数的位操作来完成，比直接处理字符串更加方便。例如：
s1: { A } -> n1 = 0x01;
s2: { B } -> n2 = 0x02;
则：（s1+s2）转换为（n1 | n2）。
题目声明输入数据都是合法的表达式，不需要考虑表达式合法性判断。则只需要表达式的解析，解析过程由运算符驱动，其中需要注意的细节有：
（1）左括号在栈内和栈外的优先级需要区分对待（在栈外具有最高优先级，入栈后则优先级降低，以让后续的运算符能够入栈）。
（2）右括号实际上不入栈，而是作为一个信号，负责把和它匹配的左括号从栈中弹出。
（3）在解析前，提前在运算符栈中压入一个左括号，这样编码形式就会统一（不需要考虑在最开始阶段，取不到栈内的运算符优先级的问题）。
（4）解析结束后，取出操作数栈中的唯一元素即可。再将其解析为字符串形式。
需要考虑的特殊情况比如：
({A})+({B}) 相当于：(1)+(2);
提交代码：
#include <stdio.h> #include <string.h> char stack_op[256]; unsigned int stack_num[256]; int top_op; int top_num; int GetPrecedence(char op, int bInStack); char* GetNumber(char *str, unsigned int *pNum); unsigned int Compute(char* line); int main(int argc, char* argv[]); int GetPrecedence(char op, int bInStack) { switch(op) { case 0: return 1; case '(': return bInStack? 1 : 100; case ')': return 1; case '+': return 2; case '-': return 2; case '*': return 3; } return 0; } /* {ABCDEFG}+ | | str ret_val */ char* GetNumber(char *str, unsigned int *pNum) { char *pCh = str + 1; *pNum = 0; while(*pCh != '}') { if(*pCh >= 'A' && *pCh <= 'Z') *pNum = *pNum | (1 << (*pCh - 'A')); ++pCh; } return pCh; } unsigned int Compute(char* line) { char *pCh; unsigned int n1, n2, result; int prec1, prec2; top_op = 0; stack_op[top_op] = '('; top_num = -1; pCh = line; while(1) { if(*pCh == '{') { pCh = GetNumber(pCh, &n1); ++top_num; stack_num[top_num] = n1; } else { prec2 = GetPrecedence(*pCh, 0); prec1 = GetPrecedence(stack_op[top_op], 1); if(prec2 > prec1) { ++top_op; stack_op[top_op] = *pCh; } else { while(prec2 <= prec1 && strchr("*+-", stack_op[top_op]) != NULL) { n1 = stack_num[top_num - 1]; n2 = stack_num[top_num]; switch(stack_op[top_op]) { case '+': result = (n1 | n2); break; case '-': result = (n1 & (~n2)); break; case '*': result = (n1 & n2); break; } --top_num; stack_num[top_num] = result; --top_op; prec1 = GetPrecedence(stack_op[top_op], 1); } if(*pCh == ')') { while(stack_op[top_op] != '(') { --top_op; } --top_op; } else if(*pCh == 0) break; else { /* push current operator into stack */ ++top_op; stack_op[top_op] = *pCh; } } } ++pCh; } /* __ENDOF__ while(1) */ if(top_num == 0) result = stack_num[0]; else result = 0; return result; } int main(int argc, char* argv[]) { unsigned int result, x; char line[256]; while(gets(line) != NULL) { result = Compute(line); printf("{"); for(x = 0; x < 26; x++) { if(result & (1 << x)) printf("%c", x + 'A'); } printf("}\n"); } return 0; }
提交结果：
| Judge Status | Problem ID | Language | Run Time(ms) | Run Memory(KB) |
| Accepted | 1958 | C | 0 | 172 |
