后缀表达式与求值

# In[1]:

class Node(object):

    pass

class BinaryOperator(Node):

    def __init__(self, left, right):

        self.left = left

        self.right = right





class UnaryOperator(Node):

    def __init__(self, operator):

        self.operator = operator



class Add(BinaryOperator):

    pass

class Sub(BinaryOperator):

    pass

class Mul(BinaryOperator):

    pass

class Div(BinaryOperator):

    pass

class Neg(UnaryOperator):

    pass



class Number(Node):

    def __init__(self, value):

        self.value = value



class NodeVisitor(object):

    def visit(self, node):

        method = getattr(self,'visit_' + type(node).__name__, None)

        if method is None:

            method = self.genetic_visit

        return method(node)

    def genetic_visit(self, node):

        raise RuntimeError("No {} method".format('visit_'+type(node).__name__))



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_Neg(self, node):

        return -self.visit(node)

# Out[1]:

evaluate the expression of 1 + 2 * (3 - 4) / 5

# In[2]:

t1  = Sub(Number(3) , Number(4))

# Out[2]:

# In[3]:

t2 = Mul(Number(2), t1)

# Out[3]:

# In[4]:

t3 = Div(t2, Number(5))

# Out[4]:

# In[5]:

t4 = Add(Number(1), t3)

# Out[5]:

# In[6]:

evaluator = Evaluator()

# Out[6]:

# In[7]:

evaluator.visit(t4)

# Out[7]: 0.6

Number类相当于递归中的BaseCase， 这样递归不会是无尽地递归下去。

利用这一特点还可以写出求值过程中的后缀表达式。

implement the postfix expression operation

# In[8]:

class PostfixOperation(NodeVisitor):

    def generate_instruction(self, node):

        self.instruction = []

        self.visit(node)

        return self.instruction



    def visit_Number(self, node):

        self.instruction.append(( 'Push', node.value))



    def visit_Add(self, node):

        self.binary_op(node)

        self.instruction.append(('Add',))



    def binary_op(self, node):

        self.visit(node.left)

        self.visit(node.right)



    def visit_Sub(self, node):

        self.binary_op(node)

        self.instruction.append(('Sub',))



    def visit_Mul(self, node):

        self.binary_op(node)

        self.instruction.append(('Mul',))



    def visit_Div(self, node):

        self.binary_op(node)

        self.instruction.append(('Div',))



    def unary_op(self, node):

        self.visit(node)



    def Neg(self, node):

        self.unary_op(node)

        self.instruction.append(('Neg',))

# Out[8]:

# In[9]:

postfix_op = PostfixOperation()

# Out[9]:

# In[10]:

postfix_op.generate_instruction(t4)

# Out[10]: [(‘Push’, 1),

(‘Push’, 2),

(‘Push’, 3),

(‘Push’, 4),

(‘Sub’,),

(‘Mul’,),

(‘Push’, 5),

(‘Div’,),

(‘Add’,)]

可是，递归并不是python擅长的，印象中，最适合递归的是函数式编程语言scala,clojure等等。

所以python提供了sys.getcursionlimit(),sys.setrecursionlimi() 两个函数。

大家都知道，一切递归可以改为循环语句执行。

而对于python，对递归的最好的修改是把递归改为流控制(stream control)，具体而言就是python的生成器,当然这也是需要循环的。

# In[11]:

import types

class Node(object):

    pass

class BinaryOperator(Node):

    def __init__(self, left, right):

        self.left = left

        self.right = right





class UnaryOperator(Node):

    def __init__(self, operator):

        self.operator = operator



class Add(BinaryOperator):

    pass

class Sub(BinaryOperator):

    pass

class Mul(BinaryOperator):

    pass

class Div(BinaryOperator):

    pass

class Neg(UnaryOperator):

    pass



class Number(Node):

    def __init__(self, value):

        self.value = value



class NodeVisitor(object):

    def visit(self, node):

        last_result = None

        stack = [node]

        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):

        method = getattr(self,'visit_' + type(node).__name__, None)

        if method is None:

            method = self.genetic_visit

        return method(node)

    def genetic_visit(self, node):

        raise RuntimeError("No {} method".format('visit_'+type(node).__name__))



class Evaluator(NodeVisitor):

    def visit_Number(self, node):

        return node.value

    def visit_Add(self, node):

        lft = yield node.left

        rht = yield node.right

        yield lft + rht

    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_Neg(self, node):

        yield -(yield node.operator)

# Out[11]:

# In[12]:

t1  = Sub(Number(3) , Number(4))

t2 = Mul(Number(2), t1)

t3 = Div(t2, Number(5))

t4 = Add(Number(1), t3)

# Out[12]:

# In[13]:

e = Evaluator()

# Out[13]:

# In[14]:

e.visit(t4)

# Out[14]: 0.6