鱼C论坛

 找回密码
 立即注册
查看: 4133|回复: 11

[技术交流] 鱼C论坛Python精英挑战赛(第二季04期)

[复制链接]
发表于 2017-8-17 08:18:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-8-20 23:26 编辑

鱼C论坛Python精英挑战赛第二季赛程已经过半啦!感谢广大鱼油的热情参与!

本季挑战赛依旧会有精彩的题目供大家挑战,大量鱼币奖励等你赢取!


                               
登录/注册后可看大图


本期题目:文献检索之关键词检索

使用过文献检索系统的同学都知道,在文献检索中我们可以使用关键词进行检索,而且关键词与关键词之间可以用“与”、“或”、“非”的逻辑关系进行组合,并且可以用括号改变“与或非”的优先级顺序。

通常,我们用“&”表示“与”,其表示的含义为两个关键词同时出现在检索的文本中;用“|”表示“或”,其表示的含义为两个关键词有任一个出现在检索的文本中;用“!”表示“非”,其表示的含义为“!”后紧跟的一个关键词不出现在检索的文本中。它们三者默认的优先级顺序为“!”>“&”> “|”,我们可以用括号改变它们之间的优先级顺序。关键词与“&|!”之间用空格隔开,“!”之后的关键词可以省略空格。

例如,被检索的文本txt = 'one apple with two leaves, one is green and the other is yellow.'
我们用s1 = '(apple | others) & two' 进行搜索,返回的结果应该为 True
我们用s4 = '!green & (ones | two)' 进行搜索,返回的结果应该为 False

现在,请你设计一个函数,给定一个关键词字符串string,在txt中搜索是否能匹配,返回True或者False。
  1. def search(string, txt):
  2.         '''Your code here!'''
  3.         return True or False
复制代码


为了使更多鱼油能参与比赛,本题分为三个难度:
#简单难度:关键词字符串中没有括号
#中等难度:关键词字符串中只有单层括号,括号不嵌套
#困难难度:关键词字符串中有多层嵌套括号

备注:尽量避免使用eval函数,因为服务器上运行不了。

#Test sample
txt = 'one apple with two leaves, one is green and the other is yellow.'
s1 = '(apple | others) & two' #True
s2 = 'one & yellow & leaf' #False
s3 = '(!three | one & four) & !five' #True
s4 = '!green & (ones | two)' #False
s5 = '(big | !apple | the) & ((!yellow | !green) | others)' #False

比赛规则:
要求程序输出正确,运行效率高,并且程序简练优雅的获胜。比赛截止日期为8月20日24时。

优胜者优先从困难难度中选择产生,奖励100鱼币,由@小甲鱼 老师倾情赞助!

@冬雪雪冬 @SixPy @~风介~

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-8-17 12:22:37 | 显示全部楼层
题目还是有一定难度的,感觉把检索式一一解析,再去运算还是很复杂的。干脆直接把检索式改为python的逻辑运算式得了,这样也不用考虑多层括号的嵌套了。
  1. def search(string, txt):
  2.     string = string.replace(' ', '')
  3.     newstr = ''
  4.     sign = '()!|&'
  5.     if string[0] not in sign:
  6.         newstr += '"' + string[0]
  7.     else:
  8.         newstr += string[0]
  9.     for i in range(1, len(string) - 1):
  10.         if string[i] not in sign and string[i - 1] in sign:
  11.             newstr += '"' + string[i]
  12.         elif string[i] not in sign and string[i + 1] in sign:
  13.             newstr += string[i] + '" in txt'
  14.         else:
  15.             newstr += string[i]
  16.     if string[-1] not in sign:
  17.         newstr += string[-1] + '" in txt'
  18.     else:
  19.         newstr += string[-1]
  20.     newstr = newstr.replace('!', ' not ')
  21.     newstr = newstr.replace('&', ' and ')
  22.     newstr = newstr.replace('|', ' or ')
  23.     return eval(newstr)

  24. txt = 'one apple with two leaves, one is green and the other is yellow.'
  25. s1 = '(apple | others) & two' #True
  26. s2 = 'one & yellow & leaf' #False
  27. s3 = '(!three | one & four) & !five' #True
  28. s4 = '!green & (ones | two)' #False
  29. s5 = '(big | !apple | the) & ((!yellow | !green) | others)' #False        
  30. print(search(s1, txt))
  31. print(search(s2, txt))
  32. print(search(s3, txt))
  33. print(search(s4, txt))
  34. print(search(s5, txt))
复制代码
  1. True
  2. False
  3. True
  4. False
  5. False
复制代码

这几个结果是正确的,不知是否有没考虑到的情况。

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 在自己电脑上运行通过的,但是服务器上不支.

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-17 13:28:14 | 显示全部楼层
本帖最后由 小Q学Python 于 2017-8-17 13:31 编辑

先粘个耍赖的方法
  1. def search(string, txt):
  2.     a = ''
  3.     flag1,flag2 = 0, 0
  4.     for i in string:
  5.         if i.isalnum() and flag1 == 0:
  6.             flag1 = 1
  7.             a+='\''
  8.         if not i.isalnum() and flag1 == 1:
  9.             if flag2 == 0:
  10.                 a+='\' in txt'
  11.             else:
  12.                 a+='\' not in txt'
  13.                 flag2 = 0
  14.             flag1 = 0
  15.         if i == '|':
  16.             a+=' or '
  17.             continue
  18.         if i == '&':
  19.             a+=' and '
  20.             continue
  21.         if i =='!':
  22.             flag2 = 1
  23.             continue
  24.         a += i
  25.     if flag2 == 1:
  26.         a+='\' not in txt'
  27.     elif flag1 == 1:
  28.         a+='\' in txt'
  29.     return eval(a)

  30. txt = 'one apple with two leaves, one is green and the other is yellow.'
  31. s1 = '(apple | others) & two' #True
  32. s2 = 'one & yellow & leaf' #False
  33. s3 = '(!three | one & four) & !five' #True
  34. s4 = '!green & (ones | two)' #False
  35. s5 = '(big | !apple | the) & ((!yellow | !green) | others)' #False

  36. print(search(s1,txt))
  37. print(search(s2,txt))
  38. print(search(s3,txt))
  39. print(search(s4,txt))
  40. print(search(s5,txt))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,eval函数在服务器上运行不了

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-17 15:22:38 | 显示全部楼层
本帖最后由 小锟 于 2017-8-20 23:59 编辑
  1.         
  2. #将中缀表达式转化为后缀表达式,即逆波兰表达式
  3. def conver_fun(list1) :
  4.     #确定运算符优先级
  5.     first={'(':1 , '|':3 , '&':5 ,'!':7 }
  6.     a = '|&!()'
  7.     #定义列表来存储运算符以及文本
  8.     txt = []
  9.     yunsuanfu = []
  10.     for i in list1:
  11.         #如果不在运算符,加入txt
  12.         if i not in a :
  13.             txt.append(i)
  14.         elif len(yunsuanfu) == 0 or i == '(' : #加入左括号
  15.             yunsuanfu.append(i)
  16.         elif i == ')': #出现右括号
  17.             #弹出‘(’之后的运算符
  18.             while len(yunsuanfu) and yunsuanfu[-1] != '(':
  19.                 txt.append(yunsuanfu.pop())
  20.             yunsuanfu.pop() #弹出左括号
  21.         else: #判断优先级
  22.             #优先级大的先弹出去加入到文本中
  23.             while (len(yunsuanfu)) and first[yunsuanfu[-1]] >= first[i]:
  24.                 txt.append(yunsuanfu.pop())
  25.             yunsuanfu.append(i)
  26.     #将剩下的运算符加入
  27.     while  len(yunsuanfu) :
  28.         txt.append(yunsuanfu.pop())

  29.     return txt

  30. #判断!运算符 返回0或1 ,判断单目运算符
  31. def yunsuan1(one , txt):
  32.     if type(one) == int :
  33.         if one == 1 :
  34.             one = 0
  35.         else :
  36.             one = 1
  37.     if type(one) != int :
  38.         if one in txt :
  39.             one = 0
  40.         else :
  41.             one = 1
  42.     return one
  43. #判断&|运算符,即双目运算符
  44. def yunsuan2(one , two ,fuhao ,txt):
  45.     if type(one) != int :
  46.         if one in txt :
  47.             one = 1
  48.         else :
  49.             one = 0
  50.     if type(two) != int :
  51.         if two in txt :
  52.             two = 1
  53.         else :
  54.             two = 0
  55.     if fuhao == '&':        
  56.         return one and two
  57.     if fuhao == '|' :
  58.         return one or two

  59.    
  60.    
  61. #计算后缀表达式
  62. def count_result(list1 , txt):
  63.     a = '|&!'
  64.     b = []
  65.     for i in list1:
  66.         if i not in a:
  67.             b.append(i)
  68.         elif i != '!':
  69.             #双目运算符,要弹两个元素来运算
  70.             one = b.pop()
  71.             two = b.pop()
  72.             new = yunsuan2(one,two,i ,txt)
  73.             b.append(new)
  74.         else:
  75.             one = b.pop()
  76.             new = yunsuan1(one ,txt)
  77.             b.append(new)
  78.     return b
  79.         



  80. txt = 'one apple with two leaves, one is green and the other is yellow.'
  81. s1 = '(apple | others) & two' #True
  82. s2 = 'one & yellow & leaf' #False
  83. s3 = '(!three | one & four) & !five' #True
  84. s4 = '!green & (ones | two)' #False
  85. s5 = '(big | !apple | the) & ((!yellow | !green) | others)' #False
  86. def search(string, txt):
  87.     #将判断的文本和运算符分割开,这里默认为!后面没有空格,直接是简写的
  88.     a = list(string)
  89.     for i in range(len(a)):
  90.         if a[i] in '!(':
  91.             a[i] += ' '
  92.         elif  a[i] in ')':
  93.             a[i] = ' ' +  a[i]
  94.     a = ''.join(a)
  95.     a = a.split(' ')

  96.     list1 = conver_fun(a)      
  97.     result = count_result(list1 , txt)
  98.     return True if result[0] else False


  99. for i in [s1 ,s2,s3,s4,s5]:
  100.     print(search(i,txt))


复制代码



刚看到这题的时候就想到了逆波兰表达式,但是有可能表达不清楚,大家随意看看

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,写得好长,加点注释呗^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-17 21:35:01 | 显示全部楼层
这楼我占了,我选择简单模式~

点评

我很赞同!: 5.0
我很赞同!: 5
期待你的解答  发表于 2017-8-17 21:49
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-18 09:24:11 | 显示全部楼层
本帖最后由 小剑剑 于 2017-8-18 11:26 编辑
  1. def scanf(string,findex,rindex):
  2.     t=0
  3.     while string[findex]==' ':
  4.         findex+=1
  5.     temp=findex
  6.     while findex<rindex:
  7.         if string[findex]=='(':
  8.             t-=1
  9.         elif string[findex]==')':
  10.             t+=1
  11.         elif string[findex]==' ':
  12.             if t==0:
  13.                 break
  14.         findex+=1
  15.     return (temp,findex)

  16. def calc(string,findex,rindex,txt):
  17.     positive=True
  18.     while string[findex]=='!':
  19.         positive=not positive
  20.         findex+=1
  21.     bracket=False
  22.     if string[findex]=='(':
  23.         findex+=1
  24.         rindex-=1
  25.         bracket=True
  26.     if not bracket:
  27.         if not positive:
  28.             result=not string[findex:rindex] in txt
  29.         else :
  30.             result =string[findex:rindex] in txt
  31.         return result
  32.     index=findex
  33.     cl=[]
  34.     while index<rindex:
  35.         cl.append(scanf(string,index,rindex))
  36.         index=cl[-1][1]
  37.     if len(cl)==1:
  38.         return calc(string,cl[0][0],cl[0][1],txt)
  39.     temp=cl.pop()
  40.     result=calc(string,temp[0],temp[1],txt)
  41.     while cl:
  42.         symbol=string[cl.pop()[0]]
  43.         if symbol=='|':
  44.             if result==True:
  45.                 return True
  46.             else:
  47.                 temp=cl.pop()
  48.                 result=calc(string,temp[0],temp[1],txt)
  49.                 continue
  50.         temp=cl.pop()
  51.         temp=calc(string,temp[0],temp[1],txt)
  52.         if temp==False:
  53.             result=False
  54.             
  55.     if not positive:
  56.         result = not result
  57.     return result
  58.         
  59. def func(string,txt):
  60.     string=string.strip()
  61.     string='('+string+')'
  62.     return calc(string,0,len(string),txt)
复制代码


恭喜大大升职


  1. ''' scanf 顾名思义就是扫描
  2.     例如  scanf('(apple | others) & two',0,len('(apple | others) & two'))
  3.     就返回 (apple | others)的索引范围
  4.     scanf('(apple | others) & two',16,len)
  5.     就返回 & 的索引范围
  6.     scanf('(apple | others) & two',18,len)
  7.     就返回 two 的索引范围
  8. '''
  9. def scanf(string,findex,rindex):
  10.     t=0
  11.     while string[findex]==' ':
  12.         findex+=1
  13.     temp=findex
  14.     while findex<rindex:
  15.         if string[findex]=='(':
  16.             t-=1
  17.         elif string[findex]==')':
  18.             t+=1
  19.         elif string[findex]==' ':
  20.             if t==0:
  21.                 break
  22.         findex+=1
  23.     return (temp,findex)

  24. def calc(string,findex,rindex,txt):
  25.     positive=True #开头是否有!可以跳过多个!
  26.     while string[findex]=='!':
  27.         positive=not positive
  28.         findex+=1#掉过!
  29.     bracket=False #括号有括号就说明这个字符串可能有运算符
  30.     if string[findex]=='(':
  31.         findex+=1
  32.         rindex-=1
  33.         bracket=True
  34.     #没有括号 那就是一个没有运算符的字符串了 可以直接查找了
  35.     if not bracket:
  36.         if not positive:
  37.             result=not string[findex:rindex] in txt
  38.         else :
  39.             result =string[findex:rindex] in txt
  40.         return result
  41.     index=findex#好像这个index是多余的 直接用findex就好了
  42.     '''
  43.     cl保存扫描的返回值 必然是
  44.     一段可以转为bool值的字符串 和 一个运算符轮流出现
  45. '''
  46.     cl=[]
  47.     while index<rindex:
  48.         cl.append(scanf(string,index,rindex))
  49.         index=cl[-1][1]
  50.     '''
  51.     拿到可以转为bool值的字符串 和 运算符
  52.     cl只有一个元素 那么
  53.     这个元素必然是可以转为bool值的字符串
  54. '''
  55.     if len(cl)==1:
  56.         return calc(string,cl[0][0],cl[0][1],txt)

  57.     '''
  58.     cl 不止一个值,一个个弹出来计算
  59. '''
  60.     temp=cl.pop()
  61.     result=calc(string,temp[0],temp[1],txt)
  62.     while cl:
  63.         symbol=string[cl.pop()[0]]#运算符
  64.         if symbol=='|':
  65.             if result==True:#或运算 一个是真后面不用算了
  66.                 return True
  67.             else:#或运算 一个值是假 直接计算下一个字符串
  68.                 temp=cl.pop()
  69.                 result=calc(string,temp[0],temp[1],txt)
  70.                 continue
  71.         '''
  72.         因为& 和 | 的优先级问题
  73.         为了防止cl里面还有 | 所以只好 & 一个个算了
  74. '''
  75.         temp=cl.pop()
  76.         temp=calc(string,temp[0],temp[1],txt)
  77.         if temp==False:
  78.             result=False
  79.             
  80.     if not positive:
  81.         result = not result
  82.     return result
  83.         
  84. def func(string,txt):
  85.     '''
  86.     去掉两边的空格
  87.     加上括号是为了兼容
  88.     如果没有括号会出错
  89.     例如 'one & yellow'
  90.     会被calc看作是一个没有运算符的字符串了
  91.     但是里面还有个 &
  92. '''
  93.     string=string.strip()
  94.     string='('+string+')'
  95.     return calc(string,0,len(string),txt)
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 为鱼油服务^_^ 写下注释呗!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-18 10:10:22 | 显示全部楼层
本帖最后由 lovesword 于 2017-8-18 10:13 编辑
  1. #coding=utf-8
  2. import re
  3. txt = 'one apple with two leaves, one is green and the other is yellow.'

  4. def multiple_replace(text, idict):
  5.     rx = re.compile('|'.join(map(re.escape, idict)))
  6.     def one_xlat(match):
  7.         return idict[match.group(0)]
  8.     return rx.sub(one_xlat, text)

  9. def search(string, txt):
  10.     idict = {i: ['False', 'True'][i in re.findall(r"[\w']+", txt)] for i in re.findall(r"[\w']+", string)}
  11.     string = multiple_replace(string, idict)
  12.     string= string.replace(' ','').replace('!False','True').replace('!True','False')
  13.     res =  eval(string)
  14.     return res

  15. s1 = '(apple | others) & two' #True
  16. s2 = 'one & yellow & leaf' #False
  17. s3 = '(!three | one & four) & !five' #True
  18. s4 = '!green & (ones | two)' #False
  19. s5 = '(big | !apple | the) & ((!yellow | !green) | others)' #False


  20. for s in [s1,s2,s3,s4,s5]:
  21.     print s,'==>', search(s, txt)
复制代码

-------result---------------------
(apple | others) & two ==> True
one & yellow & leaf ==> False
(!three | one & four) & !five ==> True
!green & (ones | two) ==> False
(big | !apple | the) & ((!yellow | !green) | others) ==> False



好难,不知道逻辑对不对,投机取巧法,就是把搜索关键字串的单词根据txt是否存在替换成 False 或者True,处理一哈 !False ,!True 的情况,(这里没考虑 !False 之间有空格的情况。)
例如:(big | !apple | the) & ((!yellow | !green) | others) ==> (False|False|True)&((False|False)|False)
最后eval(' (False|False|True)&((False|False)|False)') 得到结果(楼主千叮万嘱不要使用eval ,那只有顶风作案了,~~!)
另外 multiple_replace 这个函数 网上找的。

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,顶风作案^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-19 19:23:21 | 显示全部楼层
本帖最后由 gunjang 于 2017-8-20 12:30 编辑
  1. def search(string, txt):
  2.         v, i = mysearch(string+'=', txt)
  3.         return v

  4. def mysearch(str, txt, indexofstr=0, endchar='='): #return true/false and index
  5.         op = '#'
  6.         v = True
  7.         while str[indexofstr] != endchar:
  8.                 if str[indexofstr] == '!': #not
  9.                         op = '!'
  10.                 elif str[indexofstr] == '&': #and
  11.                         if v == False:
  12.                                 #short-circuit logic
  13.                                 #False and xx and xxx == False
  14.                                 #skip all & until end of string or find "|",
  15.                                 bracketlevel = 0
  16.                                 for i in range(indexofstr+1, len(str)):
  17.                                         #skip bracket
  18.                                         if (str[i] == endchar) and (bracketlevel==0):
  19.                                                 break
  20.                                         if (str[i] == '|') and (bracketlevel==0): #bracket
  21.                                                 break
  22.                                         if str[i] == '(':
  23.                                                 bracketlevel += 1
  24.                                         elif str[i] == ')':
  25.                                                 bracketlevel -= 1
  26.                                 indexofstr = i
  27.                                 op = '#'
  28.                                 continue

  29.                         op = '&'
  30.                 elif str[indexofstr] == '|': # or
  31.                         if v == True: #true or x or xx = True
  32.                                 #short-circuit logic
  33.                                 #skip to end
  34.                                 if endchar == '=':
  35.                                         indexofstr = len(str)
  36.                                         break
  37.                                 #else skip to right bracket “)"
  38.                                 bracketlevel = 0
  39.                                 for i in range(indexofstr+1, len(str)):
  40.                                         #skip bracket
  41.                                         if (str[i] == endchar) and (bracketlevel==0):
  42.                                                 break
  43.                                         if str[i] == '(':
  44.                                                 bracketlevel += 1
  45.                                         elif str[i] == ')':
  46.                                                 bracketlevel -= 1
  47.                                 indexofstr = i
  48.                                 break

  49.                         op = '|'
  50.                 elif str[indexofstr] == ' ':
  51.                         pass
  52.                 elif str[indexofstr] == '(':
  53.                         v, indexofstr = mysearch(str, txt, indexofstr+1, ')')
  54.                         if op == '!':
  55.                                 v = not v
  56.                                 op = '#'
  57.                 else:
  58.                         #get token
  59.                         firstindex = indexofstr
  60.                         while (indexofstr < len(str)) and not (str[indexofstr] in set('()!&| =')):
  61.                                 indexofstr += 1
  62.                         w = str[firstindex:indexofstr]
  63.                         v = txt.find(w) > -1
  64.                         if op == '!':
  65.                                 v = not v
  66.                                 op = '#'
  67.                         continue

  68.                 indexofstr += 1
  69.         return v, indexofstr
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,写下注释呗!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-20 19:41:22 | 显示全部楼层
最高难度级别!!今天才看见

  1. import re


  2. def search(string, txt):

  3.     pattern = re.compile(r'[^!&|() ]+')
  4.     def changeKeywords(string, txt):
  5.         '''
  6.         将关键字转换为0或1
  7.         例如
  8.         txt = 'one apple with two leaves, one is green and the other is yellow.'
  9.         s1 = '(apple | others) & two'
  10.         转换后 string ='(1 | 0) & 1'
  11.         '''
  12.         string = ' ' + string + ' '
  13.         keywords = pattern.findall(string)
  14.         for each in keywords:
  15.             if each in txt:
  16.                 string = re.sub('([!&|() ])(%s)([!&|() ])' % each, '\g<1>1\g<3>', string)
  17.             else:
  18.                 string = re.sub('([!&|() ])(%s)([!&|() ])' % each, '\g<1>0\g<3>', string)
  19.         string = string.replace(' ', '')
  20.         return string

  21.     operatorPrecedence = {
  22.         '(': 0,
  23.         ')': 0,
  24.         '|': 1,
  25.         '&': 2,
  26.         '!': 3
  27.     }

  28.     def postfixConvert(exp):
  29.         '''''
  30.         将表达式字符串,转为后缀表达式
  31.         如exp = "1+2*(3-1)-4"
  32.         转换为:postfix = ['1', '2', '3', '1', '-', '*', '+', '4', '-']
  33.         '''
  34.         stack = []  # 运算符栈,存放运算符
  35.         postfix = []  # 后缀表达式栈
  36.         for char in exp:
  37.             #        print char, stack, postfix
  38.             if char not in operatorPrecedence:  # 非符号,直接进栈
  39.                 postfix.append(char)
  40.             else:
  41.                 if len(stack) == 0:  # 若是运算符栈啥也没有,直接将运算符进栈
  42.                     stack.append(char)
  43.                 else:
  44.                     if char == "(":
  45.                         stack.append(char)
  46.                     elif char == ")":  # 遇到了右括号,运算符出栈到postfix中,并且将左括号出栈
  47.                         while stack[-1] != "(":
  48.                             postfix.append(stack.pop())
  49.                         stack.pop()

  50.                     elif operatorPrecedence[char] > operatorPrecedence[stack[-1]]:
  51.                         # 只要优先级数字大,那么就继续追加
  52.                         stack.append(char)
  53.                     else:
  54.                         while len(stack) != 0:
  55.                             if stack[-1] == "(":  # 运算符栈一直出栈,直到遇到了左括号或者长度为0
  56.                                 break
  57.                             # 将运算符栈的运算符,依次出栈放到表达式栈里面
  58.                             postfix.append(stack.pop())
  59.                         stack.append(char)  # 并且将当前符号追放到符号栈里面

  60.         while len(stack) != 0:  # 如果符号站里面还有元素,就直接将其出栈到表达式栈里面
  61.             postfix.append(stack.pop())
  62.         return postfix

  63.     def calculate(num1, op, num2='0'):
  64.         if not num1.isdigit() and not num2.isdigit():
  65.             raise "num error"
  66.         else:
  67.             num1 = int(num1)
  68.             num2 = int(num2)
  69.         if op == "&":
  70.             return int(num1 and num2)
  71.         elif op == "|":
  72.             return int(num1 or num2)
  73.         elif op == "!":
  74.             return int(not num1)
  75.         else:
  76.             raise "op error"

  77.     def calExpressionTree(postfix):
  78.         stack = []
  79.         for char in postfix:
  80.             stack.append(char)
  81.             if char in "&|":
  82.                 op = stack.pop()
  83.                 num2 = stack.pop()
  84.                 num1 = stack.pop()
  85.                 value = calculate(num1, op, num2)
  86.                 value = str(value)  # 计算结果是数值类型,将其化为字符串类型
  87.                 stack.append(value)
  88.             elif char == '!':
  89.                 op = stack.pop()
  90.                 num1 = stack.pop()
  91.                 value = calculate(num1, op)
  92.                 value = str(value)
  93.                 stack.append(value)
  94.         return bool(int(stack[0]))

  95.     string = changeKeywords(string, txt)
  96.     postfix = postfixConvert(string)
  97.     res = calExpressionTree(postfix)
  98.     return res


  99. if __name__ == '__main__':
  100.     txt = 'one apple with two leaves, one is green and the other is yellow.'

  101.     s1 = '(apple | others) & two'                               # True
  102.     s2 = 'one & yellow & leaf'                                  # False
  103.     s3 = '(!three | one & four) & !five'                        # True
  104.     s4 = '!green & (ones | two)'                                # False
  105.     s5 = '(big | !apple | the) & ((!yellow | !green) | others)' # False

  106.     s6 = '!(apple & other) | !apple & !(yellow | green)'

  107.     print(search(s1, txt))
  108.     print(search(s2, txt))
  109.     print(search(s3, txt))
  110.     print(search(s4, txt))
  111.     print(search(s5, txt))
  112.     print(search(s6, txt))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,写得好长!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-21 00:15:33 | 显示全部楼层
晚上刚注册就弹出这个窗口,本来python刚跟着小甲鱼视频学了一部分,然后整个晚上都在搞这道题,终于搞出来了,全部测试过关,有些许成就感了,哈哈!
  1. import re


  2. def search(string, txt):
  3.     txtToList = txt.replace(',', '').replace('.', '').strip().split(' ')
  4.     testInner = re.findall('\([^\(.*^\)]*\)', string)
  5.     newString = string
  6.     while len(testInner)>0:
  7.         for ind, each in enumerate(testInner):
  8.             toList = re.findall('!?\w+', each)
  9.             for index, val in enumerate(toList):
  10.                 testNot = re.match('!(\w+)', val)
  11.                 if testNot:
  12.                     val = testNot.group(1)
  13.                     if val not in txtToList:
  14.                         toList[index] = "True"
  15.                     else:
  16.                         toList[index] = "False"
  17.                 else:
  18.                     if val == 'True':
  19.                         pass
  20.                     if val == 'False':
  21.                         pass
  22.                     if val in txtToList:
  23.                         toList[index] = "True"
  24.                     else:
  25.                         toList[index] = "False"
  26.             def change(matched):
  27.                 toRe = toList[0]
  28.                 toList.pop(0)
  29.                 return toRe
  30.             testInner[ind] = re.sub('!?\w+', change, each)

  31.             # 先从&符号判断
  32.             while "&" in testInner[ind]:
  33.                 matchAnd = re.findall('\w+\s\&\s\w+',testInner[ind])
  34.                 for ii,vv in enumerate(matchAnd):
  35.                     if vv == 'False & False':
  36.                         matchAnd[ii] = 'False'
  37.                     elif vv == 'True & True':
  38.                         matchAnd[ii] = 'True'
  39.                     elif vv == 'True & False':
  40.                         matchAnd[ii] = 'False'
  41.                     elif vv == 'False & True':
  42.                         matchAnd[ii] = 'True'
  43.                     else:
  44.                         print('null',vv)
  45.                 def changeAnd(matched):
  46.                     toRe = matchAnd[0]
  47.                     matchAnd.pop(0)
  48.                     return toRe
  49.                 testInner[ind] = re.sub('\w+\s\&\s\w+', changeAnd, testInner[ind])

  50.             # 再从|符号判断
  51.             while "|" in testInner[ind]:
  52.                 matchOr = re.findall('\w+\s\|\s\w+',testInner[ind])
  53.                 for ii,vv in enumerate(matchOr):
  54.                     if vv == 'False | False':
  55.                         matchOr[ii] = 'False'
  56.                     elif vv == 'True | True':
  57.                         matchOr[ii] = 'True'
  58.                     elif vv == 'True | False':
  59.                         matchOr[ii] = 'True'
  60.                     elif vv == 'False | True':
  61.                         matchOr[ii] = 'True'
  62.                     else:
  63.                         print('null',vv)
  64.                 def changeOr(matched):
  65.                     toRe = matchOr[0]
  66.                     matchOr.pop(0)
  67.                     return toRe
  68.                 testInner[ind] = re.sub('\w+\s\|\s\w+', changeOr, testInner[ind])

  69.             #对单一数据去掉括号处理
  70.             if testInner[ind] == '(True)':
  71.                 testInner[ind] = 'True'
  72.             elif  testInner[ind] == '(False)':
  73.                 testInner[ind] = 'False'
  74.             else:
  75.                 print('error,error')

  76.         def changeMix(matched):
  77.             toRe = testInner[0]
  78.             testInner.pop(0)
  79.             return toRe        
  80.         newString = re.sub('\([^\(.*^\)]*\)', changeMix, newString)
  81.         testInner = re.findall('\([^\(.*^\)]*\)', newString)
  82.    
  83.     toList = re.findall('!?\w+', newString)
  84.     for index, val in enumerate(toList):
  85.         testNot = re.match('!(\w+)', val)
  86.         if testNot:
  87.             val = testNot.group(1)
  88.             if val not in txtToList:
  89.                 toList[index] = "True"
  90.             else:
  91.                 toList[index] = "False"
  92.         else:
  93.             if val == 'True':
  94.                 pass
  95.             if val == 'False':
  96.                 pass
  97.             if val in txtToList:
  98.                 toList[index] = "True"
  99.             else:
  100.                 toList[index] = "False"
  101.     def change(matched):
  102.         toRe = toList[0]
  103.         toList.pop(0)
  104.         return toRe
  105.     newString = re.sub('!?\w+', change, newString)

  106.     # 先从&符号判断
  107.     while "&" in newString:
  108.         matchAnd = re.findall('\w+\s\&\s\w+',newString)
  109.         for ii,vv in enumerate(matchAnd):
  110.             if vv == 'False & False':
  111.                 matchAnd[ii] = 'False'
  112.             elif vv == 'True & True':
  113.                 matchAnd[ii] = 'True'
  114.             elif vv == 'True & False':
  115.                 matchAnd[ii] = 'False'
  116.             elif vv == 'False & True':
  117.                 matchAnd[ii] = 'True'
  118.             else:
  119.                 print('null',vv)
  120.         def changeAnd(matched):
  121.             toRe = matchAnd[0]
  122.             matchAnd.pop(0)
  123.             return toRe
  124.         newString = re.sub('\w+\s\&\s\w+', changeAnd, newString)

  125.     # 再从|符号判断
  126.     while "|" in newString:
  127.         matchOr = re.findall('\w+\s\|\s\w+',newString)
  128.         for ii,vv in enumerate(matchOr):
  129.             if vv == 'False | False':
  130.                 matchOr[ii] = 'False'
  131.             elif vv == 'True | True':
  132.                 matchOr[ii] = 'True'
  133.             elif vv == 'True | False':
  134.                 matchOr[ii] = 'True'
  135.             elif vv == 'False | True':
  136.                 matchOr[ii] = 'True'
  137.             else:
  138.                 print('null',vv)
  139.         def changeOr(matched):
  140.             toRe = matchOr[0]
  141.             matchOr.pop(0)
  142.             return toRe
  143.         newString = re.sub('\w+\s\|\s\w+', changeOr, newString)

  144.     #对单一数据去掉括号处理
  145.     if newString == '(True)':
  146.         newString = True
  147.     elif  newString == '(False)':
  148.         newString = False
  149.     elif newString == 'True':
  150.         newString = True
  151.     elif   newString == 'False':
  152.         newString = False
  153.     else:
  154.         print('error,error',newString)   
  155.     return newString


  156. # Test sample
  157. txt = 'one apple with two leaves, one is green and the other is yellow.'
  158. s1 = '(apple | others) & two'  # True
  159. s2 = 'one & yellow & leaf'  # False
  160. s3 = '(!three | one & four) & !five'  # True
  161. s4 = '!green & (ones | two)'  # False
  162. s5 = '(big | !apple | the) & ((!yellow | !green) | others)'  # False


  163. print(search(s1, txt),search(s2, txt),search(s3, txt),search(s4, txt),search(s5, txt))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,虽然已经超过时限,精神可嘉!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-21 18:34:28 | 显示全部楼层
  1. txt = 'one apple with two leaves, one is green and the other is yellow.'
  2. s1 = '(apple | others) & two' #True
  3. s2 = 'one & yellow & leaf' #False
  4. s3 = '(!three | one & four) & !five' #True
  5. s4 = '!green & (ones | two)' #False
  6. s5 = '(big | !apple | the) & ((!yellow | !green) | others)' #False

  7. ## 把中缀表达式换成后缀表达式
  8. ## 默认!和()都是没有空格隔开的
  9. def add_space(s):
  10.     i = 0
  11.     while i < len(s):
  12.         if s[i] == '(':
  13.             s = s[:i+1] + ' ' + s[i+1:]
  14.             i += 1
  15.         if s[i] == ')':
  16.             s = s[:i] + ' ' + s[i:]
  17.             i += 1
  18.         i += 1
  19.     return s
  20.             

  21. def zhong2hou(s):
  22.     op = ['(', ')', '&', '|']
  23.     s1 = add_space(s)
  24.     s1 = s1.split()
  25.     stack = [ ]
  26.     screen = [ ]
  27.     for each in s1:
  28.         if each not in op:
  29.             screen.append(each)
  30.         else:
  31.             if each == '(':
  32.                 stack.append(each)
  33.             if each == ')':
  34.                 while stack[-1] != '(':
  35.                     screen.append(stack.pop())
  36.                 stack.pop()
  37.             if each == '&':
  38.                 if (len(stack) ==  0 or stack[-1] == '('):
  39.                     stack.append(each)
  40.                 else:
  41.                     while len(stack)!= 0 and stack[-1] == '&':
  42.                         screen.append(stack.pop())
  43.                     stack.append(each)
  44.             if each == '|':
  45.                 if (len(stack) ==  0 or stack[-1] == '('):
  46.                     stack.append(each)
  47.                 else:
  48.                     while stack[-1] == '&' or stack[-1] == '|':
  49.                         screen.append(stack.pop())
  50.                     stack.append(each)

  51.     for i in range(len(stack)):
  52.         screen.append(stack.pop())
  53.     return screen

  54. def compute(string):
  55.     if string[0] != '!':
  56.         if string in txt :
  57.             return 1
  58.         else:
  59.             return 0
  60.     else:
  61.         if string[1:] in txt :
  62.             return 0
  63.         else:
  64.             return 1

  65. def result(screen):
  66.     i = 0
  67.     a = [ ]
  68.     while i < len(screen):
  69.         if screen[i] == '&':
  70.             a[-2] = a[-2]*a[-1]
  71.             a.pop()
  72.         elif screen[i] == '|':
  73.             a[-2] = a[-2] + a[-1]
  74.             a.pop()
  75.         else:
  76.             a.append(compute(screen[i]))
  77.         i += 1
  78.     if a[0] == 1:
  79.         return True
  80.     else:
  81.         return False
  82.         
  83. screen = zhong2hou(s5)
  84. r = result(screen)
  85. print(r)               
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-19 16:22

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表