集合运算问题题解

一、题目分析

题目要求对集合表达式进行运算，支持并集（+）、差集（-）、交集（*），其中交集优先级高于并集和差集，运算左结合。输入为合法表达式，输出运算结果集合（元素按字母序排列）。

二、算法思路

1. 数据结构：用长度为26的数组表示集合（索引0-25对应A-Z，1表示元素存在）。
2. 表达式解析：通过递归和栈处理表达式，类似中缀表达式求值：
   • 递归处理括号内子表达式；
   • 栈存储运算符和操作数，按优先级执行运算。
3. 集合运算：利用位运算实现并（|）、差（&!）、交（&）操作。

三、代码实现（原代码框架）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
char s[100008];
int id;
struct point{
    int c[26];
    point(){ memset(c,0,sizeof(c)); }
    point operator + (const point &p1)
    {
        point temp;
        for(int i=0;i<26;i++) temp.c[i]=c[i]|p1.c[i];
        return temp;
    }
    point operator - (const point &p1)
    {
        point temp;
        for(int i=0;i<26;i++) temp.c[i]=c[i]&(!p1.c[i]);
        return temp;
    }
    point operator * (const point &p1)
    {
        point temp;
        for(int i=0;i<26;i++) temp.c[i]=c[i]&p1.c[i];
        return temp;
    }
    void print()
    {
        printf("{");
        for(int i=0;i<26;i++) if(c[i]) printf("%c",'A'+i);
        printf("}\n");
    }
}res;
point get()
{
    point temp;
    for(id++;s[id]!='}';id++) temp.c[s[id]-'A']=1;
    return temp;
}
int getp(char ch)
{
    if(ch=='*') return 2;
    return 1;
}
point cal(point p1,char ch,point p2)
{
    if(ch=='+') return p1+p2;
    else if(ch=='-') return p1-p2;
    return p1*p2;
}
point solve()
{
    point temp,temp2,now;
    stack<char>op;
    stack<point>q;

    if(s[id]=='('){ id++; now=solve(); }
    else now=get();
    q.push(now);
    for(id++;s[id]!='\0'&&s[id]!=')';id++)
    {
        char ch=s[id++];
        if(s[id]=='('){ id++; now=solve(); }
        else now=get();
        if(op.empty()){ op.push(ch); q.push(now); }
        else
        {
            char ch2=op.top();
            op.pop();
            if(getp(ch2)>=getp(ch))
            {
                temp=q.top(); q.pop();
                temp2=q.top();  q.pop();
                temp=cal(temp2,ch2,temp);
                q.push(temp);
                q.push(now);
                op.push(ch);
            }
            else
            {
                temp=q.top(); q.pop();
                now=cal(temp,ch,now);
                q.push(now);
                op.push(ch2);
            }
        }
    }
    if(!op.empty())
    {
        char ch=op.top();
        now=q.top();  q.pop();
        temp=q.top();  q.pop();
        now=cal(temp,ch,now);
    }
    else now=q.top();

    return now;
}
int main()
{
    while(scanf("%s",s)>0)
    {
        id=0;
        res=solve();
        res.print();
    }
    return 0;
}

四、代码核心逻辑解析

1. 集合表示与运算：

   • point结构体用数组c[26]存储集合元素，通过位运算实现并、差、交操作。例如：
     • 并集+：temp.c[i] = c[i] | p1.c[i]（只要一个集合有该元素，结果就有）；
     • 差集-：temp.c[i] = c[i] & (!p1.c[i])（仅当前集合有且另一集合没有）；
     • 交集*：temp.c[i] = c[i] & p1.c[i]（两个集合都有该元素）。

2. 表达式解析流程：

   • get()函数解析花括号内的集合（如{ABC}转换为c['A'-'A']=1, c['B'-'A']=1, c['C'-'A']=1）。
   • solve()函数递归处理表达式：
     • 遇(则递归解析子表达式；
     • 用栈管理运算符op和操作数q，按优先级（*优先级2，+和-优先级1）执行运算。例如：
       • 当栈顶运算符优先级≥当前运算符时，先计算栈顶运算（如A*B+C中*优先级高，先算A*B）；
       • 否则，先计算当前运算符（如A+B*C中+优先级等于*，但左结合，先算A+B）。

3. 输入输出处理：

   • main函数循环读取表达式，调用solve()计算结果，print()按字母序输出集合（遍历c[0-25]，输出对应字母）。

五、示例解析

以输入{ABC}+{CDE}*{CEZ}为例：

1. 解析为{ABC} + ({CDE} * {CEZ})（交集优先级高于并集）。
2. 计算{CDE} * {CEZ}：交集为{CE}。
3. 计算{ABC} + {CE}：并集为{ABCE}，与输出一致。

六、复杂度分析

• 时间复杂度：O(n)，n为表达式长度，每个字符仅被解析一次。
• 空间复杂度：O(n)，栈最多存储n个运算符和操作数。
• 优化点：位运算高效处理集合操作，递归和栈正确处理表达式优先级，确保运算顺序正确。