표현식 트리(Expression Tree)란?
표현식 트리는 수학적 표현식을 트리 구조로 표현한 특수한 형태의 이진 트리입니다. 이 트리에서 각 노드는 연산자(operator) 또는 피연산자(operand) 중 하나로만 구성됩니다.
노드의 역할
표현식 트리에서 노드의 위치에 따라 그 역할이 달라집니다.
- 잎 노드(Leaf Node): 트리의 가장 끝에 있는 노드로, 항상 피연산자(상수 또는 변수)를 나타냅니다.
- 비잎 노드(Non-leaf Node): 자식 노드를 가지는 내부 노드로, 항상 연산자(+, -, *, / 등)를 나타냅니다.
예제
다음은 표현식 트리의 대표적인 예입니다.
위 트리에서 잎 노드들은 숫자나 변수 같은 피연산자를 담고 있으며, 부모 노드들은 두 자식 노드의 값에 적용되는 연산자를 담고 있습니다.
트리 순회를 통한 표현식 추출
표현식 트리의 가장 큰 장점은 순회(traversal) 방식에 따라 서로 다른 형태의 표현식을 얻을 수 있다는 점입니다.
- 중위 순회(Inorder Traversal): 왼쪽 자식 → 루트 → 오른쪽 자식 순서로 방문하며, 사람이 쉽게 이해하고 계산할 수 있는 중위 표기식(infix expression)을 얻습니다.
- 전위 순회(Preorder Traversal): 루트 → 왼쪽 자식 → 오른쪽 자식 순서로 방문하며, 전위 표기식(prefix expression)을 얻습니다.
- 후위 순회(Postorder Traversal): 왼쪽 자식 → 오른쪽 자식 → 루트 순서로 방문하며, 컴파일러와 계산기에서 널리 사용되는 후위 표기식(postfix expression)을 얻습니다.
따라서 쉽게 해석할 수 있는 중위 표기식을 얻으려면 트리를 중위 순회 방식으로 탐색해야 합니다. 이처럼 표현식 트리는 컴파일러의 식 분석, 수식 계산기 구현 등 다양한 분야에서 활용되는 핵심 자료구조입니다.