[PYTHON与CSP的姻缘]2023-3 LDAP_csp python题解2023

练习过程

一开始一直以为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)))      # 因为需要递归定义，所以直接用函数写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93