Python : Apply distributive law to elements in list

Question

I want to do below in python2.7 . It works in case of 2 subelements but I can have multiple subelements.

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

The above code works for below:

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

Explanation:

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

I want to make this work for any number of subelements, like in below example 'S' is third element in input so ['or', 'S', 'R'] should be added in output:

 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']]

Thanks.

Answer 1

You can create a method that recursively converts anything with more than two subelements into a form where every list has two subelements (i.e. where every logical connective only has 2 arguments). For example:

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:])]

Then you can call this on any proposition before running it through the code you already have, and your code can safely assume that no connective will have more than two arguments.