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

jerryxjr1220

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

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

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

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

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

jerryxjr1220

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

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

def search(string, txt):
    #去首尾空格
    string = string.strip()
    #主循环，找不在括号中的“&”和“|”进行判断
    layer = 0
    for i in range(len(string)):
        #判断括号层数
        if string[i] == '(': layer += 1
        if string[i] == ')': layer -= 1
        #处理“&”的情况
        if string[i] == '&' and layer == 0:
            if search(string[:i], txt):
                return search(string[i+1:], txt)
            else:
                return False
        #处理“|”的情况
        elif string[i] == '|' and layer == 0:
            if search(string[:i], txt):
                return True
            else:
                return search(string[i+1:], txt)
    #去首尾括号
    if string[0]=='(' and string[-1]==')': return search(string[1:-1], txt)
    #处理“！”的情况
    return not search(string[1:], txt) if string[0] == '!' else string in txt

小锟

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

zmx296689210

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

txt = 'one apple with two leaves, one is green and the other is yellow.'
string = 'ther'
print(search(string, txt))

# 正确结果是 False
# 而楼主的运行结果是 True， 可能错在非全字匹配那里...我的代码这个样例测试也是错的...我代码需要修改一下判断条件

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

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:
            p = re.compile('[!&|() .,!]%s[!&|() .,!]' % each)
            if p.findall(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)'
    s7 = 'ther'

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

jerryxjr1220

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

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

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

zmx296689210

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

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

好吧......