百姓网那道题

╰半夏微凉° 2022-02-16 02:25 187阅读 0赞

赖勇浩（[http://laiyonghao.com][http_laiyonghao.com]）

昨天 @smallfish 传了个网址（[http://home.wangjianshuo.com/cn/20100505\_ccceeieeaece.htm][http_home.wangjianshuo.com_cn_20100505_ccceeieeaece.htm]）给我，打开一看，是王建硕先生的博客，正好我前段时间经由阮一峰的博客看到过他的简介，就好奇他又写了啥。仔细一看，原来是出了一道公开的笔试题，蛮有意思的，就决心做做看。

一开始看到要支持 AND OR 等逻辑操作符，想来也要支持括号标明优先级了，就想到拿前几天 python-cn 社区介绍的 PLY 模块做个 parser。虽然是第一次用这个模块，但真的很好用，写 parser 用的时间很短，调试了几下，就能够支持比较复杂的表达式了，比如：

(age < 15 and sex == 0) or age > 30

整出来的语法树如下：  
or  
   and  
     ('<', 'age', 15)  
     ('==', 'sex', 0)  
   ('>', 'age', 30)

接下来在比较两棵树是否有子集关系的时候，遇到了问题。今天早上看到 qmigh（[http://qmigh.blogspot.com/][http_qmigh.blogspot.com]）的想法，启发了我。不过他提出的方案是把查询表达式“规范化”，这一步是比较难做的，需要用到离散数学的一些知识，实现起来比较烦。我思考之后，发现“规范化”只是为了将语法树转成两层的或与树，想到这一点之后，就可以不进行“规范化”了，只要将与或树的特性应用到语法树中即可。具体的判断方案我在代码里以注释的形式写了出来。

本题的解决方案后面的知识，SeasonLee 有一篇文章写得清晰，可供参考：从离散数学到编译原理--百姓网编程题后序（[http://www.cnblogs.com/SeasonLee/archive/2010/05/11/1731414.html][http_www.cnblogs.com_SeasonLee_archive_2010_05_11_1731414.html]）

现在这个方案可以实现比较复杂的表达式判断，不过不支持 NOT，也不支持 != 号，只支持 AND、OR、>、< 和 ==，可以使用 () 指定优先级。其实代码不长，约有 100 行是后面测试用的一些代码。

经王建硕先生同意，我把自己的方案公布到博客上，欢迎大家讨论和指正。

1 \# encoding:utf-8  
  2  
  3 **try**:  
  4   from ply import yacc  
  5   from ply import lex  
  6 **except** ImportError:  
  7   import sys  
  8   **print** "Please install PLY first."  
  9   **print** r"You can download it from here: [http://www.dabeaz.com/ply/ply-3.3.tar.gz][http_www.dabeaz.com_ply_ply-3.3.tar.gz]"  
 10   sys.exit(1)  
 11  
 12 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
 13 \#                lex  
 14 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
 15  
 16 \# 定义条件表达式的词法  
 17 tokens = \['FIELD', 'NUMBER', 'GT', 'EQ', 'LT', 'AND', 'OR', 'LPAREN', 'RPAREN'\]  
 18  
 19 t\_ignore = ' /t'  
 20 t\_FIELD = r'(?!and)(?!or)\[a-zA-Z\_\]\[a-zA-Z0-9\_\]\*'  
 21 t\_GT = r'>'  
 22 t\_EQ = r'=='  
 23 t\_LT = r'<'  
 24 t\_AND = r'and'  
 25 t\_OR = r'or'  
 26 t\_LPAREN = r'/('  
 27 t\_RPAREN = r'/)'  
 28  
 29 **def** t\_NUMBER(t):  
 30   r'/d+'  
 31   t.value = int(t.value)  
 32   **return** t  
 33  
 34 **def** t\_error(t):  
 35   **raise** TypeError("Unknow text '%s'"%t.value)  
 36  
 37 lex.lex()  
 38  
 39 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
 40 \#                yacc  
 41 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
 42  
 43 \# 用 BNF 定义条件表达式的语法，支持 AND OR，以及 () 的嵌套  
 44 **def** p\_expr4(p):  
 45   '''  
 46   expr :  
 47   '''  
 48  
 49 **def** p\_expr3(p):  
 50   '''  
 51   expr : LPAREN expr RPAREN  
 52   '''  
 53   p\[0\] = p\[2\]  
 54  
 55 **def** p\_expr2(p):  
 56   '''  
 57   expr : condi  
 58   '''  
 59   p\[0\] = p\[1\]  
 60  
 61 **def** p\_expr(p):  
 62   '''  
 63   expr : expr logic\_op expr  
 64   '''  
 65   p\[0\] = (p\[2\], p\[1\], p\[3\])  
 66  
 67 **def** p\_logic\_op(p):  
 68   '''  
 69   logic\_op : AND  
 70   logic\_op : OR  
 71   '''  
 72   p\[0\] = p\[1\]  
 73  
 74 **def** p\_condi(p):  
 75   '''condi : FIELD cmp\_op NUMBER'''  
 76   p\[0\] = (p\[2\], p\[1\], p\[3\])  
 77  
 78 \# for i in p:print i  
 79  
 80 **def** p\_cmp\_op(p):  
 81   '''  
 82   cmp\_op : GT  
 83   cmp\_op : EQ  
 84   cmp\_op : LT  
 85   '''  
 86   p\[0\] = p\[1\]  
 87   \#for i in p:print i  
 88  
 89 **def** p\_error(p):  
 90         **raise** TypeError("unknow text at %s"%p.value)  
 91  
 92 yacc.yacc()  
 93  
 94 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
 95 \#                util  
 96 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
 97  
 98 \# 以比较漂亮的形式打印语法树  
 99 INDENT = '  '  
100 **def** print\_tree(t, indent):  
101   **if** **not** t:  
102     **print** indent + str(t)  
103     **return**  
104   op, l, r = t  
105   **if** op **in** ('and', 'or'):  
106     **print** indent + op  
107     print\_tree(l, indent + INDENT)  
108     print\_tree(r, indent + INDENT)  
109   **else**:  
110     **print** indent + str(t)  
111  
112 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
113 \#                judge  
114 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
115 OP = ('>', '<', '==')  
116 AND = 'and'  
117 OR = 'or'  
118  
119 \# 对 age < 18 和 age < 10 这种原子条件表达式对行判断  
120 \# 首先要求字段名要相同，否则返回 false  
121 \# 然后是根据表达式的比较运算符进行分情况比较  
122 **def** is\_subset\_atom\_atom(left, right):  
123   **assert** left **and** right  
124   lop, ll, lr = left  
125   rop, rl, rr = right  
126   **assert** lop **in** OP **and** rop **in** OP  
127   **if** ll != rl:  
128     **return** False  
129   **if** lop == rop == '>':  
130     **return** lr >= rr  
131   **elif** lop == rop == '<':  
132     **return** lr <= rr  
133   **elif** lop == rop == '==':  
134     **return** lr == rr  
135   **elif** lop == '>':  
136     **return** False  
137   **elif** lop == '<':  
138     **return** False  
139   **elif** lop == '==':  
140     **if** rop == '>':  
141       **return** lr > rr  
142     **else**: \# '<'  
143       **return** lr < rr  
144   **else**:  
145     **raise** RuntimeError('Error')  
146  
147 \# 比较 age < 10 和 age < 10 and sex == 0 这种形式的复合表达式  
148 \# 这种情况下要求左式必须是右式的两个子式的子集才返回为 true  
149 **def** is\_subset\_atom\_and(left, right):  
150   **assert** left **and** right  
151   rop, rl, rr = right  
152   **global** is\_subset  
153   **return** is\_subset(left, rl) **and** is\_subset(left, rr)  
154  
155 \# 比较 age < 10 和 age < 10 or sex == 0 这种形式的复杂表达式  
156 \# 这种情况下只需要左式是右式中的任一子式的子集即返回 true  
157 **def** is\_subset\_atom\_or(left, right):  
158   **assert** left **and** right  
159   rop, rl, rr = right  
160   **global** is\_subset  
161   **return** is\_subset(left, rl) **or** is\_subset(left, rr)  
162  
163 \# 比较 age < 10 and sex == 0 和 age < 10 这种复合表达式  
164 \# 要求左式的任一子式为右式的子集即返回 true  
165 **def** is\_subset\_and\_atom(left, right):  
166   **assert** left **and** right  
167   lop, ll, lr = left  
168   **global** is\_subset  
169   **return** is\_subset(ll, right) **or** is\_subset(lr, right)  
170  
171 \# 比较 age < 10 and sex == 0 和 age < 18 and sex == 1 这种复合表达式  
172 \# 要求左式的任一子式必须都是右式的\*某一\*子式的子集才返回 true  
173 **def** is\_subset\_and\_and(left, right):  
174   **assert** left **and** right  
175   lop, ll, lr = left  
176   rop, rl, rr = right  
177   **global** is\_subset  
178   lresult = is\_subset(ll, rl) **or** is\_subset(ll, rr)  
179   rresult = is\_subset(lr, rl) **or** is\_subset(lr, rr)  
180   **return** lresult **and** rresult  
181  
182 \# 比较 age < 10 and sex == 0 和 age < 10 or sex == 1 这种复合表达式  
183 \# 要求整个左式必须是右式的某一子式为真才返回 true  
184 **def** is\_subset\_and\_or(left, right):  
185   **assert** left **and** right  
186   lop, ll, lr = left  
187   rop, rl, rr = right  
188   **global** is\_subset  
189   **return** is\_subset(left, rl) **or** is\_subset(left, rr)  
190  
191 \# 比较 age < 10 or sex == 0 和 age < 10 这种复合表达式  
192 \# 要求左式的任一子式都必须是右式的子集才返回 true  
193 **def** is\_subset\_or\_atom(left, right):  
194   **assert** left **and** right  
195   lop, ll, lr = left  
196   **global** is\_subset  
197   **return** is\_subset(ll, right) **and** is\_subset(lr, right)  
198  
199 \# 比较 age < 10 or sex == 0 和 age < 10 and sex == 0 这种复合表达式  
200 \# 与 is\_subset\_or\_atom 是一样的。  
201 **def** is\_subset\_or\_and(left, right):  
202   **return** is\_subset\_or\_atom(left, right)  
203  
204 \# 比较 age < 10 or sex == 0 和 age < 10 or sex == 0 这种复合表达式  
205 \# 与 is\_subset\_or\_atom 是一样的。  
206 **def** is\_subset\_or\_or(left, right):  
207   **return** is\_subset\_or\_atom(left, right)  
208  
209 \# 根据左右式的操作符分派给上述的判断函数  
210 **def** is\_subset(left, right):  
211   **assert** left **and** right  
212   **print** 'left:',left  
213   **print** 'right:',right  
214   lop, ll, lr = left  
215   rop, rl, rr = right  
216   **if** lop **in** OP:  
217     **if** rop **in** OP:  
218       **return** is\_subset\_atom\_atom(left, right)  
219     **elif** rop == AND:  
220       **return** is\_subset\_atom\_and(left, right)  
221     **elif** rop == OR:  
222       **return** is\_subset\_atom\_or(left, right)  
223     **raise** RuntimeError('Error')  
224   **elif** lop == 'and':  
225     **if** rop **in** OP:  
226       **return** is\_subset\_and\_atom(left, right)  
227     **elif** rop == AND:  
228       **return** is\_subset\_and\_and(left, right)  
229     **elif** rop == OR:  
230       **return** is\_subset\_and\_or(left, right)  
231     **else**:  
232       **raise** RuntimeError('Error')  
233   **elif** lop == 'or':  
234     **if** rop **in** OP:  
235       **return** is\_subset\_or\_atom(left, right)  
236     **elif** rop == AND:  
237       **return** is\_subset\_or\_and(left, right)  
238     **elif** rop == OR:  
239       **return** is\_subset\_or\_or(left, right)  
240     **else**:  
241       **raise** RuntimeError('Error')  
242   **else**:  
243     **raise** RuntimeError('Error')  
244  
245 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
246 \#                query  
247 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
248 **class** Query(object):  
249   **def** \_\_init\_\_(self, q):  
250     self.\_q = q  
251     self.\_tree = yacc.parse(q)  
252     **assert** self.\_tree  
253       
254   **def** is\_subset(self, other):  
255     **if** **not** self.\_tree:  
256       **return** False  
257     **if** **not** other.\_tree:  
258       **return** True  
259     **return** is\_subset(self.\_tree, other.\_tree)  
260  
261 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
262 \#                test  
263 \#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#  
264 **if** \_\_name\_\_ == '\_\_main\_\_':  
265   t0 = Query('age > 40') \# 中年人  
266   t1 = Query('age > 18') \# 成年人  
267   **print** t0.is\_subset(t0)  
268   **print** t0.is\_subset(t1)  
269   **print** t1.is\_subset(t0)  
270   **print** t1.is\_subset(t1)  
271   **print** '-'\*30  
272     
273   t2 = Query('age > 18 and weight < 100') \# 成年瘦子  
274   t3 = Query('age > 18 or weight < 100') \# 成年人，或体重小于 100  
275   **print** t0.is\_subset(t2)  
276   **print** t0.is\_subset(t3)  
277  
278   **print** t2.is\_subset(t0)  
279   **print** t2.is\_subset(t3)  
280     
281   **print** t3.is\_subset(t2)  
282  
283   r0 = Query('age > 30 and sex == 0')  
284   r1 = Query('age > 40 and sex == 0')  
285  
286   **print** r0.is\_subset(r1)  
287   **print** r1.is\_subset(r0)  
288   **print** '='\*30  
289     
290   t0 = Query('(age < 15 and sex == 0) or age > 30')  
291   t1 = Query('age < 7')  
292   t2 = Query('age < 18')  
293   print\_tree(t0.\_tree, '')  
294   **print** '\*'\*30  
295   **assert** 't0 is subset of t0:' **and** t0.is\_subset(t0) == True  
296   **print** '-'\*30  
297   **assert** 't0 is subset of t1:' **and** t0.is\_subset(t1) == False  
298   **print** '-'\*30  
299   **assert** 't1 is subset of t0:' **and** t1.is\_subset(t0) == False  
300   **print** '-'\*30  
301   **assert** 't2 is subset of t0:' **and** t2.is\_subset(t0) == False  
302   **print** '-'\*30  
303     
304   q0 = Query('age < 15')  
305   q1 = Query('age > 30')  
306   q2 = Query('age > 18')  
307   q3 = Query('age > 40')  
308   q4 = Query('age > 30 and sex == 0')  
309     
310  
311   **assert** 'q0 is subset of q0:' **and** q0.is\_subset(q0) == True  
312   **print** '-'\*30  
313   **assert** 'q0 is subset of q1:' **and** q0.is\_subset(q1) == False  
314   **print** '-'\*30  
315   **assert** 'q0 is subset of q2:' **and** q0.is\_subset(q2) == False  
316   **print** '-'\*30  
317   **assert** 'q0 is subset of q3:' **and** q0.is\_subset(q3) == False  
318   **print** '-'\*30  
319   **assert** 'q0 is subset of q4:' **and** q0.is\_subset(q4) == False  
320   **print** '-'\*30  
321   **print**  
322  
323   **assert** 'q1 is subset of q0:' **and** q1.is\_subset(q0) == False  
324   **print** '-'\*30  
325   **assert** 'q1 is subset of q1:' **and** q1.is\_subset(q1) == True  
326   **print** '-'\*30  
327   **assert** 'q1 is subset of q2:' **and** q1.is\_subset(q2) == True  
328   **print** '-'\*30  
329   **assert** 'q1 is subset of q3:' **and** q1.is\_subset(q3) == False  
330   **print** '-'\*30  
331   **assert** 'q1 is subset of q4:' **and** q1.is\_subset(q4) == False  
332   **print** '-'\*30  
333   **print**  
334  
335   **assert** 'q2 is subset of q0:' **and** q2.is\_subset(q0) == False  
336   **print** '-'\*30  
337   **assert** 'q2 is subset of q1:' **and** q2.is\_subset(q1) == False  
338   **print** '-'\*30  
339   **assert** 'q2 is subset of q2:' **and** q2.is\_subset(q2) == True  
340   **print** '-'\*30  
341   **assert** 'q2 is subset of q3:' **and** q2.is\_subset(q3) == False  
342   **print** '-'\*30  
343   **assert** 'q2 is subset of q4:' **and** q2.is\_subset(q4) == False  
344   **print** '-'\*30  
345   **print**  
346  
347   **assert** 'q3 is subset of q0:' **and** q3.is\_subset(q0) == False  
348   **print** '-'\*30  
349   **assert** 'q3 is subset of q1:' **and** q3.is\_subset(q1) == True  
350   **print** '-'\*30  
351   **assert** 'q3 is subset of q2:' **and** q3.is\_subset(q2) == True  
352   **print** '-'\*30  
353   **assert** 'q3 is subset of q3:' **and** q3.is\_subset(q3) == True  
354   **print** '-'\*30  
355   **assert** 'q3 is subset of q4:' **and** q3.is\_subset(q4) == False  
356   **print** '-'\*30  
357   **print**  
358  
359   **assert** 'q4 is subset of q0:' **and** q4.is\_subset(q0) == False  
360   **print** '-'\*30  
361   **assert** 'q4 is subset of q1:' **and** q4.is\_subset(q1) == True  
362   **print** '-'\*30  
363   **assert** 'q4 is subset of q2:' **and** q4.is\_subset(q2) == True  
364   **print** '-'\*30  
365   **assert** 'q4 is subset of q3:' **and** q4.is\_subset(q3) == False  
366   **print** '-'\*30  
367   **assert** 'q4 is subset of q4:' **and** q4.is\_subset(q4) == True  
368   **print** '-'\*30  
369  
370

[http_laiyonghao.com]: http://laiyonghao.com
[http_home.wangjianshuo.com_cn_20100505_ccceeieeaece.htm]: http://home.wangjianshuo.com/cn/20100505_ccceeieeaece.htm
[http_qmigh.blogspot.com]: http://qmigh.blogspot.com/
[http_www.cnblogs.com_SeasonLee_archive_2010_05_11_1731414.html]: http://www.cnblogs.com/SeasonLee/archive/2010/05/11/1731414.html
[http_www.dabeaz.com_ply_ply-3.3.tar.gz]: http://www.dabeaz.com/ply/ply-3.3.tar.gz