The SetStack Computer
Time limit: 3.000 seconds
题目是这样的：
有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：
PUSH：空集“{}”入栈
DUP：把当前栈顶元素复制一份后再入栈
UNION：出栈两个集合，然后把两者的并集入栈
INTERSECT：出栈两个集合，然后把二者的交集入栈
ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈
每次操作后，输出栈顶集合的大小（即元素个数）。例如栈顶元素是A={ {}， {{}} }， 下一个元素是B={ {}， {{{}}} }，则：
UNION操作将得到{ {}， {{}}， {{{}}} }，输出3.
INTERSECT操作将得到{ {} }，输出1
ADD操作将得到{ {}， {{{}}}， { {}， {{}} } }，输出3.
（输入：先输入测试次数，再输入操作次数，再输入具体操作）
Sample Input
2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT
Sample Output
0
0
1
0
1
1
2
***
0
0
1
0
0
***
【分析】
为每个不同的集合分配一个唯一的ID，则每个集合都可以表示成所包含元素的ID集合，这样就可以用STL的set<int>来表示了，而整个栈则是一个stack<int>。
用C++语言编写程序，代码如下：
#include<iostream>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<string>
#include <algorithm>
using namespace std;
#define ALL(x) x.begin(), x.end()//所有的内容
#define INS(x) inserter(x, x.begin())//插入迭代器
typedef set<int> Set;
map<Set, int> IDcache; //把集合映射成ID
vector<Set> Setcache; //根据ID取集合
//查找给定集合x的ID。如果找不到，分配一个新ID
int ID(Set x) {
if (IDcache.count(x)) return IDcache[x];
Setcache.push_back(x);//添加集合
return IDcache[x] = Setcache.size() - 1;
}
int main() {
int T;
cin >> T;
while (T--) {
stack<int> s;//题目中的栈
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string op;
cin >> op;
if (op[0] == 'P') s.push(ID(Set()));
else if (op[0] == 'D') s.push(s.top());
else {
Set x1 = Setcache[s.top()]; s.pop();
Set x2 = Setcache[s.top()]; s.pop();
Set x;
if (op[0] == 'U') set_union(ALL(x1), ALL(x2), INS(x));
if (op[0] == 'I') set_intersection(ALL(x1), ALL(x2), INS(x));
if (op[0] == 'A') { x = x2; x.insert(ID(x1)); }
//cout << "................." << x.size() << endl;//测试语句
s.push(ID(x));
}
cout << Setcache[s.top()].size() << endl;
}
cout << "***" << endl;
}
return 0;
}
用java语言编写程序，代码如下：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int t = input.nextInt();//测试数据的组数
//将集合映射成ID（使用HashMap可以保证集合的唯一性，即一个集合对应一个ID）
HashMap<HashSet<Integer>, Integer> IDcache = new HashMap<HashSet<Integer>, Integer>();
//储存集合，而链表的下标正是对应集合的ID。所以通过下标我们可以得到对应的集合。
ArrayList<HashSet<Integer>> Setcache = new ArrayList<HashSet<Integer>>();
for(int i = 0; i < t; i++) {
int n = input.nextInt();
//模拟栈（栈中存ID，ID表集合）
Stack<Integer> s = new Stack<Integer>();
for(int j = 0; j < n; j++) {
String x = input.next();
char temp = x.charAt(0);
if(temp == 'P')
//寻找空集对应的ID，然后将ID加入栈中
s.push(ID(new HashSet<Integer>(), IDcache, Setcache));
else if(temp == 'D')
//查看栈顶元素，并将栈顶元素复制再加入栈中
s.push(s.peek());
else {
//通过出栈得到栈顶集合的ID，再有Setcache链表找到原集合，将该集合作为参数创建一个新集合
//注意................
//为什么不找到原集合后就直接赋值给集合对象x1或x2呢？如：HashSet<Integer> x1 = Setcache.get(s.pop())
//原因：因为Setcache链表找到原集合时，返回的是该集合的引用，即集合对象的地址。那么当我们进行下面操作时，必然会改变
//Setcache链表内原有的集合，那样并不是我们所想要的，我们只是想要一个内容一样的集合而已，那么我们只需用返回的集合去构造一个新集合即可。
//找到的原集合内所包含的元素就会复制一份到新集合中。这也是跟C++中有所不同的地方，C++返回对象时，进行 x1 = 对象 这一赋值过程中是对象内部值的复制。
//也就是说它会把表达式右边的对象内部的元素一一赋值到新的对象 x1 去，那样也同我们java上述操作一样了。
HashSet<Integer> x1 = new HashSet<Integer>(Setcache.get(s.pop()));
HashSet<Integer> x2 = new HashSet<Integer>(Setcache.get(s.pop()));
//HashSet<Integer> x3 = new HashSet<Integer>();
if(temp == 'U')
x2.addAll(x1);
else if(temp == 'I')
x2.retainAll(x1);
else
x2.add(ID(x1, IDcache, Setcache));
//System.out.println("..............." + x2.size());
s.push(ID(x2, IDcache, Setcache));
}
System.out.println(Setcache.get(s.peek()).size());
}
System.out.println("***");
}
}
public static Integer ID(HashSet<Integer> x, HashMap<HashSet<Integer>, Integer> IDcache,
ArrayList<HashSet<Integer>> Setcache) {
if(IDcache.containsKey(x))
return IDcache.get(x);
Setcache.add(x);
IDcache.put(x, Setcache.size() - 1);
return Setcache.size() - 1;
}
}
此前java代码中所提到的注意想再多说几句：
