Problem:


Problem D: Operations with Finite Sets

Let A, B, C, D, E be sets of integers and let U is a universal set that includes all sets under consideration. All elements in any set are different (no repetitions).

u - union of two sets, AuB = {x &isin; U : x &isin; A or x &isin; B} is the set of all elements which belong to A or B.

i - intersection of two sets, AiB = {x &isin; U : x &isin; A and x &isin; B} is the set of all elements which belong to both A and B.

d - difference of two sets, AdB = {x &isin; U : x &isin; A, x &notin; B} is the set of those elements of A which do not belong to B.

s - symmetric difference of two sets, AsB = (AdB)u(BdA) consists of those elements which belong to A or B but not to both.

c - complement of a set, cA = {x &isin; U : x &notin; A}, is set of elements which belong to U but do not belong to A. Unary operator c has higest precedence.

The universal set U is defined as a union of all sets specified in data. 

Your task is to determine the result of an expression, which includes sets, set operations and parenthesis (any number of parenthesis and any correct enclosure of parenthesis may take place).

Input

Input consists of several pairs of lines difining sets and one pair of lines defining an expression. Each pair of lines for set definition includes the following.

Line 1: Set name (A, B, C, D, E), number of elements in a set.

Line 2: Set elements separated by blanks.

Pair of lines for expression definition:

Line 1: R 0

Line 2: Expression consisting of set names, operators and parenthesis (no blanks).

Number of sets can vary from 1 to 5. Set names can be specified in any order. Each set consists of 1-100 elements. Pair of lines for expression definition signals the end of data set. Input file includes several data sets. The number of datasets is less than 20.

Output

For each data set, the output should contain one line with resulting set elements sorted in ascending order separated by blanks. If the result contains no set elements then the line should contain the text NULL.

Sample Input

A 3
1 3 -1
B 4
3 1 5 7
D 1
5
R 0
cAiBdD
C 3
1 2 3
A 4
2 10 8 3
B 3
2 4 8
R 0
(As(AiB))uC

Output for the Sample Input

7
1 2 3 10



Sample input:
A 3
1 3 -1
B 4
3 1 5 7
D 1
5
R 0
cAiBdD
C 3
1 2 3
A 4
2 10 8 3
B 3
2 4 8
R 0
(As(AiB))uC


Sample output:
7
1 2 3 10

Submission status: Wrong Answer

Solution code:
import sys

def rpn(str):
    r = []
    stack = []
    for i in range(0, len(str)):
        c = str[i]
        if c in "idsu":
            while len(stack) > 0:
                if stack[-1] in "idsuc":
                    a = stack.pop()
                    r.extend(a)
                else:
                    break
            stack.extend(c)
        elif c == "c":
            stack.extend(c)
        elif c == "(":
            stack.extend(c)
        elif c == ")":
            while len(stack) > 0:
                a = stack.pop()
                if a == "(":
                    break
                r.extend(a)
        else:
            r.extend(c)
    while len(stack) > 0:
        a = stack.pop()
        r.extend(a)
    return r

def intersect(a, b):
    r = []
    for e in a:
        if e in b:
            r.extend([e])
    return r

def union(a, b):
    r = list(set(a + b))
    return r

def diff(a, b):
    r = []
    for e in a:
        if e not in b:
            r.extend([e])
    return r

def universal(sets):
    r = []
    for v in sets.values():
        r.extend(v)
    r = list(set(r))
    return r

def calc(rpn, sets):
    stack = []
    U = universal(sets)
    for c in rpn:
        if c in "iuds":
            op2 = stack.pop()
            op1 = stack.pop()
            if c == "i":
                x = intersect(op1, op2)
                stack.append(x)
            elif c == "u":
                x = union(op1, op2)
                stack.append(x)
            elif c == "d":
                x = diff(op1, op2)
                stack.append(x)
            elif c == "s":
                x = diff(op1, op2)
                y = diff(op2, op1)
                z = union(x, y)
                stack.append(z)
        elif c == "c":
            op1 = stack.pop()
            x = diff(U, op1)
            stack.append(x)
        else:
            stack.append(sets[c])
    return stack.pop()
            
lno = 0
sets = {}
name = ""
for line in sys.stdin:
    lno += 1
    if lno % 2 == 1:
        name = line.strip().split()[0]
    elif name != "R":
        elem = list(map(int, line.strip().split()))
        sets[name] = elem
    else:
        e = rpn(line.strip())
        result = calc(e, sets)
        result.sort()
        for n in result:
            print(n, end = " ")
        print()

Submission status: Wrong Answer

Solution code:
import sys

def rpn(str):
    r = []
    stack = []
    for i in range(0, len(str)):
        c = str[i]
        if c in "idsu":
            while len(stack) > 0:
                if stack[-1] in "idsuc":
                    a = stack.pop()
                    r.extend(a)
                else:
                    break
            stack.extend(c)
        elif c == "c":
            stack.extend(c)
        elif c == "(":
            stack.extend(c)
        elif c == ")":
            while len(stack) > 0:
                a = stack.pop()
                if a == "(":
                    break
                r.extend(a)
        else:
            r.extend(c)
    while len(stack) > 0:
        a = stack.pop()
        r.extend(a)
    return r

def intersect(a, b):
    r = []
    for e in a:
        if e in b:
            r.extend([e])
    return r

def union(a, b):
    r = list(set(a + b))
    return r

def diff(a, b):
    r = []
    for e in a:
        if e not in b:
            r.extend([e])
    return r

def universal(sets):
    r = []
    for v in sets.values():
        r.extend(v)
    r = list(set(r))
    return r

def calc(rpn, sets):
    stack = []
    U = universal(sets)
    for c in rpn:
        if c in "iuds":
            op2 = stack.pop()
            op1 = stack.pop()
            if c == "i":
                x = intersect(op1, op2)
                stack.append(x)
            elif c == "u":
                x = union(op1, op2)
                stack.append(x)
            elif c == "d":
                x = diff(op1, op2)
                stack.append(x)
            elif c == "s":
                x = diff(op1, op2)
                y = diff(op2, op1)
                z = union(x, y)
                stack.append(z)
        elif c == "c":
            op1 = stack.pop()
            x = diff(U, op1)
            stack.append(x)
        else:
            stack.append(sets[c])
    return stack.pop()
            
lno = 0
sets = {}
name = ""
for line in sys.stdin:
    lno += 1
    if lno % 2 == 1:
        name = line.strip().split()[0]
    elif name != "R":
        elem = list(map(int, line.strip().split()))
        sets[name] = elem
    else:
        e = rpn(line.strip())
        result = calc(e, sets)
        result.sort()
        if len(result) > 0:
            for n in result:
                print(n, end = " ")
            print()
        else:
            print("NULL")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
from collections import defaultdict

class cset():
    
    def __init__(self, x):
        self.x = set(x)
    
    def __or__(self, that):
        return cset(self.x | that.x)
    
    def __sub__(self, that):
        return cset(self.x - that.x)

    def __and__(self, that):
        return cset(self.x & that.x)
    
    def __xor__(self, that):
        return cset(self.x ^ that.x)
    
    def __neg__(self):
        return cset(U-self.x)

try:
    while True:
        X = defaultdict(list)
        x, _ = input().split()
        while x != "R":
            X[x] = list(map(int, input().split()))
            x, _ = input().split()
        
        A, B, C, D, E = X["A"], X["B"], X["C"], X["D"], X["E"]
        U = set()
        U.update(A, B, C, D, E)
        S = input()
        for a, b in zip(list("uidsc"), list("|&-^-")):
            S = S.replace(a, b)
        for a in list("ABCDE"):
            S = S.replace(a, "cset({})".format(a))
        print(*sorted(list(eval(S).x)))
except:
    pass

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
from collections import defaultdict

class cset():
    
    def __init__(self, x):
        self.x = set(x)
    
    def __or__(self, that):
        return cset(self.x | that.x)
    
    def __sub__(self, that):
        return cset(self.x - that.x)

    def __and__(self, that):
        return cset(self.x & that.x)
    
    def __xor__(self, that):
        return cset(self.x ^ that.x)
    
    def __neg__(self):
        return cset(U-self.x)

try:
    while True:
        X = defaultdict(list)
        x, _ = input().split()
        while x != "R":
            X[x] = list(map(int, input().split()))
            x, _ = input().split()
        
        A, B, C, D, E = X["A"], X["B"], X["C"], X["D"], X["E"]
        U = set()
        U.update(A, B, C, D, E)
        S = input()
        for a, b in zip(list("uidsc"), list("|&-^-")):
            S = S.replace(a, b)
        for a in list("ABCDE"):
            S = S.replace(a, "cset({})".format(a))
        ans = sorted(list(eval(S).x))
        if len(S) == 0:
            print("NULL")
        else:
            print(*ans)
except:
    pass

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
from collections import defaultdict

class cset():
    
    def __init__(self, x):
        self.x = set(x)
    
    def __or__(self, that):
        return cset(self.x | that.x)
    
    def __sub__(self, that):
        return cset(self.x - that.x)

    def __and__(self, that):
        return cset(self.x & that.x)
    
    def __xor__(self, that):
        return cset(self.x ^ that.x)
    
    def __neg__(self):
        return cset(U-self.x)

try:
    while True:
        X = defaultdict(list)
        x, _ = input().split()
        while x != "R":
            X[x] = list(map(int, input().split()))
            x, _ = input().split()
        
        A, B, C, D, E = X["A"], X["B"], X["C"], X["D"], X["E"]
        U = set()
        U.update(A, B, C, D, E)
        S = input()
        #print(S)
        for a, b in zip(list("uidsc"), list("|&-^-")):
            S = S.replace(a, b)
        #print(S)
        for a in list("ABCDE"):
            S = S.replace(a, "cset({})".format(a))
        #print(S)
        ans = sorted(list(eval(S).x))
        if len(ans) == 0:
            print("NULL")
        else:
            print(*ans)
except:
    pass

Submission status: Wrong Answer

Solution code:
while True:
    try:
        name,elsize=raw_input().split()
    except EOFError:
        break
    p={}
    U=set()
    while True:
        p[name]=set(map(int,raw_input().split()))
        U=U.union(p[name])
        name,elsize=raw_input().split()
        if name=="R" and elsize=="0":break
    exp=raw_input()
    rule={"d":"-","i":"&","u":"|","s":"^","c":"U-"}
    for i in ["A","B","C","D","E"]:
        exp=exp.replace(i,'p["'+i+'"]')
    for i in rule:
        exp=exp.replace(i,rule[i])
    t=sorted(eval(exp))
    print " ".join(map(str,t))

Submission status: Wrong Answer

Solution code:
while True:
    try:
        name,elsize=raw_input().split()
    except EOFError:
        break
    p={}
    U=set()
    while True:
        p[name]=set(map(int,raw_input().split()))
        U=U.union(p[name])
        name,elsize=raw_input().split()
        if name=="R" and elsize=="0":break
    exp=raw_input()
    rule={"d":"-","i":"&","u":"|","s":"^","c":"U-"}
    for i in ["A","B","C","D","E"]:
        exp=exp.replace(i,'p["'+i+'"]')
    for i in rule:
        exp=exp.replace(i,rule[i])
    t=sorted(eval(exp))
    if t==[]:
        print "NULL"
    else:
        print " ".join(map(str,t))

Submission status: Wrong Answer

Solution code:
def convertC(r):
    s=""
    i=0
    stack=[]
    while i<len(r):
        if r[i]=="c":
            if "A"<=r[i+1]<="E":
                s+="(U-"+r[i+1]+")"
                i+=2
            elif r[i+1]=="(":
                s+="(U-"+r[i+1]
                stack.append(r[i+1])
                j=2
                while stack<>[]:
                    if r[i+j]=="(":
                        stack.append(r[i+j])
                    elif r[i+j]==")":
                        stack.pop()
                    s+=r[i+j]
                    j+=1
                else:
                    s+=")"
                    i+=j
        else:
            s+=r[i]
            i+=1
    return s

while True:
    try:
        name,elsize=raw_input().split()
    except EOFError:
        break
    p={}
    U=set()
    while True:
        p[name]=set(map(int,raw_input().split()))
        U=U.union(p[name])
        name,elsize=raw_input().split()
        if name=="R" and elsize=="0":break
    exp=raw_input()
    exp=convertC(exp)
    rule={"d":"-","i":"&","u":"|","s":"^"}
    for i in ["A","B","C","D","E"]:
        exp=exp.replace(i,'p["'+i+'"]')
    for i in rule:
        exp=exp.replace(i,rule[i])
    t=sorted(eval(exp))
    if len(t)==0:
        print "NULL"
    else:
        print " ".join(map(str,t))

Submission status: Accepted

Solution code:
import sys

def rpn(str):
    r = []
    stack = []
    for i in range(0, len(str)):
        c = str[i]
        if c in "idsu":
            while len(stack) > 0:
                if stack[-1] in "idsuc":
                    a = stack.pop()
                    r.extend(a)
                else:
                    break
            stack.extend(c)
        elif c == "c":
            stack.extend(c)
        elif c == "(":
            stack.extend(c)
        elif c == ")":
            while len(stack) > 0:
                a = stack.pop()
                if a == "(":
                    break
                r.extend(a)
        else:
            r.extend(c)
    while len(stack) > 0:
        a = stack.pop()
        r.extend(a)
    return r

def intersect(a, b):
    r = []
    for e in a:
        if e in b:
            r.extend([e])
    return r

def union(a, b):
    r = list(set(a + b))
    return r

def diff(a, b):
    r = []
    for e in a:
        if e not in b:
            r.extend([e])
    return r

def universal(sets):
    r = []
    for v in sets.values():
        r.extend(v)
    r = list(set(r))
    return r

def calc(rpn, sets):
    stack = []
    U = universal(sets)
    for c in rpn:
        if c in "iuds":
            op2 = stack.pop()
            op1 = stack.pop()
            if c == "i":
                x = intersect(op1, op2)
                stack.append(x)
            elif c == "u":
                x = union(op1, op2)
                stack.append(x)
            elif c == "d":
                x = diff(op1, op2)
                stack.append(x)
            elif c == "s":
                x = diff(op1, op2)
                y = diff(op2, op1)
                z = union(x, y)
                stack.append(z)
        elif c == "c":
            op1 = stack.pop()
            x = diff(U, op1)
            stack.append(x)
        else:
            stack.append(sets[c])
    return stack.pop()
            
lno = 0
sets = {}
name = ""
for line in sys.stdin:
    lno += 1
    if lno % 2 == 1:
        name = line.strip().split()[0]
    elif name != "R":
        elem = list(map(int, line.strip().split()))
        sets[name] = elem
    else:
        e = rpn(line.strip())
        result = calc(e, sets)
        result.sort()
        if len(result) > 0:
            print(" ".join([str(n) for n in result]))
        else:
            print("NULL")
        sets = {}

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

while True:
    A = set()
    B = set()
    C = set()
    D = set()
    E = set()
    while True:
        try:
            name, _ = raw_input().split()
            if name == 'R':
                break
            globals()[name] = set(map(int, raw_input().split()))
        except:
            exit()
    U = A | B | C | D | E

    # evaluate operation
    def operate(term1, term2, op):
        if op == 'u':
            return term1 | term2
        if op == 'i':
            return term1 & term2
        if op == 'd':
            return term1 - term2
        if op == 's':
            return term1 ^ term2

    # evaluate expression without bracket
    def calc(S):
        if len(S) == 1:
            if type(S[0]) == type(""):
                return globals()[S[0]]
            else:
                return S[0]
        for i in range(len(S) - 1, -1, -1):
            if S[i] in ['u', 'i', 'd', 's']:
                return operate(calc(S[:i]), calc(S[i + 1:]), S[i])
        return U - calc(S[1:]) # case of ['inv']

    # evaluate expression
    def br(S):
        index = 0
        lst = []
        while True:
            if index >= len(S) or S[index] == ')':
                return index, calc(lst)
            elif S[index] == '(':
                ret, value = br(S[index + 1:])
                index += ret + 1
                lst.append(value)
            else:
                lst.append(S[index])
            index += 1

    def split(S):
        ret = []
        for c in S:
            if c == 'c':
                ret.append('inv')
            else:
                ret.append(c)
        return ret

    S = raw_input()
    ans = br(split(S))[1]
    print ' '.join(map(str, sorted(list(ans)))) if len(ans) > 0 else 'NULL'

Submission status: Runtime Error

Solution code:
import sys

def rpn(str):
    r = []
    stack = []
    for i in range(0, len(str)):
        c = str[i]
        if c in "idsu":
            while len(stack) > 0:
                if stack[-1] in "idsuc":
                    a = stack.pop()
                    r.extend(a)
                else:
                    break
            stack.extend(c)
        elif c == "c":
            stack.extend(c)
        elif c == "(":
            stack.extend(c)
        elif c == ")":
            while len(stack) > 0:
                a = stack.pop()
                if a == "(":
                    break
                r.extend(a)
        else:
            r.extend(c)
    while len(stack) > 0:
        a = stack.pop()
        r.extend(a)
    return r

def intersect(a, b):
    r = []
    for e in a:
        if e in b:
            r.extend([e])
    return r

def union(a, b):
    r = list(set(a + b))
    return r

def diff(a, b):
    r = []
    for e in a:
        if e not in b:
            r.extend([e])
    return r

def universal(sets):
    r = []
    for v in sets.values():
        r.extend(v)
    r = list(set(r))
    return r

def calc(rpn, sets):
    stack = []
    U = universal(sets)
    for c in rpn:
        if c in "iuds":
            op2 = stack.pop()
            op1 = stack.pop()
            if c == "i":
                x = intersect(op1, op2)
                stack.append(x)
            elif c == "u":
                x = union(op1, op2)
                stack.append(x)
            elif c == "d":
                x = diff(op1, op2)
                stack.append(x)
            elif c == "s":
                x = diff(op1, op2)
                y = diff(op2, op1)
                z = union(x, y)
                stack.append(z)
        elif c == "c":
            op1 = stack.pop()
            x = diff(U, op1)
            stack.append(x)
        else:
            stack.append(sets[c])
    return stack.pop()
            
lno = 0
sets = {}
name = ""
for line in sys.stdin:
    lno += 1
    if lno % 2 == 1:
        name = line.strip().split()[0]
    elif name != "R":
        elem = list(map(int, line.strip().split()))
        sets[name] = elem
    else:
        e = rpn(line.strip())
        result = calc(e, sets)
        result.sort()
        if length(result) > 0:
            for n in result:
                print(n, end = " ")
            print()
        else:
            print("NULL")

Submission status: Runtime Error

Solution code:
def convertC(r):
    s=""
    i=0
    stack=[]
    while i<len(r):
        if r[i]=="c":
            if "A"<=r[i+1]<="E":
                s+="(U-"+r[i+1]+")"
                i+=2
            elif r[i+1]=="(":
                s+="(U-"+r[i+1]
                stack.append(r[i+1])
                j=2
                while stack<>[]:
                    if r[i+j]=="(":
                        stack.append(r[i+j])
                    elif r[i+j]==")":
                        stack.pop()
                    s+=r[i+j]
                    j+=1
                else:
                    s+=")"
                    i=j
        else:
            s+=r[i]
            i+=1
    return s

while True:
    try:
        name,elsize=raw_input().split()
    except EOFError:
        break
    p={}
    U=set()
    while True:
        p[name]=set(map(int,raw_input().split()))
        U=U.union(p[name])
        name,elsize=raw_input().split()
        if name=="R" and elsize=="0":break
    exp=raw_input()
    exp=convertC(exp)
    rule={"d":"-","i":"&","u":"|","s":"^"}
    print exp
    for i in ["A","B","C","D","E"]:
        exp=exp.replace(i,'p["'+i+'"]')
    for i in rule:
        exp=exp.replace(i,rule[i])
    t=sorted(eval(exp))
    if len(t)==0:
        print "NULL"
    else:
        print " ".join(map(str,t))

Submission status: WA: Presentation Error

Solution code:
import sys

def rpn(str):
    r = []
    stack = []
    for i in range(0, len(str)):
        c = str[i]
        if c in "idsu":
            while len(stack) > 0:
                if stack[-1] in "idsuc":
                    a = stack.pop()
                    r.extend(a)
                else:
                    break
            stack.extend(c)
        elif c == "c":
            stack.extend(c)
        elif c == "(":
            stack.extend(c)
        elif c == ")":
            while len(stack) > 0:
                a = stack.pop()
                if a == "(":
                    break
                r.extend(a)
        else:
            r.extend(c)
    while len(stack) > 0:
        a = stack.pop()
        r.extend(a)
    return r

def intersect(a, b):
    r = []
    for e in a:
        if e in b:
            r.extend([e])
    return r

def union(a, b):
    r = list(set(a + b))
    return r

def diff(a, b):
    r = []
    for e in a:
        if e not in b:
            r.extend([e])
    return r

def universal(sets):
    r = []
    for v in sets.values():
        r.extend(v)
    r = list(set(r))
    return r

def calc(rpn, sets):
    stack = []
    U = universal(sets)
    for c in rpn:
        if c in "iuds":
            op2 = stack.pop()
            op1 = stack.pop()
            if c == "i":
                x = intersect(op1, op2)
                stack.append(x)
            elif c == "u":
                x = union(op1, op2)
                stack.append(x)
            elif c == "d":
                x = diff(op1, op2)
                stack.append(x)
            elif c == "s":
                x = diff(op1, op2)
                y = diff(op2, op1)
                z = union(x, y)
                stack.append(z)
        elif c == "c":
            op1 = stack.pop()
            x = diff(U, op1)
            stack.append(x)
        else:
            stack.append(sets[c])
    return stack.pop()
            
lno = 0
sets = {}
name = ""
for line in sys.stdin:
    lno += 1
    if lno % 2 == 1:
        name = line.strip().split()[0]
    elif name != "R":
        elem = list(map(int, line.strip().split()))
        sets[name] = elem
    else:
        e = rpn(line.strip())
        result = calc(e, sets)
        result.sort()
        if len(result) > 0:
            for n in result:
                print(n, end = " ")
            print()
        else:
            print("NULL")
        sets = {}