표현식 트리란?
표현식 트리(Expression Tree)는 리프 노드(leaf node)에 연산의 대상이 되는 값(피연산자)이 위치하고, 내부 노드(internal node)에는 해당 값들에 대해 수행할 연산자(operator)가 담기는 이진 트리입니다.
이러한 구조 덕분에 트리를 순회하는 방식에 따라 중위(infix), 전위(prefix), 후위(postfix) 표기식을 손쉽게 얻을 수 있어 컴파일러와 계산기 프로그램 등에서 널리 활용됩니다.
예시
다음 수식 4 + ((7 + 9) × 2) 는 아래와 같은 표현식 트리로 나타낼 수 있습니다.
여기서 '+'와 '*' 같은 연산자는 내부 노드에, 숫자 4, 7, 9, 2는 리프 노드에 배치됩니다.
표현식 트리 평가 알고리즘
완성된 표현식 트리 T의 값을 계산하는 절차는 다음과 같습니다.
If T is not NULL:
If T->data is an operand:
return T.data
A = solve(T.left)
B = solve(T.right)
--> A와 B에 대해 'T.data' 연산자를 적용하고 재귀 호출,
return calculate(A, B, T.data)
즉, 왼쪽 서브트리와 오른쪽 서브트리를 각각 재귀적으로 평가한 뒤, 그 결과값에 현재 노드의 연산자를 적용하는 방식입니다.
표현식 트리를 구성하는 방법
주어진 표현식으로부터 표현식 트리를 만들 때는 일반적으로 스택(Stack) 자료구조를 사용합니다. 특히 후위 표기식(postfix expression)을 순서대로 읽으면서 다음 단계를 따르면 됩니다.
- 피연산자를 만난 경우: 해당 값을 스택에 push합니다. 이 노드는 표현식 트리의 루트(또는 서브트리의 루트)가 됩니다.
- 연산자를 만난 경우: 스택에서 두 값을 pop하여 해당 연산자 노드의 왼쪽·오른쪽 자식으로 붙인 뒤, 이 새로운 노드를 다시 스택에 push합니다.
- 반복: 위 과정을 후위 표기식의 모든 항목을 처리할 때까지 반복합니다.
- 검증: 마지막으로 모든 내부(루트) 노드에는 연산자만, 모든 리프(자식) 노드에는 피연산자 값만 들어 있는지 확인합니다.
모든 입력을 처리한 후 스택에 남아 있는 단 하나의 노드가 곧 완성된 표현식 트리의 루트가 됩니다.