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

jerryxjr1220

鱼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。

def search(string, txt):
        '''Your code here!'''
        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 @～风介～

冬雪雪冬

题目还是有一定难度的，感觉把检索式一一解析，再去运算还是很复杂的。干脆直接把检索式改为python的逻辑运算式得了，这样也不用考虑多层括号的嵌套了。

def search(string, txt):
    string = string.replace(' ', '')
    newstr = ''
    sign = '()!|&'
    if string[0] not in sign:
        newstr += '"' + string[0]
    else:
        newstr += string[0]
    for i in range(1, len(string) - 1):
        if string[i] not in sign and string[i - 1] in sign:
            newstr += '"' + string[i]
        elif string[i] not in sign and string[i + 1] in sign:
            newstr += string[i] + '" in txt'
        else:
            newstr += string[i]
    if string[-1] not in sign:
        newstr += string[-1] + '" in txt'
    else:
        newstr += string[-1]
    newstr = newstr.replace('!', ' not ')
    newstr = newstr.replace('&', ' and ')
    newstr = newstr.replace('|', ' or ')
    return eval(newstr)

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        
print(search(s1, txt))
print(search(s2, txt))
print(search(s3, txt))
print(search(s4, txt))
print(search(s5, txt))

True
False
True
False
False

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

小Q学Python

先粘个耍赖的方法

def search(string, txt):
    a = ''
    flag1,flag2 = 0, 0
    for i in string:
        if i.isalnum() and flag1 == 0:
            flag1 = 1
            a+='\''
        if not i.isalnum() and flag1 == 1:
            if flag2 == 0:
                a+='\' in txt'
            else:
                a+='\' not in txt'
                flag2 = 0
            flag1 = 0
        if i == '|':
            a+=' or '
            continue
        if i == '&':
            a+=' and '
            continue
        if i =='!':
            flag2 = 1
            continue
        a += i
    if flag2 == 1:
        a+='\' not in txt'
    elif flag1 == 1:
        a+='\' in txt'
    return eval(a)

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

print(search(s1,txt))
print(search(s2,txt))
print(search(s3,txt))
print(search(s4,txt))
print(search(s5,txt))

小锟

        
#将中缀表达式转化为后缀表达式，即逆波兰表达式
def conver_fun(list1) :
    #确定运算符优先级
    first={'(':1 , '|':3 , '&':5 ,'!':7 }
    a = '|&!()'
    #定义列表来存储运算符以及文本
    txt = []
    yunsuanfu = []
    for i in list1:
        #如果不在运算符，加入txt
        if i not in a :
            txt.append(i)
        elif len(yunsuanfu) == 0 or i == '(' : #加入左括号
            yunsuanfu.append(i)
        elif i == ')': #出现右括号
            #弹出‘（’之后的运算符
            while len(yunsuanfu) and yunsuanfu[-1] != '(':
                txt.append(yunsuanfu.pop())
            yunsuanfu.pop() #弹出左括号
        else: #判断优先级
            #优先级大的先弹出去加入到文本中
            while (len(yunsuanfu)) and first[yunsuanfu[-1]] >= first[i]:
                txt.append(yunsuanfu.pop())
            yunsuanfu.append(i)
    #将剩下的运算符加入
    while  len(yunsuanfu) :
        txt.append(yunsuanfu.pop())

    return txt

#判断！运算符 返回0或1 ，判断单目运算符
def yunsuan1(one , txt):
    if type(one) == int :
        if one == 1 :
            one = 0
        else :
            one = 1
    if type(one) != int :
        if one in txt :
            one = 0
        else :
            one = 1
    return one 
#判断&|运算符，即双目运算符
def yunsuan2(one , two ,fuhao ,txt):
    if type(one) != int :
        if one in txt :
            one = 1
        else :
            one = 0
    if type(two) != int :
        if two in txt :
            two = 1
        else :
            two = 0
    if fuhao == '&':        
        return one and two 
    if fuhao == '|' :
        return one or two 

    
    
#计算后缀表达式
def count_result(list1 , txt):
    a = '|&!'
    b = []
    for i in list1:
        if i not in a:
            b.append(i)
        elif i != '!':
            #双目运算符，要弹两个元素来运算
            one = b.pop()
            two = b.pop()
            new = yunsuan2(one,two,i ,txt)
            b.append(new)
        else:
            one = b.pop()
            new = yunsuan1(one ,txt)
            b.append(new)
    return b
        



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
def search(string, txt):
    #将判断的文本和运算符分割开，这里默认为！后面没有空格，直接是简写的
    a = list(string)
    for i in range(len(a)):
        if a[i] in '!(':
            a[i] += ' '
        elif  a[i] in ')':
            a[i] = ' ' +  a[i]
    a = ''.join(a)
    a = a.split(' ')

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


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

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

新手·ing

这楼我占了，我选择简单模式~

小剑剑

def scanf(string,findex,rindex):
    t=0
    while string[findex]==' ':
        findex+=1
    temp=findex
    while findex<rindex:
        if string[findex]=='(':
            t-=1
        elif string[findex]==')':
            t+=1
        elif string[findex]==' ':
            if t==0:
                break
        findex+=1
    return (temp,findex)

def calc(string,findex,rindex,txt):
    positive=True
    while string[findex]=='!':
        positive=not positive
        findex+=1
    bracket=False
    if string[findex]=='(':
        findex+=1
        rindex-=1
        bracket=True
    if not bracket:
        if not positive:
            result=not string[findex:rindex] in txt
        else :
            result =string[findex:rindex] in txt
        return result
    index=findex
    cl=[]
    while index<rindex:
        cl.append(scanf(string,index,rindex))
        index=cl[-1][1]
    if len(cl)==1:
        return calc(string,cl[0][0],cl[0][1],txt)
    temp=cl.pop()
    result=calc(string,temp[0],temp[1],txt)
    while cl:
        symbol=string[cl.pop()[0]]
        if symbol=='|':
            if result==True:
                return True
            else:
                temp=cl.pop()
                result=calc(string,temp[0],temp[1],txt)
                continue
        temp=cl.pop()
        temp=calc(string,temp[0],temp[1],txt)
        if temp==False:
            result=False
            
    if not positive:
        result = not result
    return result
        
def func(string,txt):
    string=string.strip()
    string='('+string+')'
    return calc(string,0,len(string),txt)

恭喜大大升职

''' scanf 顾名思义就是扫描
    例如  scanf('(apple | others) & two',0,len('(apple | others) & two'))
    就返回 (apple | others)的索引范围
    scanf('(apple | others) & two',16,len)
    就返回 & 的索引范围
    scanf('(apple | others) & two',18,len)
    就返回 two 的索引范围
'''
def scanf(string,findex,rindex):
    t=0
    while string[findex]==' ':
        findex+=1
    temp=findex
    while findex<rindex:
        if string[findex]=='(':
            t-=1
        elif string[findex]==')':
            t+=1
        elif string[findex]==' ':
            if t==0:
                break
        findex+=1
    return (temp,findex)

def calc(string,findex,rindex,txt):
    positive=True #开头是否有！可以跳过多个！
    while string[findex]=='!':
        positive=not positive
        findex+=1#掉过！
    bracket=False #括号有括号就说明这个字符串可能有运算符
    if string[findex]=='(':
        findex+=1
        rindex-=1
        bracket=True
    #没有括号 那就是一个没有运算符的字符串了 可以直接查找了
    if not bracket:
        if not positive:
            result=not string[findex:rindex] in txt
        else :
            result =string[findex:rindex] in txt
        return result
    index=findex#好像这个index是多余的 直接用findex就好了
    '''
    cl保存扫描的返回值 必然是
    一段可以转为bool值的字符串 和 一个运算符轮流出现
'''
    cl=[]
    while index<rindex:
        cl.append(scanf(string,index,rindex))
        index=cl[-1][1]
    '''
    拿到可以转为bool值的字符串 和 运算符
    cl只有一个元素 那么
    这个元素必然是可以转为bool值的字符串
'''
    if len(cl)==1:
        return calc(string,cl[0][0],cl[0][1],txt)

    '''
    cl 不止一个值,一个个弹出来计算
'''
    temp=cl.pop()
    result=calc(string,temp[0],temp[1],txt)
    while cl:
        symbol=string[cl.pop()[0]]#运算符
        if symbol=='|':
            if result==True:#或运算 一个是真后面不用算了
                return True
            else:#或运算 一个值是假 直接计算下一个字符串
                temp=cl.pop()
                result=calc(string,temp[0],temp[1],txt)
                continue
        '''
        因为& 和 | 的优先级问题
        为了防止cl里面还有 | 所以只好 & 一个个算了
'''
        temp=cl.pop()
        temp=calc(string,temp[0],temp[1],txt)
        if temp==False:
            result=False
            
    if not positive:
        result = not result
    return result
        
def func(string,txt):
    '''
    去掉两边的空格
    加上括号是为了兼容
    如果没有括号会出错
    例如 'one & yellow'
    会被calc看作是一个没有运算符的字符串了
    但是里面还有个 &
'''
    string=string.strip()
    string='('+string+')'
    return calc(string,0,len(string),txt)

lovesword

#coding=utf-8
import re
txt = 'one apple with two leaves, one is green and the other is yellow.'

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

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

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


for s in [s1,s2,s3,s4,s5]:
    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 这个函数 网上找的。

gunjang

def search(string, txt):
        v, i = mysearch(string+'=', txt)
        return v

def mysearch(str, txt, indexofstr=0, endchar='='): #return true/false and index
        op = '#'
        v = True
        while str[indexofstr] != endchar:
                if str[indexofstr] == '!': #not
                        op = '!'
                elif str[indexofstr] == '&': #and
                        if v == False:
                                #short-circuit logic
                                #False and xx and xxx == False
                                #skip all & until end of string or find "|", 
                                bracketlevel = 0 
                                for i in range(indexofstr+1, len(str)):
                                        #skip bracket
                                        if (str[i] == endchar) and (bracketlevel==0):
                                                break
                                        if (str[i] == '|') and (bracketlevel==0): #bracket
                                                break
                                        if str[i] == '(':
                                                bracketlevel += 1
                                        elif str[i] == ')':
                                                bracketlevel -= 1
                                indexofstr = i
                                op = '#'
                                continue

                        op = '&'
                elif str[indexofstr] == '|': # or
                        if v == True: #true or x or xx = True
                                #short-circuit logic
                                #skip to end
                                if endchar == '=':
                                        indexofstr = len(str)
                                        break
                                #else skip to right bracket “)"
                                bracketlevel = 0 
                                for i in range(indexofstr+1, len(str)):
                                        #skip bracket
                                        if (str[i] == endchar) and (bracketlevel==0):
                                                break
                                        if str[i] == '(':
                                                bracketlevel += 1
                                        elif str[i] == ')':
                                                bracketlevel -= 1
                                indexofstr = i
                                break

                        op = '|'
                elif str[indexofstr] == ' ': 
                        pass
                elif str[indexofstr] == '(': 
                        v, indexofstr = mysearch(str, txt, indexofstr+1, ')')
                        if op == '!':
                                v = not v
                                op = '#'
                else:
                        #get token
                        firstindex = indexofstr
                        while (indexofstr < len(str)) and not (str[indexofstr] in set('()!&| =')):
                                indexofstr += 1
                        w = str[firstindex:indexofstr]
                        v = txt.find(w) > -1
                        if op == '!':
                                v = not v
                                op = '#'
                        continue

                indexofstr += 1
        return v, indexofstr

zmx296689210

最高难度级别！！今天才看见

import re


def search(string, txt):

    pattern = re.compile(r'[^!&|() ]+')
    def changeKeywords(string, txt):
        '''
        将关键字转换为0或1
        例如
        txt = 'one apple with two leaves, one is green and the other is yellow.'
        s1 = '(apple | others) & two'
        转换后 string ='(1 | 0) & 1'
        '''
        string = ' ' + string + ' '
        keywords = pattern.findall(string)
        for each in keywords:
            if each in txt:
                string = re.sub('([!&|() ])(%s)([!&|() ])' % each, '\g<1>1\g<3>', string)
            else:
                string = re.sub('([!&|() ])(%s)([!&|() ])' % each, '\g<1>0\g<3>', string)
        string = string.replace(' ', '')
        return string

    operatorPrecedence = {
        '(': 0,
        ')': 0,
        '|': 1,
        '&': 2,
        '!': 3
    }

    def postfixConvert(exp):
        ''''' 
        将表达式字符串，转为后缀表达式 
        如exp = "1+2*(3-1)-4" 
        转换为：postfix = ['1', '2', '3', '1', '-', '*', '+', '4', '-'] 
        '''
        stack = []  # 运算符栈，存放运算符
        postfix = []  # 后缀表达式栈
        for char in exp:
            #        print char, stack, postfix
            if char not in operatorPrecedence:  # 非符号，直接进栈
                postfix.append(char)
            else:
                if len(stack) == 0:  # 若是运算符栈啥也没有，直接将运算符进栈
                    stack.append(char)
                else:
                    if char == "(":
                        stack.append(char)
                    elif char == ")":  # 遇到了右括号，运算符出栈到postfix中，并且将左括号出栈
                        while stack[-1] != "(":
                            postfix.append(stack.pop())
                        stack.pop()

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

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

    def calculate(num1, op, num2='0'):
        if not num1.isdigit() and not num2.isdigit():
            raise "num error"
        else:
            num1 = int(num1)
            num2 = int(num2)
        if op == "&":
            return int(num1 and num2)
        elif op == "|":
            return int(num1 or num2)
        elif op == "!":
            return int(not num1)
        else:
            raise "op error"

    def calExpressionTree(postfix):
        stack = []
        for char in postfix:
            stack.append(char)
            if char in "&|":
                op = stack.pop()
                num2 = stack.pop()
                num1 = stack.pop()
                value = calculate(num1, op, num2)
                value = str(value)  # 计算结果是数值类型，将其化为字符串类型
                stack.append(value)
            elif char == '!':
                op = stack.pop()
                num1 = stack.pop()
                value = calculate(num1, op)
                value = str(value)
                stack.append(value)
        return bool(int(stack[0]))

    string = changeKeywords(string, txt)
    postfix = postfixConvert(string)
    res = calExpressionTree(postfix)
    return res


if __name__ == '__main__':
    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

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

    print(search(s1, txt))
    print(search(s2, txt))
    print(search(s3, txt))
    print(search(s4, txt))
    print(search(s5, txt))
    print(search(s6, txt))

ershing

晚上刚注册就弹出这个窗口，本来python刚跟着小甲鱼视频学了一部分，然后整个晚上都在搞这道题，终于搞出来了，全部测试过关，有些许成就感了，哈哈！

import re


def search(string, txt):
    txtToList = txt.replace(',', '').replace('.', '').strip().split(' ')
    testInner = re.findall('\([^\(.*^\)]*\)', string)
    newString = string
    while len(testInner)>0:
        for ind, each in enumerate(testInner):
            toList = re.findall('!?\w+', each)
            for index, val in enumerate(toList):
                testNot = re.match('!(\w+)', val)
                if testNot:
                    val = testNot.group(1)
                    if val not in txtToList:
                        toList[index] = "True"
                    else:
                        toList[index] = "False"
                else:
                    if val == 'True':
                        pass
                    if val == 'False':
                        pass
                    if val in txtToList:
                        toList[index] = "True"
                    else:
                        toList[index] = "False"
            def change(matched):
                toRe = toList[0]
                toList.pop(0)
                return toRe
            testInner[ind] = re.sub('!?\w+', change, each)

            # 先从&符号判断
            while "&" in testInner[ind]:
                matchAnd = re.findall('\w+\s\&\s\w+',testInner[ind])
                for ii,vv in enumerate(matchAnd):
                    if vv == 'False & False':
                        matchAnd[ii] = 'False'
                    elif vv == 'True & True':
                        matchAnd[ii] = 'True'
                    elif vv == 'True & False':
                        matchAnd[ii] = 'False'
                    elif vv == 'False & True':
                        matchAnd[ii] = 'True'
                    else:
                        print('null',vv)
                def changeAnd(matched):
                    toRe = matchAnd[0]
                    matchAnd.pop(0)
                    return toRe
                testInner[ind] = re.sub('\w+\s\&\s\w+', changeAnd, testInner[ind])

            # 再从|符号判断
            while "|" in testInner[ind]:
                matchOr = re.findall('\w+\s\|\s\w+',testInner[ind])
                for ii,vv in enumerate(matchOr):
                    if vv == 'False | False':
                        matchOr[ii] = 'False'
                    elif vv == 'True | True':
                        matchOr[ii] = 'True'
                    elif vv == 'True | False':
                        matchOr[ii] = 'True'
                    elif vv == 'False | True':
                        matchOr[ii] = 'True'
                    else:
                        print('null',vv)
                def changeOr(matched):
                    toRe = matchOr[0]
                    matchOr.pop(0)
                    return toRe
                testInner[ind] = re.sub('\w+\s\|\s\w+', changeOr, testInner[ind])

            #对单一数据去掉括号处理
            if testInner[ind] == '(True)':
                testInner[ind] = 'True'
            elif  testInner[ind] == '(False)':
                testInner[ind] = 'False'
            else:
                print('error,error')

        def changeMix(matched):
            toRe = testInner[0]
            testInner.pop(0)
            return toRe        
        newString = re.sub('\([^\(.*^\)]*\)', changeMix, newString)
        testInner = re.findall('\([^\(.*^\)]*\)', newString)
    
    toList = re.findall('!?\w+', newString)
    for index, val in enumerate(toList):
        testNot = re.match('!(\w+)', val)
        if testNot:
            val = testNot.group(1)
            if val not in txtToList:
                toList[index] = "True"
            else:
                toList[index] = "False"
        else:
            if val == 'True':
                pass
            if val == 'False':
                pass
            if val in txtToList:
                toList[index] = "True"
            else:
                toList[index] = "False"
    def change(matched):
        toRe = toList[0]
        toList.pop(0)
        return toRe
    newString = re.sub('!?\w+', change, newString)

    # 先从&符号判断
    while "&" in newString:
        matchAnd = re.findall('\w+\s\&\s\w+',newString)
        for ii,vv in enumerate(matchAnd):
            if vv == 'False & False':
                matchAnd[ii] = 'False'
            elif vv == 'True & True':
                matchAnd[ii] = 'True'
            elif vv == 'True & False':
                matchAnd[ii] = 'False'
            elif vv == 'False & True':
                matchAnd[ii] = 'True'
            else:
                print('null',vv)
        def changeAnd(matched):
            toRe = matchAnd[0]
            matchAnd.pop(0)
            return toRe
        newString = re.sub('\w+\s\&\s\w+', changeAnd, newString)

    # 再从|符号判断
    while "|" in newString:
        matchOr = re.findall('\w+\s\|\s\w+',newString)
        for ii,vv in enumerate(matchOr):
            if vv == 'False | False':
                matchOr[ii] = 'False'
            elif vv == 'True | True':
                matchOr[ii] = 'True'
            elif vv == 'True | False':
                matchOr[ii] = 'True'
            elif vv == 'False | True':
                matchOr[ii] = 'True'
            else:
                print('null',vv)
        def changeOr(matched):
            toRe = matchOr[0]
            matchOr.pop(0)
            return toRe
        newString = re.sub('\w+\s\|\s\w+', changeOr, newString)

    #对单一数据去掉括号处理
    if newString == '(True)':
        newString = True
    elif  newString == '(False)':
        newString = False
    elif newString == 'True':
        newString = True
    elif   newString == 'False':
        newString = False
    else:
        print('error,error',newString)    
    return newString


# 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


print(search(s1, txt),search(s2, txt),search(s3, txt),search(s4, txt),search(s5, txt))

WelanceLee

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

## 把中缀表达式换成后缀表达式
## 默认!和()都是没有空格隔开的
def add_space(s):
    i = 0
    while i < len(s):
        if s[i] == '(':
            s = s[:i+1] + ' ' + s[i+1:]
            i += 1
        if s[i] == ')':
            s = s[:i] + ' ' + s[i:]
            i += 1
        i += 1
    return s
            

def zhong2hou(s):
    op = ['(', ')', '&', '|']
    s1 = add_space(s)
    s1 = s1.split()
    stack = [ ]
    screen = [ ]
    for each in s1:
        if each not in op:
            screen.append(each)
        else:
            if each == '(':
                stack.append(each)
            if each == ')':
                while stack[-1] != '(':
                    screen.append(stack.pop())
                stack.pop()
            if each == '&':
                if (len(stack) ==  0 or stack[-1] == '('):
                    stack.append(each)
                else:
                    while len(stack)!= 0 and stack[-1] == '&':
                        screen.append(stack.pop())
                    stack.append(each)
            if each == '|':
                if (len(stack) ==  0 or stack[-1] == '('):
                    stack.append(each)
                else:
                    while stack[-1] == '&' or stack[-1] == '|':
                        screen.append(stack.pop())
                    stack.append(each)

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

def compute(string):
    if string[0] != '!':
        if string in txt :
            return 1
        else:
            return 0
    else:
        if string[1:] in txt :
            return 0
        else:
            return 1

def result(screen):
    i = 0
    a = [ ]
    while i < len(screen):
        if screen[i] == '&':
            a[-2] = a[-2]*a[-1]
            a.pop()
        elif screen[i] == '|':
            a[-2] = a[-2] + a[-1]
            a.pop()
        else:
            a.append(compute(screen[i]))
        i += 1
    if a[0] == 1:
        return True
    else:
        return False
        
screen = zhong2hou(s5)
r = result(screen)
print(r)