문제 소개
표현식 트리(expression tree)의 후위 순회(postorder traversal) 결과가 주어졌을 때, 이를 바탕으로 트리를 다시 구축한 뒤 수식의 값을 계산하는 프로그램을 만들어 보겠습니다. 최종적으로는 표현식 트리의 루트 노드와 함께 계산된 값을 반환하면 됩니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
['1', '2', '-', '3', '4', '+', '*']
위 후위 표기법(postfix) 수식을 일반적인 중위 표기로 바꾸면 (1 − 2) × (3 + 4)이며, 계산 결과는 -7입니다. 이 입력으로 만들어지는 표현식 트리는 다음과 같은 구조를 가집니다.
*
/ \
- +
/ \ / \
1 2 3 4
해결 접근 방법
이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.
1. evaluate() — 트리 값 계산하기
- 노드의 값이 숫자라면 그대로 정수로 변환해 반환합니다.
- 그렇지 않다면(연산자라면) 왼쪽 자식과 오른쪽 자식을 재귀적으로 평가합니다.
- 루트의 연산자가 '+'이면 두 값의 합, '-'이면 차, '*'이면 곱, '/'이면 정수 나눗셈의 몫을 반환합니다.
2. buildTree() — 후위 순회로 트리 만들기
- 루트를 null로 초기화하고 빈 스택을 준비합니다.
- 후위 순회 배열이 빌 때까지 뒤에서부터 요소를 하나씩 꺼내(pop) 새 노드를 만듭니다. 가장 먼저 꺼낸 노드가 루트가 됩니다.
- 스택에 대기 중인 부모가 있다면 꺼내서, 저장된 방향(LEFT 또는 RIGHT)에 따라 현재 노드를 자식으로 연결합니다.
- 현재 노드가 연산자라면 아직 두 개의 자식이 필요하므로 (노드, LEFT), (노드, RIGHT) 순서로 스택에 추가합니다.
- 모든 요소를 처리한 뒤 루트를 반환합니다.
여기서 핵심 도구는 스택입니다. 후위 순회에서는 연산자가 피연산자보다 뒤에 위치하므로, 배열의 끝에서부터 읽으면 연산자를 먼저 만나게 됩니다. 이 연산자 노드들은 아직 채워지지 않은 두 개의 자식 자리를 스택에 등록해 두고, 이후 등장하는 피연산자 노드가 순서대로 그 자리를 채우는 방식으로 동작합니다.
구현 예제
LEFT = 0
RIGHT = 1
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def evaluate(root):
# 피연산자(숫자)라면 정수로 변환해 반환
if root.val.isnumeric():
return int(root.val)
left_val = evaluate(root.left)
right_val = evaluate(root.right)
if root.val == '+':
return left_val + right_val
elif root.val == '-':
return left_val - right_val
elif root.val == '*':
return left_val * right_val
else: # '/'
return left_val // right_val
def buildTree(postfix):
root = None
stack = []
while postfix:
curr = postfix.pop() # 뒤에서부터 하나씩 꺼냄
curr_node = Node(curr)
if not root: # 첫 번째 노드가 루트
root = curr_node
if stack: # 자식을 기다리는 부모가 있다면 연결
parent, side = stack.pop()
if side == LEFT:
parent.left = curr_node
else:
parent.right = curr_node
if not curr.isnumeric(): # 연산자라면 두 자식 자리를 스택에 등록
stack.append((curr_node, LEFT))
stack.append((curr_node, RIGHT))
return root
root = buildTree(['1', '2', '-', '3', '4', '+', '*'])
print(evaluate(root))
입력
['1', '2', '-', '3', '4', '+', '*']
출력
-7
복잡도 분석
후위 순회 배열의 각 요소를 정확히 한 번씩 처리하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 스택과 완성된 트리를 저장해야 하므로 O(n)입니다.
마무리
이처럼 후위 순회 결과와 스택만 있으면 문자열 형태의 수식을 실제 트리 구조로 복원할 수 있고, 재귀 호출만으로 손쉽게 값을 계산할 수 있습니다. 나머지 연산(%), 거듭제곱(^) 같은 연산자나 단항 연산자로 확장하면 더 복잡한 수식 계산기로 발전시킬 수도 있습니다.