Python嵌套列表与递归问题

2024-09-30 14:37:20 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图处理一个一阶逻辑公式,在python中用嵌套列表和字符串表示,这样它就可以用析取范式了

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

变成

['|'['amp;',['amp;','a','c'],['amp;','b','c']],['amp;',['amp;','a','d',['amp;','b','d']]]

其中|是“or”和“and”是“and”。在

目前,im使用递归实现,它对一个公式进行多次传递,直到在“ands”的列表参数中找不到任何嵌套的“或”符号。在

这是我的实现,performDNF(form)是入口点。现在它只对公式执行一次传递,但是while循环检查函数在“&;s”中找不到“|”并终止,请帮助任何让我抓狂的人。在

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

Tags: selfformlenreturnifdeftyperesult
2条回答

对不起,我没试着理解你的解决办法。我认为这太难读了,可能方法太麻烦了。在

如果你有一个DNF,你需要做的就是找到所有的原子组合,从每个子列表中取出一个。这几乎可以归结为this问题。。。从每个或子类中,你需要取一个原子,并将所有这些与和结合起来。在

所有可能的与从句的OR组合会产生您想要的结果。正确的?在

好吧,这是一个实际可行的解决方案。在

我不明白你的代码,而且我也没听说过DNF,所以我开始研究这个问题。在

Wikipedia page on DNF非常有用。它包含了一个描述DNF的语法。在

在此基础上,我编写了一组简单的递归函数,我相信这些函数可以正确识别DNF。我的代码包括一些简单的测试用例。在

然后我意识到数据表示的二叉树性质使得应用DeMorgan定律简化“not”情况变得相对简单,方法是编写一个名为negate()的函数,它递归地求反,剩下的部分就就位了。在

我已经包括了测试用例。似乎有用。在

我没有进一步的计划。如果有人发现了bug,请提供一个测试用例,我会查看它。在

这段代码应该在任何python2.4或更新版本上运行。您甚至可以通过用一个简单的字符列表替换frozenset来将其移植到较旧的Python版本。我用python3.x进行了测试,发现异常语法已经改变了,因此如果您想在python3下运行它,就需要更改raise行;重要的部分都可以工作。在

在这个问题中,您没有提到您对not使用了什么字符;鉴于您对and使用了&,而对{}使用了{},我假设您很可能使用!来表示{},并相应地编写了代码。关于您的代码,这是让我困惑的一件事:难道您不希望在您的输入中找到not?在

我做这件事很有意思。它不像数独游戏那样毫无意义。在

import sys


ch_and = '&'
ch_not = '!'
ch_or = '|'

def echo(*args):
    # like print() in Python 3 but works in 2.x or in 3
    sys.stdout.write(" ".join(str(x) for x in args) + "\n")

try:
    symbols = frozenset([ch_and, ch_not, ch_or])
except NameError:
    raise Exception, "sorry, your Python is too old for this code"

try:
    __str_type = basestring
except NameError:
    __str_type = str


def is_symbol(x):
    if not isinstance(x, __str_type) or len(x) == 0:
        return False
    return x[0] in symbols

def is_and(x):
    if not isinstance(x, __str_type) or len(x) == 0:
        return False
    return x[0] == ch_and

def is_or(x):
    if not isinstance(x, __str_type) or len(x) == 0:
        return False
    return x[0] == ch_or

def is_not(x):
    if not isinstance(x, __str_type) or len(x) == 0:
        return False
    return x[0] == ch_not

def is_literal_char(x):
    if not isinstance(x, __str_type) or len(x) == 0:
        return False
    return x[0] not in symbols

def is_list(x, n):
    return isinstance(x, list) and len(x) == n


def is_literal(x):
    """\
True if x is a literal char, or a 'not' followed by a literal char."""
    if is_literal_char(x):
        return True
    return is_list(x, 2) and is_not(x[0]) and is_literal_char(x[1])


def is_conjunct(x):
    """\
True if x is a literal, or 'and' followed by two conjuctions."""
    if is_literal(x):
        return True
    return (is_list(x, 3) and
            is_and(x[0]) and is_conjunct(x[1]) and is_conjunct(x[2]))


def is_disjunct(x):
    """\
True if x is a conjunction, or 'or' followed by two disjuctions."""
    if is_conjunct(x):
        return True
    return (is_list(x, 3) and
            is_or(x[0]) and is_disjunct(x[1]) and is_disjunct(x[2]))



def is_dnf(x):
    return is_disjunct(x)

def is_wf(x):
    """returns True if x is a well-formed list"""
    if is_literal(x):
        return True
    elif not isinstance(x, list):
        raise TypeError, "only lists allowed"
    elif len(x) == 2 and is_not(x[0]) and is_wf(x[1]):
        return True
    else:
        return (is_list(x, 3) and (is_and(x[0]) or is_or(x[0])) and
                is_wf(x[1]) and is_wf(x[2]))

def negate(x):
    # trivial: negate a returns !a
    if is_literal_char(x):
        return [ch_not, x]

    # trivial: negate !a returns a
    if is_list(x, 2) and is_not(x[0]):
        return x[1]

    # DeMorgan's law:  negate (a && b) returns (!a || !b)
    if is_list(x, 3) and is_and(x[0]):
        return [ch_or, negate(x[1]), negate(x[2])]

    # DeMorgan's law:  negate (a || b) returns (!a && !b)
    if is_list(x, 3) and is_or(x[0]):
        return [ch_and, negate(x[1]), negate(x[2])]

    raise ValueError, "negate() only works on well-formed values."

def __rewrite(x):
    # handle all dnf, which includes simple literals.
    if is_dnf(x):
        # basis case. no work to do, return unchanged.
        return x

    if len(x) == 2 and is_not(x[0]):
        x1 = x[1]
        if is_list(x1, 2) and is_not(x1[0]):
            # double negative!  throw away the 'not' 'not' and keep rewriting.
            return __rewrite(x1[1])
        assert is_list(x1, 3)
        # handle non-inner 'not'
        return __rewrite(negate(x1))

    # handle 'and' with 'or' inside it
    assert is_list(x, 3) and is_and(x[0]) or is_or(x[0])
    if len(x) == 3 and is_and(x[0]):
        x1, x2 = x[1], x[2]
        if ((is_list(x1, 3) and is_or(x1[0])) and
                (is_list(x2, 3) and is_or(x2[0]))):
# (a || b) && (c || d)   (a && c) || (b && c) || (a && d) || (b && d)
            lst_ac = [ch_and, x1[1], x2[1]]
            lst_bc = [ch_and, x1[2], x2[1]]
            lst_ad = [ch_and, x1[1], x2[2]]
            lst_bd = [ch_and, x1[2], x2[2]]
            new_x = [ch_or, [ch_or, lst_ac, lst_bc], [ch_or, lst_ad, lst_bd]]
            return __rewrite(new_x)

        if (is_list(x2, 3) and is_or(x2[0])):
# a && (b || c)    (a && b) || (a && c)
            lst_ab = [ch_and, x1, x2[1]]
            lst_ac = [ch_and, x1, x2[2]]
            new_x = [ch_or, lst_ab, lst_ac]
            return __rewrite(new_x)

        if (is_list(x1, 3) and is_or(x1[0])):
# (a || b) && c    (a && c) || (b && c)
            lst_ac = [ch_and, x1[1], x2]
            lst_bc = [ch_and, x1[2], x2]
            new_x = [ch_or, lst_ac, lst_bc]
            return __rewrite(new_x)

    return [x[0], __rewrite(x[1]), __rewrite(x[2])]
    #return x

def rewrite(x):
    if not is_wf(x):
        raise ValueError, "can only rewrite well-formed lists"
    while not is_dnf(x):
        x = __rewrite(x)
    return x


#### self-test code ####

__failed = False
__verbose = True
def test_not_wf(x):
    global __failed
    if is_wf(x):
        echo("is_wf() returned True for:", x)
        __failed = True

def test_dnf(x):
    global __failed
    if not is_wf(x):
        echo("is_wf() returned False for:", x)
        __failed = True
    elif not is_dnf(x):
        echo("is_dnf() returned False for:", x)
        __failed = True

def test_not_dnf(x):
    global __failed
    if not is_wf(x):
        echo("is_wf() returned False for:", x)
        __failed = True
    elif is_dnf(x):
        echo("is_dnf() returned True for:", x)
        __failed = True
    else:
        xr = rewrite(x)
        if not is_wf(xr):
            echo("rewrite produced non-well-formed for:", x)
            echo("result was:", xr)
            __failed = True
        elif not is_dnf(xr):
            echo("rewrite failed for:", x)
            echo("result was:", xr)
            __failed = True
        else:
            if __verbose:
                echo("original:", x)
                echo("rewritten:", xr)
                echo()

def self_test():
    a, b, c, d = 'a', 'b', 'c', 'd'
    test_dnf(a)
    test_dnf(b)
    test_dnf(c)
    test_dnf(d)

    lstna = [ch_not, a]
    test_dnf(lstna)

    lstnb = [ch_not, b]
    test_dnf(lstnb)

    lsta = [ch_and, a, b]
    test_dnf(lsta)

    lsto = [ch_or, a, b]
    test_dnf(lsto)

    test_dnf([ch_and, lsta, lsta])

    test_dnf([ch_or, lsta, lsta])

    lstnn = [ch_not, [ch_not, a]]
    test_not_dnf(lstnn)

    test_not_dnf([ch_and, lstnn, lstnn])

    # test 'and'/'or' inside 'not'
    test_not_dnf([ch_not, lsta])
    test_not_dnf([ch_not, lsto])

    # test 'or' inside of 'and'
    # a&(b|c)  > (a&b)|(b&c)
    test_not_dnf([ch_and, a, [ch_or, b, c]])
    # (a|b)&c  > (a&c)|(b&c)
    test_not_dnf([ch_and, [ch_or, a, b], c])
    # (a|b)&(c|d)  > ((a&c)|(b&c))|((a&d)|(b&d))
    test_not_dnf([ch_and, [ch_or, a, b], [ch_or, c, d]])

    # a&a&a&(b|c)  > a&a&(a&b|b&c)  > a&(a&a&b|a&b&c)  > (a&a&a&b|a&a&b&c)
    test_not_dnf([ch_and, a, [ch_and, a, [ch_and, a, [ch_or, b, c]]]])

    if __failed:
        echo("one or more tests failed")

self_test()

现在,我很抱歉这么说,但我想得越多,我就越觉得你让我帮你做作业。所以,我刚刚编写了这段代码的一个改进版本,但我不打算在这里共享;我将把它留给您作为练习。在我描述之后,你应该可以很容易地做到。在

我有一个while循环反复调用__rewrite(),这是一个可怕的黑客行为。rewrite()函数应该能够通过对__rewrite()的单个调用重写树结构。只需做一些简单的更改,您就可以摆脱while循环;我做了它,并对其进行了测试,它工作了。您希望__rewrite()沿着树向下走,然后在返回的过程中重写内容,它将在一个过程中工作。您还可以修改__rewrite()以在列表格式不正确的情况下返回错误,并取消对is_wf()的调用;这也很简单。在

我怀疑你的老师会为while循环扣分,所以你应该有动力尝试这个。我希望你做的愉快,我希望你从我的代码中学到了一些有用的东西。在

相关问题 更多 >