Различные результаты по доходности против возврата

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  ^^^^^^^^^

Версия без возврата работает, потому что вы возвращаете списки, которые могут повторяться снова, в отличие от генераторов. Также обратите внимание, что вы перебираете только 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