[DP] 접미사 표현식 및 값 구하기 visitor

접미사 표현식과 값 구하기

# 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