The comprehensive application of the setstack computer (uva12096) Purple Book p116stl

First Vjudge Address ： Click here

subject ：

There's one designed specifically for set operations “ Set stack ” Computer . The machine has a stack that starts empty and supports the following operations .
1.PUSH： An empty set “{}” Push .
2.DUP： Copy the current top of the stack element and put it on the stack .
3.UNION： Two sets out of the stack , Then put the union of the two on the stack .
4.INTERSECT： Two sets out of the stack , Then put the intersection of the two on the stack .
5.ADD： Two sets out of the stack , Then add the first out of stack set to the later out of stack set , Put the results on the stack .

for example , The top element of the stack is A = { {},{ {}} }, The next element is B = { {}, { { {}}} }, be ：
UNION The operation will get { {}, { {}}, { { {}}} }, Output 3.
INTERSECT The operation will get { {} }, Output 1.
ADD The operation will get { {}, { { {}}},{ {} , { {}}} }, Output 3.

Input ：

The first line has an integer T（0<=T<=5） Express T Group test data .
Each set of test data has N（0<=N<=2000） operations , Ensure smooth operation （ There is no need to perform an out of stack operation on an empty stack ）.

Output ：

For each operation specified in the input , Output the size of the stack top set （ That is, the number of elements ） And line breaks .
Output one line after each set of test data “***”.

Examples ：

Intput
2
9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION
5
PUSH
PUSH
ADD
PUSH
INTERSECT

Output
0
0
1
0
1
1
2
2
2
***
0
0
1
0
0
***

Topic analysis ( According to the purple book )：

How to simulate the collection stack described in the topic ？ The big guys are flying all over the sky stl The operation is really impressive ;
The point to be explained separately in this topic is , All sets in the topic are operated by an empty set , Therefore, the form of elements in a set is not limited to brackets or numbers , It can be extended more widely ;

data structure （ A top priority ）：
Before explaining the choice of data structure , We know that every element in a set is unique , So you can give each element in the set Assign sequence number , Replace the element with a sequence number without operating on the element itself ;
for example ：{ {}} Marked with serial number 1,{ {},{}} Marked with serial number 2,{ { {}},{}} Marked with serial number 3… wait ;
So we can use set<int> a Store each set ,
utilize map<set<int>,int> IDcache Store the correspondence between set and sequence number ;
utilize vector<set<int>> Setcache To get the contents of the collection through the sequence number ;
Definition stcak<int> s A stack that stores the sequence number of a collection ;
thus , We can already define the container and STL A series of operations required in the title are realized by the built-in function of ;

Algorithm design ：
Just hard simulation ;

Module design ： Definition and pretreatment – Read in and initialize – simulation – Output –return 0;

Code ：

#include<bits/stdc++.h>
using namespace std;

typedef set<int> Set;
map<Set,int> IDcache;
vector<Set> Setcache;
int t,n;

int ID(Set x){
    
	 if(IDcache.count(x)) return IDcache[x]; // adopt map Get set label 
	 Setcache.push_back(x);
	 return IDcache[x]=Setcache.size()-1; // If you can't find it, follow up the label 
}

#define ALL(x) x.begin(),x.end() // Konjaku does not understand the macro , Just for a suit 
#define INS(x) inserter(x,x.begin())

int main()
{
    
	 cin>>t;
	 while(t--)
	 {
    
	 	 stack<int> s;
	 	 cin>>n;
	 	 string order;
	 	 for(int i=0;i<n;i++)
	 	 {
    
	 	 	 cin>>order;
	 	 	 if(order=="PUSH") s.push(ID(Set()));
	 	 	 else if(order=="DUP") s.push(s.top());
	 	 	 else{
    
	 	 	 	 Set x1=Setcache[s.top()];
	 	 	 	 s.pop();
	 	 	 	 Set x2=Setcache[s.top()];
	 	 	 	 s.pop();
	 	 	 	 Set x;
	 	 	 	 if(order=="UNION") set_union (ALL(x1),ALL(x2),INS(x));
	 	 	 	 if(order=="INTERSECT") set_intersection (ALL(x1),ALL(x2),INS(x));
	 	 	 	 if(order=="ADD") {
     x=x2; x.insert(ID(x1));}
	 	 	 	 s.push(ID(x));
			 }
			 cout<<Setcache[s.top()].size()<<endl;
		 }
		 cout<<"***"<<endl;
	 }
	 return 0;
}

Summary of key points and details ：

1. About... In the code set_union And set_intersection yes STL Built in functions for , Save in header file #include<set>,uinon Is a union ,intersection To get the intersection ; Use details reference here ;
2. Worship big brother STL Use ;

Update and 2020.7.3