Python 嵌套列表和递归问题

Question

我昨天在一个备用账号下发了这个问题，没意识到我的账号在9个月后仍然活跃，抱歉重复发帖了。我已经修正了jellybean指出的示例中的错误，并将进一步阐述问题的背景。

我正在尝试处理一个用嵌套列表和字符串表示的第一阶逻辑公式，目标是将其转换为析取范式。

也就是说，

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

要变成

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

其中 | 代表或，而 & 代表和。

目前我使用的是递归实现，这个实现会对公式进行多次处理，直到在'和'的列表参数中找不到嵌套的'或'符号。这个方法用于处理一组用字符串和列表表示的嵌套公式，属于通用的计算树逻辑，所以它不仅会有 | 和 &，还会有时间运算符。

这是我的实现，performDNF(form) 是入口点。目前它对公式进行一次处理，使用 dnfDistributivity()，这个方法对较小的输入有效，但当输入较大时，检查函数的while循环（checkDistributivity()）在 & 内部找不到 |，就会终止。有人能帮忙吗，这让我很抓狂。

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

你有：

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

那应该是：

    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

Answer 2

首先，对你的代码有两个一般性的建议：

• 用 return True 代替 return 1。
• 用 isinstance(form, list) 代替 isinstance(form, type([]))。

其次，还有一些其他的观察：

• 我猜你也想去掉双重否定。目前你的代码没有做到这一点。
• 同样，你需要应用德摩根定律之一，把否定推到最底层。

除此之外，我觉得这段代码的可读性可以大大提高。我会给出一个我认为正确的替代实现。让我知道下面的代码是否对你有效；我没有过于复杂的表达式，所以可能会漏掉一些边界情况。最后，我只会关注常规的命题连接词。关于如何应用涉及CTL特定连接词的变换，应该很清楚。

1. 创建一个 Op 类，表示一个运算符（连接词）：

   class Op(list):
       def __init__(self, *args):
           super().__init__(args)
   

   这里传给 __init__ 的参数是操作数。这段代码使用了 super，如 PEP 3135 所定义的，只在 Python 3.x 中有效。在 Python 2.x 中，你需要使用 super，如 PEP 367 所定义的：

   class Op(list):
       def __init__(self, *args):
           super(Op, self).__init__(args)
   

2. 为每个运算符创建简单的 Op 子类。为了调试，你可能想实现一个自定义的 __str__ 方法：

   class Neg(Op):
       def __str__(self):
           return '!(%s)' % tuple(self)
   class And(Op):
       def __str__(self):
           return '(%s) & (%s)' % tuple(self)
   class Or(Op):
       def __str__(self):
           return '(%s) | (%s)' % tuple(self)
   class AX(Op):
       def __str__(self):
           return 'AX (%s)' % tuple(self)
   ...
   

   现在，公式 !(a & b) 可以表示为 Neg(And('a', 'b'))。

3. 创建 非常简单 的函数，每个函数只应用一次特定的变换。这会保持实现的简洁。为这些函数 添加注释，说明它们应该如何应用。一个 前序 函数应该从上到下应用：先变换表达式树的根节点，然后递归。一个 后序 函数应该在递归应用到子表达式后再应用于表达式。使用 isinstance 来检查连接词的类型。

   1. 我们从简单开始：函数 removeDoubleNeg 用来去掉双重否定：

      @expressionTransformation('postorder')
      def removeDoubleNeg(expr):
          if isinstance(expr, Neg) and isinstance(expr[0], Neg):
              return expr[0][0]
      

   2. 接下来，定义德摩根定律之一：

      @expressionTransformation('preorder')
      def deMorgan(expr):
          if isinstance(expr, Neg) and isinstance(expr[0], And):
              return Or(Neg(expr[0][0]), Neg(expr[0][1]))
      

   3. 现在是这个问题的核心函数：

      @expressionTransformation('preorder', 'postorder')
      def distribute(expr):
          if isinstance(expr, And):
              if isinstance(expr[0], Or):
                  return Or(And(expr[0][0], expr[1]), And(expr[0][1], expr[1]))
              if isinstance(expr[1], Or):
                  return Or(And(expr[0], expr[1][0]), And(expr[0], expr[1][1]))
      

      哇！这段代码少了很多！

4. 那么，这个是怎么工作的呢？注意，任何简单的表达式变换 f 的实现都会涉及一些重复的代码：

   1. 测试参数是否是连接词（而不是常量或变量）。
   2. 尝试将 f 应用到表达式树的根节点。
   3. 递归。
   4. 返回结果。

   根据 f 的不同，第1步和第2步可能需要调换顺序（后序 而不是 前序）。不过，每个 f 的实现看起来都会差不多。你会想要避免重复的代码，尤其是如果你打算定义更多的变换。正是因为缺少这些重复的代码，前面定义的函数才如此简洁（因此也更容易调试！）。函数 expressionTransformation 返回的装饰器解决了这个问题。它的实现如下：

   from functools import wraps
   def expressionTransformation(*args):
       def wrap(f):
           @wraps(f)
           def recursiveTransformation(expr):
               if not isinstance(expr, Op):
                   return expr
               if 'postorder' in args:
                   expr[:] = map(recursiveTransformation, expr)
               res = f(expr)
               expr = expr if res is None else res 
               if 'preorder' in args:
                   expr[:] = map(recursiveTransformation, expr)
               return expr
           return recursiveTransformation
       return wrap
   

   这里发生的事情是：

   1. 函数 expressionTransformation 返回一个装饰器（名为 wrap），它接收变换函数 f 作为参数。
   2. wrap 返回一个递归函数 recursiveTransformation，它只在参数 expr 是连接词时才应用 f。
   3. 根据传给 expressionTransformation 的参数 args，f 会在应用于子表达式之前或之后（或同时在之前和之后）被应用。
   4. 假设 f 可能在没有变换的情况下返回 None。

   使用 functools.wraps 来复制 f 的某些属性，比如它的名称，给 recursiveTransformation。这个功能不是必需的。

   （注意，有更高效的方法来创建前序和后序变换，而不是一次又一次地使用测试 'postorder' in args 和 'preorder' in args，但我选择这种方式是为了清晰。）

5. 就这样。我们现在可以轻松地组合这些函数（注意这个函数不应该被装饰）：

   def toDNF(expr):
       return distribute(removeDoubleNeg(deMorgan(expr)))
   

6. 你可以用这样的语句来测试代码：

   toDNF(AX(And(Or('a', 'b'), And(Or('c', 'd'), Or('e', 'f')))))
   toDNF(Neg(And(Or(Neg(Neg('a')), 'b'), And(Or('c', 'd'), Or('e', 'f')))))