8.22 不用递归实现访问者模式

    通过巧妙的使用生成器可以在树遍历或搜索算法中消除递归。在8.21小节中，我们给出了一个访问者类。下面我们利用一个栈和生成器重新实现这个类：

    如果你使用这个类，也能达到相同的效果。事实上你完全可以将它作为上一节中的访问者模式的替代实现。考虑如下代码，遍历一个表达式的树：

    1. class UnaryOperator(Node):
    2.     def __init__(self, operand):
    3.         self.operand = operand
    4.  
    5. class BinaryOperator(Node):
    6.     def __init__(self, left, right):
    7.         self.left = left
    8.         self.right = right
    9.  
    10. class Add(BinaryOperator):
    11.     pass
    12.  
    13. class Sub(BinaryOperator):
    14.     pass
    15.  
    16. class Mul(BinaryOperator):
    17.     pass
    18.  
    19. class Div(BinaryOperator):
    20.     pass
    21.  
    22. class Negate(UnaryOperator):
    23.     pass
    24.  
    25. class Number(Node):
    26.     def __init__(self, value):
    27.         self.value = value
    28. # A sample visitor class that evaluates expressions
    29. class Evaluator(NodeVisitor):
    30.     def visit_Number(self, node):
    31.         return node.value
    32.  
    33.     def visit_Add(self, node):
    34.         return self.visit(node.left) + self.visit(node.right)
    35.  
    36.     def visit_Sub(self, node):
    37.         return self.visit(node.left) - self.visit(node.right)
    38.  
    39.     def visit_Mul(self, node):
    40.         return self.visit(node.left) * self.visit(node.right)
    41.  
    42.     def visit_Div(self, node):
    43.         return self.visit(node.left) / self.visit(node.right)
    44.  
    45.     def visit_Negate(self, node):
    46.         return -self.visit(node.operand)
    47.  
    48. if __name__ == '__main__':
    49.     # 1 + 2*(3-4) / 5
    50.     t1 = Sub(Number(3), Number(4))
    51.     t2 = Mul(Number(2), t1)
    52.     t3 = Div(t2, Number(5))
    53.     t4 = Add(Number(1), t3)
    54.     # Evaluate it
    55.     e = Evaluator()
    56.     print(e.visit(t4))  # Outputs 0.6

    如果嵌套层次太深那么上述的Evaluator就会失效：

    1. >>> a = Number(0)
    2. ... a = Add(a, Number(n))
    3. ...
    4. >>> e = Evaluator()
    5. >>> e.visit(a)
    6. Traceback (most recent call last):
    7. ...
    8.     File "visitor.py", line 29, in _visit
    9. return meth(node)
    10.     File "visitor.py", line 67, in visit_Add
    11. return self.visit(node.left) + self.visit(node.right)
    12. RuntimeError: maximum recursion depth exceeded
    13. >>>

    现在我们稍微修改下上面的Evaluator：

    1. >>> a = Number(0)
    2. >>> for n in range(1,100000):
    3. ...     a = Add(a, Number(n))
    4. ...
    5. >>> e = Evaluator()
    6. >>> e.visit(a)
    7. 4999950000
    8. >>>

    如果你还想添加其他自定义逻辑也没问题：

    1. class Evaluator(NodeVisitor):
    2.     ...
    3.     def visit_Add(self, node):
    4.         print('Add:', node)
    5.         lhs = yield node.left
    6.         print('left=', lhs)
    7.         rhs = yield node.right
    8.         print('right=', rhs)
    9.         yield lhs + rhs
    10.     ...

    下面是简单的测试：

    这一小节我们演示了生成器和协程在程序控制流方面的强大功能。避免递归的一个通常方法是使用一个栈或队列的数据结构。例如，深度优先的遍历算法，第一次碰到一个节点时将其压入栈中，处理完后弹出栈。 方法的核心思路就是这样。

    另外一个需要理解的就是生成器中yield语句。当碰到yield语句时，生成器会返回一个数据并暂时挂起。上面的例子使用这个技术来代替了递归。例如，之前我们是这样写递归：

      1. value = yield node.left

      它会将 返回给 方法，然后 方法调用那个节点相应的 方法。yield暂时将程序控制器让出给调用者，当执行完后，结果会赋值给value，

      看完这一小节，你也许想去寻找其它没有yield语句的方案。但是这么做没有必要，你必须处理很多棘手的问题。例如，为了消除递归，你必须要维护一个栈结构，如果不使用生成器，代码会变得很臃肿，到处都是栈操作语句、回调函数等。实际上，使用yield语句可以让你写出非常漂亮的代码，它消除了递归但是看上去又很像递归实现，代码很简洁。

      原文: