Aizu Online Judge 1012 Operations with Finite Sets

■1012 Operations with Finite Sets

構文解析ゲー．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. // AC  
10. public class Main{  
11.   
12.  Scanner sc=new Scanner(System.in);  
13.   
14.  int INF=1<<28;  
15.  double EPS=1e-9;  
16.  TreeSet<Integer>[] sets;  
17.  String exp;  
18.  TreeSet<Integer> U;  
19.   
20.  @SuppressWarnings("unchecked")  
21.  void run(){  
22.   for(; sc.hasNext();){  
23.    sets=new TreeSet[256];  
24.    for(char c='A'; c<='E'; c++){  
25.     sets[c]=new TreeSet<Integer>();  
26.    }  
27.    U=new TreeSet<Integer>();  
28.    for(;;){  
29.     char c=sc.next().charAt(0);  
30.     int n=sc.nextInt();  
31.     if(c=='R'&&n==0){  
32.      break;  
33.     }  
34.     for(int i=0; i<n; i++){  
35.      int e=sc.nextInt();  
36.      sets[c].add(e);  
37.      U.add(e);  
38.     }  
39.    }  
40.    exp=sc.next();  
41.    solve();  
42.   }  
43.  }  
44.   
45.  void solve(){  
46.   exp+='\0';  
47.   Result r=e(0);  
48.   debug(r.set.toArray());  
49.   if(r.set.size()==0){  
50.    println("NULL");  
51.   }else{  
52.    for(Iterator<Integer> it=r.set.iterator(); it.hasNext();){  
53.     print(it.next()+(it.hasNext()?" ":"\n"));  
54.    }  
55.   }  
56.  }  
57.   
58.  Result e(int p){  
59.   debug("e", p);  
60.   Result r=f(p);  
61.   debug(r.set.toArray(), r.p);  
62.   for(;;){  
63.    if(op(exp.charAt(r.p))){  
64.     Result r2=f(r.p+1);  
65.     switch(exp.charAt(r.p)){  
66.     case 'u': // or  
67.      r.set.addAll(r2.set);  
68.      break;  
69.     case 'i': // and  
70.      for(int e : U){  
71.       if(r.set.contains(e)&&r2.set.contains(e)){}else{  
72.        r.set.remove(e);  
73.       }  
74.      }  
75.      break;  
76.     case 'd': // diff  
77.      r.set.removeAll(r2.set);  
78.      break;  
79.     case 's': // sym  
80.      for(int e : U){  
81.       if(r.set.contains(e)&&r2.set.contains(e)){  
82.        r.set.remove(e);  
83.       }else if(r2.set.contains(e)){  
84.        r.set.add(e);  
85.       }  
86.      }  
87.      break;  
88.     }  
89.     r.p=r2.p;  
90.    }else{  
91.     break;  
92.    }  
93.   }  
94.   return r;  
95.  }  
96.   
97.  boolean op(char c){  
98.   return c=='u'||c=='i'||c=='d'||c=='s';  
99.  }  
100.   
101.  Result f(int p){  
102.   debug("f", p);  
103.   if(exp.charAt(p)=='c'){  
104.    Result r=f(p+1);  
105.    TreeSet<Integer> c=new TreeSet<Integer>();  
106.    for(int e : U){  
107.     if(!r.set.contains(e)){  
108.      c.add(e);  
109.     }  
110.    }  
111.    r.set.clear();  
112.    r.set.addAll(c);  
113.    return r;  
114.   }else{  
115.    return t(p);  
116.   }  
117.  }  
118.   
119.  Result t(int p){  
120.   debug("t", p);  
121.   if(exp.charAt(p)=='('){  
122.    Result r=e(p+1);  
123.    r.p++; // skip ')'  
124.    return r;  
125.   }else{  
126.    Result r=new Result(p+1);  
127.    r.set.addAll(sets[exp.charAt(p)]);  
128.    return r;  
129.   }  
130.  }  
131.   
132.  class Result{  
133.   int p;  
134.   TreeSet<Integer> set;  
135.   
136.   Result(int p){  
137.    this.p=p;  
138.    set=new TreeSet<Integer>();  
139.   }  
140.  }  
141.   
142.  void debug(Object... os){  
143.   // System.err.println(Arrays.deepToString(os));  
144.  }  
145.   
146.  void print(String s){  
147.   System.out.print(s);  
148.  }  
149.   
150.  void println(String s){  
151.   System.out.println(s);  
152.  }  
153.   
154.  public static void main(String[] args){  
155.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
156.   new Main().run();  
157.  }  
158. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;
 TreeSet<Integer>[] sets;
 String exp;
 TreeSet<Integer> U;

 @SuppressWarnings("unchecked")
 void run(){
  for(; sc.hasNext();){
   sets=new TreeSet[256];
   for(char c='A'; c<='E'; c++){
    sets[c]=new TreeSet<Integer>();
   }
   U=new TreeSet<Integer>();
   for(;;){
    char c=sc.next().charAt(0);
    int n=sc.nextInt();
    if(c=='R'&&n==0){
     break;
    }
    for(int i=0; i<n; i++){
     int e=sc.nextInt();
     sets[c].add(e);
     U.add(e);
    }
   }
   exp=sc.next();
   solve();
  }
 }

 void solve(){
  exp+='\0';
  Result r=e(0);
  debug(r.set.toArray());
  if(r.set.size()==0){
   println("NULL");
  }else{
   for(Iterator<Integer> it=r.set.iterator(); it.hasNext();){
    print(it.next()+(it.hasNext()?" ":"\n"));
   }
  }
 }

 Result e(int p){
  debug("e", p);
  Result r=f(p);
  debug(r.set.toArray(), r.p);
  for(;;){
   if(op(exp.charAt(r.p))){
    Result r2=f(r.p+1);
    switch(exp.charAt(r.p)){
    case 'u': // or
     r.set.addAll(r2.set);
     break;
    case 'i': // and
     for(int e : U){
      if(r.set.contains(e)&&r2.set.contains(e)){}else{
       r.set.remove(e);
      }
     }
     break;
    case 'd': // diff
     r.set.removeAll(r2.set);
     break;
    case 's': // sym
     for(int e : U){
      if(r.set.contains(e)&&r2.set.contains(e)){
       r.set.remove(e);
      }else if(r2.set.contains(e)){
       r.set.add(e);
      }
     }
     break;
    }
    r.p=r2.p;
   }else{
    break;
   }
  }
  return r;
 }

 boolean op(char c){
  return c=='u'||c=='i'||c=='d'||c=='s';
 }

 Result f(int p){
  debug("f", p);
  if(exp.charAt(p)=='c'){
   Result r=f(p+1);
   TreeSet<Integer> c=new TreeSet<Integer>();
   for(int e : U){
    if(!r.set.contains(e)){
     c.add(e);
    }
   }
   r.set.clear();
   r.set.addAll(c);
   return r;
  }else{
   return t(p);
  }
 }

 Result t(int p){
  debug("t", p);
  if(exp.charAt(p)=='('){
   Result r=e(p+1);
   r.p++; // skip ')'
   return r;
  }else{
   Result r=new Result(p+1);
   r.set.addAll(sets[exp.charAt(p)]);
   return r;
  }
 }

 class Result{
  int p;
  TreeSet<Integer> set;

  Result(int p){
   this.p=p;
   set=new TreeSet<Integer>();
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}