Python nested lists and recursion problem

Question

Hi guys,

I posted this question under an alter yesterday not realising my account was still active after 9 months, sorry for the double post, i've fixed an error in my example pointed out by jellybean and i'll elaborate further on the context of the problem.

I'm trying to process a first order logic formula represented as nested lists and strings in python so that that its in disjunctive normal form,

i.e

[
    '&', 
    ['|', 'a', 'b'], 
    ['|', 'c', 'd']
]

turns into

[
    '|',
    [
        '|', 
        ['&', 'a', 'c'], 
        ['&', 'b', 'c']
    ], 
    [
        '|', 
        ['&', 'a', 'd'], 
        ['&', 'b', 'd']
    ]
]`

where | is or and & is and.

currently im using a recursive implementation which does several passes over a formula until it can't find any nested 'or' symbols inside a list argument for 'ands'. Its being used to process a set of nested formulas represented as strings and lists for universal computational tree logic so it will not only have |s and &s but temporal operators.

This is my implementation, performDNF(form) is the entry point. Right now it performs a single pass over the formula with dnfDistributivity() which works for smaller inputs but when you use larger inputs the while loop checking function (checkDistributivity()) finds no |s inside of &s and terminates. Help anyone, this is driving me mad.

def dnfDistributivity(self, form):
    if isinstance(form, type([])):
        if len(form) == 3:
            if form[0] == '&':
                if form[1][0] == '|':
                    form = [
                               '|', 
                               ['&', form[2], form[1][1]], 
                               ['&', form[2], form[1][2]]
                           ]
                elif form[2][0] == '|':
                    form = [
                                '|', 
                                ['&', form[1], form[2][1]], 
                                ['&', form[1], form[2][2]]
                           ]
            form[1] = self.dnfDistributivity(form[1])
            form[2] = self.dnfDistributivity(form[2])
        elif len(form) == 2:
            form[1] = self.dnfDistributivity(form[1])
    return form

def checkDistributivity(self, form, result = 0):
    if isinstance(form, type([])):
        if len(form) == 3:
            if form[0] == '&':
                print "found &"
                if isinstance(form[1], type([])):
                    if form[1][0] == '|':
                        return 1
                elif isinstance(form[2], type([])):
                    if form[2][0] == '|':
                        return 1
                else:
                    result = self.checkDistributivity(form[1], result)
                    print result
                    if result != 1:
                        result = self.checkDistributivity(form[2], result)
                        print result
        elif len(form) == 2:
            result = self.checkDistributivity(form[1], result)
            print result
    return result

def performDNF(self, form):
    while self.checkDistributivity(form):
        form = self.dnfDistributivity(self.dnfDistributivity(form))
    return form

Answer 1

You have:

    elif len(form) == 2:
        result = self.checkDistributivity(form[1], result)
        print result

Shouldn't that be:

    elif len(form) == 2:
        result_1 = self.checkDistributivity(form[1], result)
        result_2 = self.checkDistributivity(form[2], result) 
        if result_1 or result_2:
            return 1