8.22 不用遞歸實(shí)現(xiàn)訪問(wèn)者模式

問(wèn)題

你使用訪問(wèn)者模式遍歷一個(gè)很深的嵌套樹(shù)形數(shù)據(jù)結(jié)構(gòu)，并且因?yàn)槌^(guò)嵌套層級(jí)限制而失敗。你想消除遞歸，并同時(shí)保持訪問(wèn)者編程模式。

解決方案

通過(guò)巧妙的使用生成器可以在樹(shù)遍歷或搜索算法中消除遞歸。在8.21小節(jié)中，我們給出了一個(gè)訪問(wèn)者類(lèi)。下面我們利用一個(gè)棧和生成器重新實(shí)現(xiàn)這個(gè)類(lèi)：

import types

class Node:
    pass

class NodeVisitor:
    def visit(self, node):
        stack = [node]
        last_result = None
        while stack:
            try:
                last = stack[-1]
                if isinstance(last, types.GeneratorType):
                    stack.append(last.send(last_result))
                    last_result = None
                elif isinstance(last, Node):
                    stack.append(self._visit(stack.pop()))
                else:
                    last_result = stack.pop()
            except StopIteration:
                stack.pop()

        return last_result

    def _visit(self, node):
        methname = 'visit_' + type(node).__name__
        meth = getattr(self, methname, None)
        if meth is None:
            meth = self.generic_visit
        return meth(node)

    def generic_visit(self, node):
        raise RuntimeError('No {} method'.format('visit_' + type(node).__name__))

如果你使用這個(gè)類(lèi)，也能達(dá)到相同的效果。事實(shí)上你完全可以將它作為上一節(jié)中的訪問(wèn)者模式的替代實(shí)現(xiàn)?？紤]如下代碼，遍歷一個(gè)表達(dá)式的樹(shù)：

class UnaryOperator(Node):
    def __init__(self, operand):
        self.operand = operand

class BinaryOperator(Node):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class Add(BinaryOperator):
    pass

class Sub(BinaryOperator):
    pass

class Mul(BinaryOperator):
    pass

class Div(BinaryOperator):
    pass

class Negate(UnaryOperator):
    pass

class Number(Node):
    def __init__(self, value):
        self.value = value

# A sample visitor class that evaluates expressions
class Evaluator(NodeVisitor):
    def visit_Number(self, node):
        return node.value

    def visit_Add(self, node):
        return self.visit(node.left) + self.visit(node.right)

    def visit_Sub(self, node):
        return self.visit(node.left) - self.visit(node.right)

    def visit_Mul(self, node):
        return self.visit(node.left) * self.visit(node.right)

    def visit_Div(self, node):
        return self.visit(node.left) / self.visit(node.right)

    def visit_Negate(self, node):
        return -self.visit(node.operand)

if __name__ == '__main__':
    # 1 + 2*(3-4) / 5
    t1 = Sub(Number(3), Number(4))
    t2 = Mul(Number(2), t1)
    t3 = Div(t2, Number(5))
    t4 = Add(Number(1), t3)
    # Evaluate it
    e = Evaluator()
    print(e.visit(t4))  # Outputs 0.6

如果嵌套層次太深那么上述的Evaluator就會(huì)失效：

>>> a = Number(0)
>>> for n in range(1, 100000):
... a = Add(a, Number(n))
...
>>> e = Evaluator()
>>> e.visit(a)
Traceback (most recent call last):
...
    File "visitor.py", line 29, in _visit
return meth(node)
    File "visitor.py", line 67, in visit_Add
return self.visit(node.left) + self.visit(node.right)
RuntimeError: maximum recursion depth exceeded
>>>

現(xiàn)在我們稍微修改下上面的Evaluator： class Evaluator(NodeVisitor):
def visit_Number(self, node):
return node.value

    def visit_Add(self, node):
        yield (yield node.left) + (yield node.right)

    def visit_Sub(self, node):
        yield (yield node.left) - (yield node.right)

    def visit_Mul(self, node):
        yield (yield node.left) * (yield node.right)

    def visit_Div(self, node):
        yield (yield node.left) / (yield node.right)

    def visit_Negate(self, node):
        yield - (yield node.operand)

再次運(yùn)行，就不會(huì)報(bào)錯(cuò)了：

>>> a = Number(0)
>>> for n in range(1,100000):
...     a = Add(a, Number(n))
...
>>> e = Evaluator()
>>> e.visit(a)
4999950000
>>>

如果你還想添加其他自定義邏輯也沒(méi)問(wèn)題：

class Evaluator(NodeVisitor):
    ...
    def visit_Add(self, node):
        print('Add:', node)
        lhs = yield node.left
        print('left=', lhs)
        rhs = yield node.right
        print('right=', rhs)
        yield lhs + rhs
    ...

下面是簡(jiǎn)單的測(cè)試：

>>> e = Evaluator()
>>> e.visit(t4)
Add: <__main__.Add object at 0x1006a8d90>
left= 1
right= -0.4
0.6
>>>

討論

這一小節(jié)我們演示了生成器和協(xié)程在程序控制流方面的強(qiáng)大功能。避免遞歸的一個(gè)通常方法是使用一個(gè)棧或隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。例如，深度優(yōu)先的遍歷算法，第一次碰到一個(gè)節(jié)點(diǎn)時(shí)將其壓入棧中，處理完后彈出棧。visit() 方法的核心思路就是這樣。

另外一個(gè)需要理解的就是生成器中yield語(yǔ)句。當(dāng)碰到y(tǒng)ield語(yǔ)句時(shí)，生成器會(huì)返回一個(gè)數(shù)據(jù)并暫時(shí)掛起。上面的例子使用這個(gè)技術(shù)來(lái)代替了遞歸。例如，之前我們是這樣寫(xiě)遞歸：

value = self.visit(node.left)

現(xiàn)在換成yield語(yǔ)句：

value = yield node.left

它會(huì)將 node.left 返回給 visti() 方法，然后 visti() 方法調(diào)用那個(gè)節(jié)點(diǎn)相應(yīng)的 vist_Name() 方法。yield暫時(shí)將程序控制器讓出給調(diào)用者，當(dāng)執(zhí)行完后，結(jié)果會(huì)賦值給value，

看完這一小節(jié)，你也許想去尋找其它沒(méi)有yield語(yǔ)句的方案。但是這么做沒(méi)有必要，你必須處理很多棘手的問(wèn)題。例如，為了消除遞歸，你必須要維護(hù)一個(gè)棧結(jié)構(gòu)，如果不使用生成器，代碼會(huì)變得很臃腫，到處都是棧操作語(yǔ)句、回調(diào)函數(shù)等。實(shí)際上，使用yield語(yǔ)句可以讓你寫(xiě)出非常漂亮的代碼，它消除了遞歸但是看上去又很像遞歸實(shí)現(xiàn)，代碼很簡(jiǎn)潔。