[자료구조] 이진트리 응용 - 평가트리 (in python)

강의출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님

코드 결과)

https://github.com/nyunu/data_structure/blob/main/%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC.ipynb

GitHub - nyunu/data_structure

 

---

평가트리

평가트리란 ?

: 이진 트리에 저장된 수식을 탐색하면서 값을 계산할 수 있는 트리

-> 노드 구조

• left, right : 연결 링크
• data : 노드가 가지고 있는 값
• value : 수식의 계산 값

 

[예제 1] 논리 연산식 평가

• data : boolean variable (T, F) or logical operation (Not, And, Or)
• 재귀함수를 사용하여 풀이
• 각 노드가 담고 있는 data가 무엇이냐에 따라 계산한 결과를 value에 저장
  = data의 값에 따라 value값을 변경

class Node:
  def __init__(self, item):
    self.data = item
    self.value = None
    self.rchild = None
    self.lchild = None

class Tree:
  def evaluateBool(self, node):
    if node:
      self.evaluateBool(node.lchild)
      self.evaluateBool(node.rchild)
      if node.data == 'or':
        node.value = node.lchild.value or node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == 'and':
        node.value = node.lchild.value and node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == 'not':
        node.value = not node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == 'TRUE':
        node.value = True
        print("%3s"%node.data, ':', node.value)
      elif node.data == 'FALSE':
        node.value = False
        print("%3s"%node.data, ':', node.value)
      else:
        print("%3s"%node.data, ':', node.value)

 

[예제 2] 산술 연산식 평가

• data: 정수, 산술 연산자 (+, -, *, ...)
• 재귀함수를 사용하여 풀이
• 각 노드가 담고 있는 data가 무엇이냐에 따라 계산한 결과를 value에 저장

class Node:
  def __init__(self, item):
    self.data = item
    self.value = None
    self.rchild = None
    self.lchild = None

class Tree:
  def evaluate(self, node):
    if node:
      self.evaluate(node.lchild)
      self.evaluate(node.rchild)
      if node.data == '+':
        node.value = node.lchild.value + node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == '-':
        node.value = node.lchild.value - node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == '*':
        node.value = node.lchild.value * node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == '/':
        node.value = node.lchild.value // node.rchild.value
        print("%3s"%node.data, ':', node.value)
      elif node.data == '%':
        node.value = node.lchild.value % node.rchild.value
        print("%3s"%node.data, ':', node.value)
      else:
        node.value = int(node.data)
        print("%3s"%node.data, ':', node.value)