Python：递归地将操作数及其运算符组合在一个列表中

Question

我有一个包含符号和运算符的列表，如下所示：

[['B31', '+', 'W311', '*', ['B21', '+', 'W211', '*', ['B11', '+', 'W111', '*', 'x'], '+', 'W221', '*',
                                       ['B12', '+', 'W121', '*', 'x']], '+', 'W312', '*',
             ['B22', '+', 'W212', '*', ['B11', '+', 'W111', '*', 'x'], '+', 'W222', '*',
              ['B12', '+', 'W121', '*', 'x']]]]

我希望在 3 个元素的列表中将运算符及其操作数组合在一起，这里是

[['B31', '+',
          ['W311', '*',
           ['B21', '+',
            [['W211', '*', [['B11', '+', ['W111', '*', 'x']]],
             '+', ['W221', '*',
                   ['B12', '+', ['W121', '*', 'x']]]]]]]],
         '+', ['W312', '*',
               ['B22', '+',
                [['W212', '*', ['B11', '+', ['W111', '*', 'x']]],
                 '+', ['W222', '*',
                       ['B12', '+', ['W121', '*', 'x']]]]]]]]

我的算法是这样的：

def group_by_symbol(formula: Union[List, str], symbol: str) -> List:
"""
Group multiplication in formula: a op b -> [a op b]
:param formula: contains operations not inside a list.
:return: operations enclosed in a list.
"""
modified_formula = formula

# loop backwards
for i in range(len(modified_formula) - 1, -1, -1):
    if i > len(modified_formula) - 1:
        continue

    if modified_formula[i] == symbol:
        # introduce parentheses around symbol
        group = [modified_formula[i - 1], modified_formula[i], modified_formula[i + 1]]
        del modified_formula[i:i + 2]
        modified_formula[i - 1] = group
    elif isinstance(modified_formula[i], List) \
            and len(modified_formula[i]) > 3:
        # recurse
        modified_formula[i] = group_by_symbol(modified_formula[i], symbol)

return modified_formula

它的调用方式如下：

grouped = group_by_symbol(formula, '*')
grouped = group_by_symbol(grouped, '+')

但是，在同一个列表中出现多个加法的情况下，并没有创建所需的组，我得到的结果如下，其中一个列表中出现了多个+符号，而不是所有列表的大小为 3:

[[['B31', '+', [['W311', '*', ['B21', '+', ['W211', '*', ['B11', '+', ['W111', '*', 'x']]], '+',
                                               ['W221', '*', ['B12', '+', ['W121', '*', 'x']]]]],
                                '+', ['W312', '*',
                                      ['B22', '+', ['W212', '*', ['B11', '+', ['W111', '*', 'x']]], '+',
                                       ['W222', '*', ['B12', '+', ['W121', '*', 'x']]]]]]]]]

我怀疑该错误与提前退出递归有关，但是，检查子列表以仅包含条件中的字符串会导致无休止的递归。

Answer 1

我们可以通过编写一个纯函数来极大地简化程序。这里的编号注释对应下面程序中的源代码编号。

如果没有操作，op，我们就达到了基本情况。如果提供的参数 arg 是一个列表，将其转换为表达式或简单地 return arg.
通过归纳，是一个操作，op。如果提供的 arg 是一个列表，我们也需要递归地转换它。 Return 一个包含 expr(*arg)、op 和递归结果 expr(*more)
通过归纳，有一个操作，提供的 arg 是 而不是 列表。 Return 一个包含 arg、op 和递归结果 expr(*more)

tree = \
  [['B31','+','W311','*',['B21','+','W211','*',['B11','+','W111','*','x'],'+','W221','*',['B12','+','W121','*','x']],'+','W312','*',['B22','+','W212','*',['B11','+','W111','*','x'],'+','W222','*',['B12','+','W121','*','x']]]]

def expr(arg, op = None, *more):
  if not op:
    return expr(*arg) if isinstance(arg, list) else arg #1
  elif isinstance(arg, list):
    return [ expr(*arg), op, expr(*more) ]              #2
  else:
    return [ arg, op, expr(*more) ]                     #3


print(expr(tree))
# ['B31', '+', ['W311', '*', [['B21', '+', ['W211', '*', [['B11', '+', ['W111', '*', 'x']], '+', ['W221', '*', ['B12', '+', ['W121', '*', 'x']]]]]], '+', ['W312', '*', ['B22', '+', ['W212', '*', [['B11', '+', ['W111', '*', 'x']], '+', ['W222', '*', ['B12', '+', ['W121', '*', 'x']]]]]]]]]]

如果将表达式转换为字符串，也许我们可以更好地验证输出 -

def expr_to_str(expr1, op, expr2):
  return \
  f"({expr_to_str(*expr1) if isinstance(expr1, list) else expr1} {op} {expr_to_str(*expr2) if isinstance(expr2, list) else expr2})"

print(expr_to_str(*expr(tree)))
# (B31 + (W311 * ((B21 + (W211 * ((B11 + (W111 * x)) + (W221 * (B12 + (W121 * x)))))) + (W312 * (B22 + (W212 * ((B11 + (W111 * x)) + (W222 * (B12 + (W121 * x))))))))))

这是另一种使用 class -

的方法

class expr:
  def __init__(self, x, op = None, *y):
    self.op = op
    self.x = expr(*x) if isinstance(x, list) else x
    self.y = expr(*y) if y else y

  def __str__(self):
    if not self.op:
      return f"{self.x}"
    else:
      return f"({self.x} {self.op} {self.y})"

print(expr(tree))
# (B31 + (W311 * ((B21 + (W211 * ((B11 + (W111 * x)) + (W221 * (B12 + (W121 * x)))))) + (W312 * (B22 + (W212 * ((B11 + (W111 * x)) + (W222 * (B12 + (W121 * x))))))))))

varaidic 支持

在评论中，您询问 expr 是否可以支持 3 元素结果和 2 元素结果。这是一个这样灵活的实现-

在构造函数中，__init__，我们做一个简单的案例分析-

如果输入a是一个列表，并且列表少于4个元素，我们不需要分解任何东西。只需将 expr 映射到 a.
通过归纳，输入a是一个列表至少 4个元素，因此我们需要将其分解成更小的表达式。构造第一个元素expr(a[0])、第二个元素expr(a[1])和所有剩余元素的递归结果expr(a[2::])
通过归纳，输入a是不是列表，即它是单个项。将表达式的数据设置为单例，[ a ]

在__str__方法中，我们做类似的分析，将我们表达式的data转换成字符串-

当self.data为空时，return为空字符串，""
据归纳，self.data不是空。如果小于2个元素（单例），return单例结果，f"{self.data[0]}"
通过归纳，self.data是至少2个或更多元素。 return 一个 (...) 封闭的字符串，其中每个部分递归转换为 str 并与 space、" "

class expr:
  def __init__(self, a):
    if isinstance(a, list):
      if len(a) < 4:
        self.data = [ expr(x) for x in a ]                   #1
      else:
        self.data = [ expr(a[0]), expr(a[1]), expr(a[2::]) ] #2
    else:
      self.data = [ a ]                                      #3

  def __str__(self):
    if not self.data:
      return ""                                              #1 empty
    elif len(self.data) < 2:
      return f"{self.data[0]}"                               #2 singleton
    else:
      return "(" + " ".join(str(x) for x in self.data) + ")" #3 variadic

print(expr(tree))
# (B31 + (W311 * ((B21 + (W211 * ((B11 + (W111 * x)) + (W221 * (B12 + (W121 * x)))))) + (W312 * (B22 + (W212 * ((B11 + (W111 * x)) + (W222 * (B12 + (W121 * x))))))))))

print(expr([[ "¬", ["a", "+", "b"]], "and", [["length", "x"], ">", 0]]))
# ((¬ (a + b)) and ((length x) > 0))

分解

通过将一个复杂的问题分解成更小的部分，可以更容易地解决子问题，并为我们提供更多的灵活性和控制力。就其价值而言，此技术不依赖于 Python 的特定 OOP 机制。这些是普通的、定义明确的纯函数 -

def unit(): return ('unit',)
def nullary(op): return ('nullary', op)
def unary(op, a): return ('unary', op, a)
def binary(op, a, b): return ('binary', op, a, b)

现在使用我们之前所做的平面案例分析，我们实现我们的递归表达式构造函数 expr -

如果输入a不是一个列表，它是一个单一的值。用 a

nullary

通过归纳，输入是一个列表。如果列表为空，则构造一个空结果，即 unit 表达式。
通过归纳，输入不是一个空列表。如果它只包含一个元素，构造一个 nullary 表达式，其中只有一个元素 expr(a[0])
通过归纳，输入包含至少两个元素。如果输入恰好是两个元素，构造一个unary表达式，其中expr(a[0])和expr(a[1])
通过归纳，输入包含至少三个元素。如果输入运算符is_infix位置，则转换为前缀位置。构造一个binary表达式，expr(a[0])和expr(a[1])交换位置，递归结果expr(a[2::])
通过归纳，输入包含至少三个元素 而不是 在中缀位置。构造expr(a[0])和expr(a[1])的普通（前缀位置）binary表达式和递归结果expr(a[2::])

infix_ops = set([ '+', '-', '*', '/', '>', '<', 'and', 'or' ])

def is_infix (a):
  return a[1] in infix_ops

def expr(a):
  if not isinstance(a, list):
    return nullary(a)                                    #1
  elif len(a) == 0:
      return unit()                                      #2
  elif len(a) == 1:
    return nullary(expr(a[0]))                           #3
  elif len(a) == 2:
    return unary(expr(a[0]), expr(a[1]))                 #4
  elif is_infix(a):
    return binary(expr(a[1]), expr(a[0]), expr(a[2::]))  #5
  else:
    return binary(expr(a[0]), expr(a[1]), expr(a[2::]))  #6

现在看结果-

tree2 = \
  [[ "¬", ["a", "+", "b"]], "and", [["length", "x"], ">", 0]]

print(expr(tree2))
# ('binary', ('nullary', 'and'), ('unary', ('nullary', '¬'), ('binary', ('nullary', '+'), ('nullary', 'a'), ('nullary', ('nullary', 'b')))), ('nullary', ('binary', ('nullary', '>'), ('unary', ('nullary', 'length'), ('nullary', 'x')), ('nullary', ('nullary', 0)))))

这只是一种可能的表达方式。因为我们使用 tuple 实现了表达式，所以 Python 能够打印出来，尽管很冗长。相比之下，这里是 Python 选择表示对象的方式 -

class foo: pass
f = foo()
print(f)
# <__main__.foo object at 0x7f2ba03bc8e0>

这里重要的是我们的表达式数据结构是明确定义的，我们可以轻松地对其执行计算或以其他方式表示它 -

def expr_to_str(m):
  if not isinstance(m, tuple):
    return str(m)
  elif m[0] == "unit":
    return ""
  elif m[0] == "nullary":
    return expr_to_str(m[1])
  elif m[0] == "unary":
    return f"({expr_to_str(m[1])} {expr_to_str(m[2])})"
  elif m[0] == "binary":
    return f"({expr_to_str(m[1])} {expr_to_str(m[2])} {expr_to_str(m[3])})"
  else:
    raise TypeError("invalid expression type", m[0])

print(expr_to_str(expr(tree2)))
# (and (¬ (+ a b)) (> (length x) 0))

计算表达式

那么如果我们想要评估我们的表达式之一呢？

m = expr([3, "+", 2, "*", 5, "-", 1])

print(expr_to_str(m))
# (+ 3 (* 2 (- 5 1)))

print(eval_expr(m))
# 11

你只差几步就能写出 eval_expr -

def eval_expr(m):
  if not isinstance(m, tuple):
      return m
  elif m[0] == "unit":
    return None
  elif m[0] == "nullary":
    return eval0(m[1])
  elif m[0] == "unary":
    return eval1(m[1], m[2])
  elif m[0] == "binary":
    return eval2(m[1], m[2], m[3])
  else:
    raise TypeError("invalid expression type", m[0])

看，将复杂的问题分解成小部分会更容易。现在我们只写 eval0、eval1 和 eval2 -

def eval0(op):
  return eval_expr(op)

def eval1(op, a):
  if op == expr("not"):      # or op == expr("¬") ...
    return not eval_expr(a)
  elif op == expr("neg"):    # or op == expr("~") ...
    return -eval_expr(a)
  # +, ++, --, etc...
  else:
    raise ValueError("invalid op", op)

def eval2(op, a, b):
  if op == expr("+"):
      return eval_expr(a) + eval_expr(b)
  elif op == expr("-"):
    return eval_expr(a) - eval_expr(b)
  elif op == expr("*"):
    return eval_expr(a) * eval_expr(b)
  elif op == expr("/"):
    return eval_expr(a) / eval_expr(b)
  elif op == expr("and"):
    return eval_expr(a) and eval_expr(b)
  # >, <, or, xor, etc...
  else:
    raise ValueError("invalid op", op)

现在让我们看看混合表达式 -

print(eval_expr(expr([True, 'and', ['not', False]])))
# True

print(eval_expr(expr(['neg', [9, '*', 11]])))
# -99

print(eval_expr(expr(['stay', '+', 'inside'])))
# 'stayinside'

您甚至可以定义自己的函数 -

def eval1(op, a):
  # ...
  elif op == expr('scream'):
    return eval_expr(a).upper() # make uppercase!
  else:
    raise ValueError("invalid op", op)

并在你的表达式中使用它们 -

print(eval_expr(expr(["scream", ["stay", "+", "inside"]])))
# 'STAYINSIDE'

Python：递归地将操作数及其运算符组合在一个列表中

Python: Recursively group operands together with their operators in a list

python

recursion

parsing

operators

formula