鱼C论坛Python精英挑战赛（第二季04期）评比结果

jerryxjr1220

可能是由于本期题目的难度提高了，所以参与答题的鱼油人数明显减少了。

答题者中，有不少鱼油采用替换的方法并结合eval函数，虽然结果正确，但eval函数在大多数服务器上是禁止使用的（出于安全性考虑），所以都不计分。

剩下的鱼油中，@小锟 的解答当s6='!(apple & other) | !apple & !(yellow | green)'时，判断错误

小剑剑、gunjang、zmx296689210 测试结果都正确，而且代码长度都差不多，所以评选他们并列第一。

最后请@小甲鱼 老师评判并颁奖！

jerryxjr1220

贴下我的解答，其实这题应该很明显可以考虑用递归函数，为什么大家都没有想到呢？

用递归写的话，逻辑很清楚，程序也很简洁，看注释吧。不算注释的话，才10多行代码。

1. def search(string, txt):
   
2.     #去首尾空格
   
3.     string = string.strip()
   
4.     #主循环，找不在括号中的“&”和“|”进行判断
   
5.     layer = 0
   
6.     for i in range(len(string)):
   
7.         #判断括号层数
   
8.         if string[i] == '(': layer += 1
   
9.         if string[i] == ')': layer -= 1
   
10.         #处理“&”的情况
    
11.         if string[i] == '&' and layer == 0:
    
12.             if search(string[:i], txt):
    
13.                 return search(string[i+1:], txt)
    
14.             else:
    
15.                 return False
    
16.         #处理“|”的情况
    
17.         elif string[i] == '|' and layer == 0:
    
18.             if search(string[:i], txt):
    
19.                 return True
    
20.             else:
    
21.                 return search(string[i+1:], txt)
    
22.     #去首尾括号
    
23.     if string[0]=='(' and string[-1]==')': return search(string[1:-1], txt)
    
24.     #处理“！”的情况
    
25.     return not search(string[1:], txt) if string[0] == '!' else string in txt

复制代码

小锟

判断单目运算符 ！ 的时候，没考虑到传入的是整数，考虑不全

zmx296689210

楼主代码考虑错了的情况：

1. 
   
2. txt = 'one apple with two leaves, one is green and the other is yellow.'
   
3. string = 'ther'
   
4. print(search(string, txt))
   
5. 
   
6. # 正确结果是 False
   
7. # 而楼主的运行结果是 True， 可能错在非全字匹配那里...我的代码这个样例测试也是错的...我代码需要修改一下判断条件
   

复制代码

修改后...主要是用了转换为后缀式（逆波兰式）

1. import re
   
2. 
   
3. 
   
4. def search(string, txt):
   
5. 
   
6.     pattern = re.compile(r'[^!&|() .,!]+')
   
7.     def changeKeywords(string, txt):
   
8.         '''
   
9.         将关键字转换为0或1
   
10.         例如
    
11.         txt = 'one apple with two leaves, one is green and the other is yellow.'
    
12.         s1 = '(apple | others) & two'
    
13.         转换后 string ='(1 | 0) & 1'
    
14.         '''
    
15.         string = ' ' + string + ' '
    
16.         keywords = pattern.findall(string)
    
17.         for each in keywords:
    
18.             p = re.compile('[!&|() .,!]%s[!&|() .,!]' % each)
    
19.             if p.findall(txt):
    
20.                 string = re.sub('([!&|() ])(%s)([!&|() ])' % each, '\g<1>1\g<3>', string)
    
21.             else:
    
22.                 string = re.sub('([!&|() ])(%s)([!&|() ])' % each, '\g<1>0\g<3>', string)
    
23.         string = string.replace(' ', '')
    
24.         return string
    
25. 
    
26.     operatorPrecedence = {
    
27.         '(': 0,
    
28.         ')': 0,
    
29.         '|': 1,
    
30.         '&': 2,
    
31.         '!': 3
    
32.     }
    
33. 
    
34.     def postfixConvert(exp):
    
35.         '''''
    
36.         将表达式字符串，转为后缀表达式
    
37.         如exp = "1+2*(3-1)-4"
    
38.         转换为：postfix = ['1', '2', '3', '1', '-', '*', '+', '4', '-']
    
39.         '''
    
40.         stack = []  # 运算符栈，存放运算符
    
41.         postfix = []  # 后缀表达式栈
    
42.         for char in exp:
    
43.             #        print char, stack, postfix
    
44.             if char not in operatorPrecedence:  # 非符号，直接进栈
    
45.                 postfix.append(char)
    
46.             else:
    
47.                 if len(stack) == 0:  # 若是运算符栈啥也没有，直接将运算符进栈
    
48.                     stack.append(char)
    
49.                 else:
    
50.                     if char == "(":
    
51.                         stack.append(char)
    
52.                     elif char == ")":  # 遇到了右括号，运算符出栈到postfix中，并且将左括号出栈
    
53.                         while stack[-1] != "(":
    
54.                             postfix.append(stack.pop())
    
55.                         stack.pop()
    
56. 
    
57.                     elif operatorPrecedence[char] > operatorPrecedence[stack[-1]]:
    
58.                         # 只要优先级数字大，那么就继续追加
    
59.                         stack.append(char)
    
60.                     else:
    
61.                         while len(stack) != 0:
    
62.                             if stack[-1] == "(":  # 运算符栈一直出栈，直到遇到了左括号或者长度为0
    
63.                                 break
    
64.                             # 将运算符栈的运算符，依次出栈放到表达式栈里面
    
65.                             postfix.append(stack.pop())
    
66.                         stack.append(char)  # 并且将当前符号追放到符号栈里面
    
67. 
    
68.         while len(stack) != 0:  # 如果符号站里面还有元素，就直接将其出栈到表达式栈里面
    
69.             postfix.append(stack.pop())
    
70.         return postfix
    
71. 
    
72.     def calculate(num1, op, num2='0'):
    
73.         if not num1.isdigit() and not num2.isdigit():
    
74.             raise "num error"
    
75.         else:
    
76.             num1 = int(num1)
    
77.             num2 = int(num2)
    
78.         if op == "&":
    
79.             return int(num1 and num2)
    
80.         elif op == "|":
    
81.             return int(num1 or num2)
    
82.         elif op == "!":
    
83.             return int(not num1)
    
84.         else:
    
85.             raise "op error"
    
86. 
    
87.     def calExpressionTree(postfix):
    
88.         stack = []
    
89.         for char in postfix:
    
90.             stack.append(char)
    
91.             if char in "&|":
    
92.                 op = stack.pop()
    
93.                 num2 = stack.pop()
    
94.                 num1 = stack.pop()
    
95.                 value = calculate(num1, op, num2)
    
96.                 value = str(value)  # 计算结果是数值类型，将其化为字符串类型
    
97.                 stack.append(value)
    
98.             elif char == '!':
    
99.                 op = stack.pop()
    
100.                 num1 = stack.pop()
     
101.                 value = calculate(num1, op)
     
102.                 value = str(value)
     
103.                 stack.append(value)
     
104.         return bool(int(stack[0]))
     
105. 
     
106.     string = changeKeywords(string, txt)
     
107.     postfix = postfixConvert(string)
     
108.     res = calExpressionTree(postfix)
     
109.     return res
     
110. 
     
111. 
     
112. if __name__ == '__main__':
     
113.     txt = 'one apple with two leaves, one is green and the other is yellow.'
     
114. 
     
115.     s1 = '(apple | others) & two'                               # True
     
116.     s2 = 'one & yellow & leaf'                                  # False
     
117.     s3 = '(!three | one & four) & !five'                        # True
     
118.     s4 = '!green & (ones | two)'                                # False
     
119.     s5 = '(big | !apple | the) & ((!yellow | !green) | others)' # False
     
120. 
     
121.     s6 = '!(apple & other) | !apple & !(yellow | green)'
     
122.     s7 = 'ther'
     
123. 
     
124.     print(search(s1, txt))
     
125.     print(search(s2, txt))
     
126.     print(search(s3, txt))
     
127.     print(search(s4, txt))
     
128.     print(search(s5, txt))
     
129.     print(search(s6, txt))
     
130.     print(search(s7, txt))
     

复制代码

jerryxjr1220

zmx296689210 发表于 2017-8-21 00:35
楼主代码考虑错了的情况：

如果ther的话，结果是为True啊， other的一部分，也确实是匹配的啊。

题目规定是包含关键词，并没有规定一定要全字符匹配。

zmx296689210

jerryxjr1220 发表于 2017-8-21 01:19
如果ther的话，结果是为True啊， other的一部分，也确实是匹配的啊。

题目规定是包含关键词，并没有 ...

好吧......