练习过程
一开始一直以为set输出数字的时候是有序的。。。(扣了一天一直显示错误,不知道哪跟哪,大冤种无语了。。。)
然后改了输出直接满分(。。。。。。。无语ing。。。。。。)
主要注意要考虑到表达式的一些嵌套,这样就可以参考题干中对语句的递归定义来写,用递归进行对表达式的切分处理,切分到原子表达式的时候对原子表达式进行分析
题解
def analysis(token): # token->string
ans = set()
if ":" in token:
attr,value = map(int,token.split(':'))
for dn,dic in person.items():
if attr in dic and value==dic[attr]:
ans.add(dn)
elif "~" in token:
attr,value = map(int,token.split('~'))
for dn,dic in person.items():
if attr in dic and value!=dic[attr]:
ans.add(dn)
return ans
def work(token):
ans = set() # 复合条件的用户的dn->set
if token[0].isdigit(): # 原子:union-》
ans = ans.union(analysis(token))
elif token[0] == '&': # 复合->递归
ans1 = set() # 第一个表达式的结果集合->用户dn
ans2 = set() # 第二个表达式的结果集合->用户dn
# 切分第一个表达式
operater = ['('] # 栈,用于判断括号是否闭合
pos = 1 # 指针,标记判断的位置
while len(operater)!=0:
pos += 1
if token[pos] == '(':
operater.append('(')
elif token[pos] == ')':
operater.pop()
ans1 = work(token[2:pos])
# 切分第二个表达式
q = pos+1 # 指针,标记判断的位置
operater = ['(']
while len(operater)!=0:
q += 1
if token[q] == '(':
operater.append('(')
elif token[q] == ')':
operater.pop()
ans2 = work(token[pos+2:q]) # pos是第一个表达式结束的位置,q是第二个表达式结束的位置
ans = ans1 & ans2
elif token[0] == '|':
ans1 = set()
ans2 = set()
operater = ['(']
pos = 1
while len(operater)!=0:
pos += 1
if token[pos] == '(':
operater.append('(')
elif token[pos] == ')':
operater.pop()
ans1 = work(token[2:pos])
q = pos+1
operater = ['(']
while len(operater)!=0:
q += 1
if token[q] == '(':
operater.append('(')
elif token[q] == ')':
operater.pop()
ans2 = work(token[pos+2:q])
ans = ans1 | ans2
return ans
n = int(input())
person = {} # DN-ATTR-VALUE
for _ in range(n):
tmp = list(map(int,input().split()))
dn = tmp[0]
for i in range(2,len(tmp),2):
person.setdefault(dn,{})[tmp[i]] = tmp[i+1]
m = int(input())
for _ in range(m):
s = input()
ans = work(s) # 复合条件的用户的dn->set
if len(ans)==0:
print(" ")
# result.append([])
else:
print(*sorted(list(ans))) # 因为需要递归定义,所以直接用函数写