Problem D
Select Group

Playing the popularity game is all about getting yourself into the right groups. If you are on the football team and the honor roll, this might impress some people. If you are in the AV club, chess club, and academic probation, perhaps not so much. For this problem, develop a program that computes the set of people inside or outside various groups.


Input begins with the description of a collection of up to 100 groups. Each group starts with a line of the form “group $X$ $n$” where $X$ is the name of the group and $1 \le n \le 100$ is the number of people in the group. This is followed by $n$ individual names. Group names and individual names are sequences of upper and lower-case letters (a-z) of length up to 10. The group descriptions will be followed up to 100 selection expressions, one per line. A selection expression is a Polish notation syntax for identifying a set of individuals and may take one of the following forms:

  • $G$
    Where $G$ is the name of a group, selects the set of individuals in group $G$.

  • union $S_1$ $S_2$
    Where $S_1$ and $S_2$ are selection expressions, selects the set of individuals in (selected by) either $S_1$ or $S_2$

  • intersection $S_1$ $S_2$
    Where $S_1$ and $S_2$ are selection expressions, selects the set of individuals in both $S_1$ and $S_2$

  • difference $S_1$ $S_2$
    Where $S_1$ and $S_2$ are selection expressions, selects the set of individuals in $S_1$ but not in $S_2$

Each selection expression contains up to 100 group names and set operations.

The sequence of select statements ends at the end of file. No group will have the name group, union, intersection or difference. Different people will have different names; different groups will have different names.


For each selection expression, print out a single line giving the set of individuals selected. Names on each output line should be space separated and printed in lexicographic order.

Sample Input 1 Sample Output 1
group geeks 3 Trevor Chet Kari
group jocks 3 Chet Mary Bert
group popular 4 Kari Selma Aaron Mary
group Trevor 1 Trevor
union geeks jocks
intersection geeks union jocks popular
union geeks union difference jocks popular Trevor
Bert Chet Kari Mary Trevor
Chet Kari
Bert Chet Kari Trevor
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in