표현식 트리(Expression Tree)란?
표현식 트리는 이진 트리의 한 종류로, 리프 노드(단말 노드)에는 연산 대상이 되는 값, 즉 피연산자가 저장되고 내부 노드에는 해당 값들에 적용할 연산자가 저장됩니다. 완성된 트리를 순회하면 원래의 수식을 그대로 복원할 수 있습니다.
예시: 4 + ((7 + 9) * 2)를 표현식 트리로 나타내면 다음과 같습니다.
문제 해결 접근 방식
후위 표기식(postfix)으로 주어진 표현식의 트리를 구성할 때는 일반적으로 스택(Stack) 자료구조를 활용합니다. 표현식을 순회하면서 다음 단계를 반복 수행합니다.
- 피연산자를 만나면 새 노드를 생성해 스택에 push 합니다.
- 연산자를 만나면 스택에서 노드 두 개를 pop 하여 해당 연산자 노드의 오른쪽·왼쪽 자식으로 연결한 뒤, 연산자 노드를 다시 스택에 push 합니다.
- 표현식 전체가 처리될 때까지 위 과정을 반복하며, 마지막에 스택에 남은 노드가 표현식 트리의 루트가 됩니다.
아래 예제 코드는 후위 표기식의 마지막 문자(항상 연산자)를 루트로 정하고, 나머지 문자열을 역순으로 순회하면서 각 노드의 오른쪽 자식과 왼쪽 자식을 차례로 채워 나가는 방식으로 트리를 구성합니다.
파이썬 구현 코드
class stack:
def __init__(self):
self.arr = []
def push(self, data):
self.arr.append(data)
def pop(self):
try:
return self.arr.pop(-1)
except:
pass
def top(self):
try:
return self.arr[-1]
except:
pass
def size(self):
return len(self.arr)
# 표현식 트리의 노드 클래스
class node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# 표현식 트리 클래스
class exp_tree:
def __init__(self, postfix_exp):
self.exp = postfix_exp
self.root = None
self.createTree(self.exp)
def isOperator(self, char):
optr = ["+", "-", "*", "/", "^"]
if char in optr: # 연산자이면 True 반환
return True
return False # 피연산자이면 False 반환
def createTree(self, exp):
s = stack()
# 후위 표기식의 마지막 문자는 항상 연산자이므로 루트가 됨
self.root = node(exp[-1])
s.push(self.root)
# 나머지 표현식을 역순으로 순회
for i in "".join(reversed(exp[:-1])):
curr_node = s.top()
if not curr_node.right:
# 현재 노드의 오른쪽 자식이 비어 있는 경우
temp = node(i)
curr_node.right = temp
if self.isOperator(i):
s.push(temp)
else:
# 현재 노드의 왼쪽 자식이 비어 있는 경우
temp = node(i)
curr_node.left = temp
# 자식이 모두 채워졌으므로 현재 노드를 pop
s.pop()
if self.isOperator(i):
s.push(temp)
def inorder(self, head):
# 중위 순회: 왼쪽 → 루트 → 오른쪽
if head.left:
self.inorder(head.left)
print(head.data, end=" ")
if head.right:
self.inorder(head.right)
def infixExp(self):
# 표현식 트리를 중위 순회하면 중위 표기식이 얻어짐
self.inorder(self.root)
print()
if __name__ == "__main__":
postfixExp = "ab+ef*g*-"
et = exp_tree(postfixExp)
et.infixExp()
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
(a + b - e * f * g)
설명:
후위 표기식 ab+ef*g*-로 트리를 구성하면 피연산자(a, b, e, f, g)는 리프 노드에, 연산자(+, -, *)는 내부 노드에 배치됩니다. 완성된 트리를 중위 순회(왼쪽 → 루트 → 오른쪽)하면 원래의 중위 표기식인 a + b - e * f * g가 그대로 출력되는 것을 확인할 수 있습니다.