集合栈计算机（UVa12096)

　　题目具体描述见：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3248

算法流程如下：

C++11代码如下：

 #include<iostream>

 #include<vector>

 #include<string>

 #include<map>

 #include<set>

 #include<stack>

 #include<algorithm>

 #include<iterator>

 using namespace std;

 typedef set<int> Set;

 map<Set, int>IDcache;

 vector<Set>Setcache;

 // #define ALL(x) x.begin(),x.end()

 // #define INS(x) inserter(x,x,begin())

 int ID(Set x) {

     if (IDcache.count(x)) return IDcache[x];  //map中已有key(x),返回对应的value值

     Setcache.push_back(x);   //map中没有key(x),将其插入vector 中

     return IDcache[x] = Setcache.size() - ;   //将key(x)存入map中，并将对应的value赋值为在vector中的下标

 }

 int main() {

     int n, k;

     stack<int>s;

     cin >> n;

     while (n--) {

         cin >> k;

         while (k--) {

             string str;

             cin >> str;

             if (str[] == 'P') s.push(ID(Set()));   //空集入栈

             else if (str[] == 'D') s.push(s.top());

             else {

                 Set x1 = Setcache[s.top()]; s.pop();

                 Set x2 = Setcache[s.top()]; s.pop();

                 Set x;

                 if (str[] == 'U') set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.begin()));

                 if (str[] == 'I') set_intersection(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.begin()));

                 if (str[] == 'A') { x = x2; x.insert(ID(x1)); }  //将x1的ID插入到x中

                 s.push(ID(x));  //合并后的x存入vector中，再将ID压入栈中

             }

             cout << Setcache[s.top()].size() << endl;

         }

         cout << "***" << endl;

     }

     return ;

 }