python : Apply distributive law to elements in list

Question

我想在 python2.7 下面做。它适用于 2 个子元素，但我可以有多个子元素。

NOT = "not"
OR = "or"
AND  = "and"

def convertMain(prop) :

    if isinstance(prop, str) : 
        answer = prop
    else :
        op = prop[0]
        #tree1 =  convertIntoCNF(prop[1])
        #tree2 =  convertIntoCNF(prop[2])
        """{ assert: tree1 and tree2  are in  cnf }"""
        if op == AND :            
            answer = [AND] + [convertIntoCNF(item) for item in prop[1:]]
        else : # op == OR
            if (len(prop) == 3) :
                tree1 =  convertIntoCNF(prop[1])
                tree2 =  convertIntoCNF(prop[2])

                answer = distOr2(tree1, tree2)

    return answer

def distOr2(p1,p2):

    if isinstance(p1, list) and p1[0] == AND :
        #{ assert:  p1 = P11 & P12 }
        answer = [AND, distOr2(p1[1],p2), distOr2(p1[2],p2)]
    elif  isinstance(p2, list) and p2[0] == AND :
        #{ assert:  p2 = P21 & P22 }
        answer = [AND, distOr2(p1,p2[1]), distOr2(p1,p2[2])]
    else :
        #{ assert: since  p1 and p2 are both in cnf, then both are disjunctive clauses, which can be appended }
        answer = [OR, p1, p2]
    return answer

以上代码适用于以下情况:

 Input  : ['and', ['or', ['and', '-P', 'Q'], 'R'], ['or', '-P', '-R']]
 Output : ['and', ['and', ['or', '-P', 'R'], ['or', 'Q', 'R']], ['or', '-P', '-R']]

解释:

 Input is expression ((-P V Q) V R) ^ (-P V -R))
 Output is expression  ((-P V R) ^ (Q V R)) ^ (-P V -R)

我想让这个适用于任意数量的子元素，如下例所示，“S”是输入中的第三个元素，因此应在输出中添加 ['or', 'S', 'R']:

 Input  : ['and', ['or', ['and', '-P', 'Q', 'S'], 'R'], ['or', '-P', '-R']]
 Output : ['and', ['and', ['or', '-P', 'R'], ['or', 'Q', 'R'], ['or', 'S', 'R']], ['or', '-P', '-R']]

谢谢。

Answer 1

您可以创建一个方法，以递归方式将具有两个以上子元素的任何内容转换为每个列表都有两个子元素的形式(即每个逻辑连接词只有 2 个参数)。例如:

def makeBinary(prop):
    if isinstance(prop, str):
        return prop
    elif len(prop) == 3:
        return [prop[0], makeBinary(prop[1]), makeBinary(prop[2])]
    else:
        return [prop[0], makeBinary(prop[1]), makeBinary([prop[0]] + prop[2:])]

然后您可以在任何命题上调用它，然后再通过您已有的代码运行它，并且您的代码可以安全地假设连接词不会有超过两个参数。