yield和return的不同结果

Question

我不太明白在这种情况下，yield 语句是怎么工作的。题目要求我们在没有括号的表达式中，写一个函数来生成所有可能的完全括号化（FP）表达式。比如，输入是 '1+2+3+4'，应该生成 5 个 FP 表达式：

1. (1+(2+(3+4)))
2. (1+((2+3)+4))
3. ((1+2)+(3+4))
4. ((1+(2+3))+4)
5. (((1+2)+3)+4)

我的代码如下。

OPS = ('+', '-', '*', '/')
def f(expr):
    """
    Generates FP exprs
    Recursive formula: f(expr1[op]expr2) = (f(expr1) [op] f(expr2))
    """
    if expr.isdigit(): yield expr
#       return [expr]

#   ret = []
    first = ''
    i = 0
    while i < len(expr):
        if expr[i] not in OPS:
            first += expr[i]
            i += 1
        else:
            op = expr[i]
            i += 1
            second = expr[i:]
            firstG, secondG = f(first), f(second)
            for e in ('(' + e1 + op + e2 + ')' for e1 in firstG for e2 in secondG):
                yield e
#               ret.append(e)
            first += op
#    return ret

如果我使用 return 语句（注释掉的那几行），那么代码就能按预期工作。但是，当我把它改成 yield 语句时，只得到了前 4 个结果。如果输入表达式的操作数数量增加，当然会丢失更多结果。例如，对于输入 '1+2+3+4+5'，我只得到了 8 个结果，而不是 14 个。

我最后找到了解决代码问题的方法，就是注释掉这一行 firstG, secondG = f(first), f(second)，并把这一行

for e in ('(' + e1 + op + e2 + ')' for e1 in firstG for e2 in secondG):

替换成

for e in ('(' + e1 + op + e2 + ')' for e1 in f(first) for e2 in f(second)):

这意味着因为这一行 firstG, secondG = f(first), f(second)，一些生成器的“信息”丢失了，但我还搞不清楚具体原因。你们能给我一些建议吗？

Answer 1

问题在于你在使用yield版本时，是在遍历生成器而不是列表，特别是secondG，它在第一次循环后就用完了。把这一行改成这样就可以正常工作：

firstG, secondG = f(first), list(f(second))

或者，你可以改一下你的循环：

for e in ("(%s%s%s)" % (e1, op, e2) for e1 in f(first) for e2 in f(second)):
#                               new generator object every loop  ^^^^^^^^^

非yield版本之所以能正常工作，是因为你返回的是列表，列表可以被再次遍历，而生成器则不行。另外要注意，你只遍历了一次firstG，所以它没有受到影响。

记住，这个：

r = [v for a in A for b in B]

等同于：

r = []
for a in A:
  for b in B:
    r.append(v)

这更清楚地显示了对B的重复循环。

另一个例子：

def y():
  yield 1
  yield 2
  yield 3
def r():
  return [1, 2, 3]

vy = y()
for v in vy:
  print v
for v in vy:
  print v

print "---"

vr = r()
for v in vr:
  print v
for v in vr:
  print v