식 트리(Expression Tree)는 수식을 표현하기 위해 사용되는 이진 트리(Binary Tree)입니다. 식 트리에서 내부 노드는 연산자(operator)에 해당하고, 각 리프 노드(leaf node)는 피연산자(operand)에 해당합니다.
이 글에서는 C++를 사용하여 후위 표기식(postfix expression)으로부터 식 트리를 구성하고, 이를 중위(inorder), 전위(preorder), 후위(postorder) 순회 방식으로 출력하는 프로그램을 살펴봅니다.
알고리즘
프로그램의 전체적인 동작 흐름은 다음과 같습니다.
시작
함수 r(): 문자 하나를 매개변수로 받습니다.
문자가 +, -, *, / 중 하나라면
-1을 반환합니다.
문자가 A~Z 범위라면
1을 반환합니다.
문자가 a~z 범위라면
1을 반환합니다.
그 외의 경우
-100을 반환합니다.
함수 construct_expression_tree(): 식 트리를 구성합니다.
함수 push(): 스택에 값을 삽입(push)합니다.
함수 pop(): 스택에서 값을 꺼냅니다(pop).
함수 preOrder(): 전위 순회를 수행합니다.
함수 inOrder(): 중위 순회를 수행합니다.
함수 postOrder(): 후위 순회를 수행합니다.
종료.예제 코드
아래 코드는 후위 표기식을 입력받아 스택을 활용해 식 트리를 만들고, 세 가지 순회 방법으로 결과를 출력합니다.
#include <iostream>
using namespace std;
struct n {
char d;
n *l;
n *r;
};
char pf[50];
int top = -1;
n *a[50];
int r(char inputch) {
if (inputch == '+' || inputch == '-' || inputch == '*' || inputch== '/')
return (-1);
else if (inputch >= 'A' || inputch <= 'Z')
return (1);
else if (inputch >= 'a' || inputch <= 'z')
return (1);
else
return (-100);
}
void push(n *tree) {
top++;
a[top] = tree;
}
n *pop() {
top--;
return (a[top + 1]);
}
void construct_expression_tree(char *suffix) {
char s;
n *newl, *p1, *p2;
int flag;
s = suffix[0];
for (int i = 1; s != 0; i++) {
flag = r(s);
if (flag == 1) {
newl = new n;
newl->d = s;
newl->l = NULL;
newl->r = NULL;
push(newl);
} else {
p1 = pop();
p2 = pop();
newl = new n;
newl->d = s;
newl->l = p2;
newl->r = p1;
push(newl);
}
s = suffix[i];
}
}
void preOrder(n *tree) {
if (tree != NULL) {
cout << tree->d;
preOrder(tree->l);
preOrder(tree->r);
}
}
void inOrder(n *tree) {
if (tree != NULL) {
inOrder(tree->l);
cout << tree->d;
inOrder(tree->r);
}
}
void postOrder(n *tree) {
if (tree != NULL) {
postOrder(tree->l);
postOrder(tree->r);
cout << tree->d;
}
}
int main(int argc, char **argv) {
cout << "Enter Postfix Expression : ";
cin >> pf;
construct_expression_tree(pf);
cout << "\nIn-Order Traversal : ";
inOrder(a[0]);
cout << "\nPre-Order Traversal : ";
preOrder(a[0]);
cout << "\nPost-Order Traversal : ";
postOrder(a[0]);
return 0;
}코드 동작 원리
- r() 함수: 입력된 문자가 연산자인지 피연산자인지 판별합니다. 연산자면 -1, 영문자면 1을 반환하여 트리 구성 시 분기 기준으로 사용됩니다.
- construct_expression_tree() 함수: 후위 표기식을 왼쪽에서 오른쪽으로 한 문자씩 읽으며 처리합니다. 피연산자를 만나면 새 노드를 생성해 스택에 push하고, 연산자를 만나면 스택에서 두 개의 노드를 pop하여 연산자 노드의 자식으로 연결한 뒤 다시 push합니다.
- 순회 함수들: 완성된 트리의 루트(a[0])를 기준으로 전위, 중위, 후위 순회를 재귀적으로 수행합니다.
실행 결과
Enter Postfix Expression : 762*+6+ In-Order Traversal : 7+6*2+6 Pre-Order Traversal : ++7*626 Post-Order Traversal : 762*+6+
실행 결과를 보면, 후위 순회(postorder traversal)의 결과가 원래 입력한 후위 표기식과 동일하게 출력되는 것을 확인할 수 있습니다. 이는 후위 표기식이 곧 식 트리의 후위 순회 결과와 일치하기 때문입니다.