Parse Tree

이진트리 애플리케이션

파스 트리

트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다.

http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png

다음은 간단한 수학식을 트리로 표현한 것이다.

             *
           /   \
          +     -
         / \   / \
        7   3  5  2

> ( 7 + 3) * ( 5 - 2 )

이와 같이 트리로 표현한 수식은 연자의 우선순위를 알 수 있으므로 괄호로 계산 순서를 표시해주지 않아도 된다. 트리를 따라가면서 계산하려면 최상위의 연산을 수행하기 이전에 그 아래에의 연산을 먼저 수행해야 한다. 그렇다면 수식을 트리로 바꾸는 작업과, 이렇게 트리로 구성한 수식을 계산하는 법 그리고 트리로부터 원래의 수식을 복원하는 법에 대해서 살펴보자.

수식을 트리로 파싱하기

트리를 구성하기 위해서는 수식 문자열을 각각의 토큰으로 분해해야 한다. 토큰에는 크게 4종류가 있는데 1) 왼쪽 괄호, 2) 오른쪽 괄호, 3) 연산자 4) 피연산자가 있다. 왼쪽 괄호를 만나게 되면 이는 새로운 수식을 시작한다는 의미이다. 그리고 오른쪽 괄호를 만나면 그 새로운 수식이 종료된다는 의미이다. 또 피 연산자는 트리에서 ‘잎’에 해당하며 연산자의 자식 노드가 될 것이다. 따라서 규칙을 정리하면

  1. 현재 토큰이 '('이면 현재 노드에서 새로운 왼쪽 자손을 만들고 아래로 내려간다.
  2. 현재 토큰이 연산자이면 현재 노드의 루트 값은 연산자가 된다. 그리고 현재 토큰의 오른족에 자식 노드를 만들고 그 곳으로 내려 간다.
  3. 토큰이 숫자이면 현재 노드의 루트값은 그 숫자가 되고, 부모 노드로 올라간다.
  4. 현재 토큰이 ')'이면 부모 노드로 올라간다.

먼저 트리 구축을 위해서 트리 구성을 위한 노드 클래스를 간단히 구현해 보았다.

class Node:

    def __init__(self, value=None):
        self._rootValue = value
        self._parent = None
        self._leftChild = None
        self._rightChild = None

    @property
    def isLeaf(self):
        return self._leftChild is None and self._rightChild is None

    @property
    def isRoot(self):
        return self._parent is None

    @property
    def parentNode(self):
        return self._parent

    @parentNode.setter
    def parentNode(self, node):
        self._parent = node

    @property
    def leftChild(self):
        return self._leftChild

    @leftChild.setter
    def leftChild(self, value):
        self._leftChild = value

    @property
    def rightChild(self):
        return self._rightChild

    @rightChild.setter
    def rightChild(self, value):
        self._rightChild = value

    def getRootValue(self):
        return self._rootValue

    def setRootValue(self, item):
        self._rootValue = item

    def insertLeftNode(self, item):
        newChild = Node(item)
        if self._leftChild is not None:
            newChild.leftChild = self.leftChild
        self.leftChild = newChild
        newChild.parentNode = self

    def insertRightNode(self, item):
        newChild = Node(item)
        if self.rightChild is not None:
            newChild.rightChild = self.rightChild
        self.rightChild = newChild
        newChild.parentNode = self

이제 위의 규칙을 바탕으로 수식을 트리로 변환하는 함수를 짜본다.

def buildParseTree(expStr):
    tokens = expStr.split()
    rootNode = Node()
    currentNode = rootNode
    ops = ['*', '/', '+', '-']
    for t in tokens:
        if t is '(':
            currentNode.insertLeftNode(None)
            currentNode = currentNode.leftChild
        elif t is ')':
            currentNode = currentNode.parentNode
        elif t in ops:
            currentNode.setRootValue(t)
            currentNode.insertRightNode(None)
            currentNode = currentNode.rightChild
        else:
            # print(t)
            currentNode.setRootValue(t)
            currentNode = currentNode.parentNode
    return rootNode

트리 내용 확인을 위한 순회함수를 짜보자. 트리 순회 중에서 post-order로 순회한다. 이 순회방법은 root 값을 언제 표시할 것이냐는 것인데, post-order는 왼쪽자식, 오른쪽자식을 순회한 후 자신의 값을 출력하는 방식이다.

def postOrder(tree):
    if tree is None:
        return
    assert isinstance(tree, Node)
    postOrder(tree.leftChild)
    postOrder(tree.rightChild)
    print(tree.getRootValue())

재귀적으로 자식노드를 순회하는 구조이므로 함수 자체는 매우 간단하다. 여기서 각 행의 위치만 바꿔주면 순회 방식을 변경하는 게 된다. 테스트용 수식을 넣고 파싱해보자.

pt = buildParseTree("( ( 10 + 5 ) * 3 )")
postOrder(pt)

이 트리를 계산하는 함수는 어떻게 만들까? 역시 트리의 구성을 재귀적으로 따르면 된다.

  1. 루트 값이 숫자이면 자신을 반환
  2. 루트 값이 연산자이면 왼쪽 노드와 오른쪽 노드를 각각 평가한 결과값을 연산자로 계산한 결과값을 리턴
  3. 2의 각각의 평가는 좌,우 노드에 대에 재귀적으로 반복

이를 구현한 코드는 다음과 같다. 연산자 구분에 따른 계산을 좀 편하게 하려고 별도의 클래스를 하나 만들었다.

class Operator:
    @classmethod
    def add(self, a, b):
        return a + b

    @classmethod
    def sub(self, a, b):
        return a - b

    @classmethod
    def mul(self, a, b):
        return a * b

    @classmethod
    def div(self, a, b):
        return a / b


def evalTree(tr):
    ops = {
        '*': Operator.mul,
        '/': Operator.div,
        '+': Operator.add,
        '-': Operator.sub
    }
    v = tr.getRootValue()
    if v in ops:
        return ops[v](evalTree(tr.leftChild), evalTree(tr.rightChild))
    else:
        if '.' in v:
            return float(v)
        else:
            return int(v)

끝으로 트리를 가지고 다시 계산식을 재구축하는 함수이다. in-order 방식으로 순회하면서 루트값이 연산자인 경우, 해당 노드의 값 앞, 뒤에 괄호를 붙여주기만 하면 된다.

def buildExp(tree):
output = []

def trasavel(output, tree):
    if tree is None:
        return
    assert isinstance(tree, Node)
    v = tree.getRootValue()
    if v in '*-/+':
        output.append('(')
    trasavel(output, tree.leftChild)
    output.append(tree.getRootValue())
    trasavel(output, tree.rightChild)
    if v in '*-/+':
        output.append(')')
trasavel(output, tree)
return " ".join(output)