pythoncookbook深入挖掘------------访问者模式

问题
你要处理由大量不同类型的对象组成的复杂数据结构，每一个对象都需要需要进行不同的处理。 比如，遍历一个树形结构，然后根据每个节点的相应状态执行不同的操作。

解决方案
这里遇到的问题在编程领域中是很普遍的，有时候会构建一个由大量不同对象组成的数据结构。 假设你要写一个表示数学表达式的程序，那么你可能需要定义如下的类：

关于访问者模式<<pythoncookbook>>里举了数学表达式的例子，并用递归和非递归两种方式实现了求值。

其中用生成器（yield)实现非递归非常巧妙，也对生成器的理解更深了。

为了加强理解，同样用递归和非递归2种方式实际了多叉树的前序和后序遍历，代码如下：

__author__ = 'zhangxa'

import types

class Node:
    pass

class Branch(Node):
    def __init__(self,children):
        assert children is not None and isinstance(children,list)
        self.children = children

    def __str__(self):
        branch_str = 'Branch['
        for child in self.children:
            branch_str += str(child)
        branch_str += ']'
        return branch_str

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

    def __str__(self):
        return 'Leaf[%s]'%self.value

class Visitor:
    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__))

class PreTreeVisitor(Visitor):
    def visit_Branch(self,node):
        print(node)
        for child in node.children:
            self.visit(child)

    def visit_Leaf(self,node):
        print(node)

class AfterTreeVisitor(Visitor):
    def visit_Branch(self,node):
        for child in node.children:
            self.visit(child)
        print(node)

    def visit_Leaf(self,node):
        print(node)

class GenTreeVisitor(Visitor):
    def gen_visit(self,node):
        stack = [node]
        last_result = None
        print('------%s------'%self.__class__)
        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:
                    print(stack.pop())
            except StopIteration:
                stack.pop()


class GeneratorAfterTreeVisitor(GenTreeVisitor):
    def visit_Branch(self,node):
        for child in node.children:
            yield child
        yield str(node)

    def visit_Leaf(self,node):
        yield str(node)


class GeneratorPreTreeVisitor(GenTreeVisitor):
    def visit_Branch(self,node):
        yield str(node)
        for child in node.children:
            yield child


    def visit_Leaf(self,node):
        yield str(node)


if __name__ == "__main__":
    t1 = Leaf(1)
    t2 = Leaf(2)
    t3 = Leaf(3)
    t4 = Branch([t1,t2,t3])

    t5 = Leaf(4)
    t6 = Leaf(5)
    t7 = Leaf(6)
    t8 = Branch([t6,t7])
    t9 = Branch([t5,t8])
    t10 = Branch([t4,t9])

    print('------after traverse------')
    tv = AfterTreeVisitor()
    tv.visit(t10)

    print('------pre traverse------')
    tv = PreTreeVisitor()
    tv.visit(t10)

    tv = GeneratorAfterTreeVisitor()
    tv.gen_visit(t10)

    tv = GeneratorPreTreeVisitor()
    tv.gen_visit(t10)

（编辑：ASP站长网）