티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
이진 트리를 이용해서 수식을 표현해 놓은 것을 가리켜 '수식 트리'라고 합니다. 즉 수식 트리는 이전 트리와 구분이 되는 별개의 것이 아닙니다. 먼저 다음의 수식을 보겠습니다.
7 + 4 * 2 - 1
우리는 보통 이러한 수식을 컴퓨터가 스스로 알아서 인식할 수 있다고 생각합니다. 그렇다면 컴파일러는 어떻게 이러한 수식을 처리하는 걸까요? 알다시피 컴파일러는 위의 코드를 실행이 가능한 상태로 만드는 소프트웨어입니다. 그런데 그 방법을 인간이 결정하여 컴파일러에게 인식시킨다는 사실을 놓치는 경우가 종종 있습니다.
컴퓨터의 유연한 판단을 유도하는 것은 쉽지 않습니다. 때문에 가급적 정해진 일련의 과정을 거쳐서 수식을 인식할 수 있도록 도와야 합니다. 그리고 이를 위해서 수식 트리라는 것을 활용합니다. 결론은 수식을 수식 트리로 표현하면 컴파일러의 수식 해석이 좋아진다는 것입니다. 따라서 컴파일러는 수식의 이해를 위해서 수식을 수식 트리로 재 표현합니다.
앞서 소개한 위 수식을 수식 트리로 표현하면 다음과 같습니다.
그런데 위 수식 트리를 보면서, 수식 트리가 중위 표기법을 사용하는지, 후위 표기법을 사용하는지 궁금할 수 있습니다. 수식 트리는 그냥 수식 트리일 뿐입니다. 중위 표기법이나 후위 표기법이 수식 표현의 한 가지 방법이라면 수식 트리도 이와 대등한, 수식을 표현하는 또 다른 방법일 뿐입니다.
수식 트리의 계산 방법에 대해 설명하겠습니다.
수식 트리의 루트 노드의 연산자에 해당하는 연산을 수행하되, 그의 자식 노드를 인자로 하여 계산합니다. 만약 자식 노드가 연산자라면 그 노드에 대해 똑같은 알고리즘을 적용합니다. 즉, 위 수식 트리의 루트 노드는 '-'이므로 자식 노드를 인자로 받아 연산합니다. 그런데 왼쪽 자식 노드가 '+'연산자입니다. 따라서 '+' 노드의 자식 노드를 인자로 받아 +연산을 수행해야 합니다. 그런데 이번에는 오른쪽 자식 노드가 '*'연산자입니다. 따라서 *노드의 자식 노드를 인자로 받아 *연산을 먼저 수행합니다. 그리고 그 결과를 반환합니다.
그림으로 표현하면 다음과 같습니다.
4와 2를 곱하는 연산을 먼저 수행합니다.
4와 2를 곱한 연산 결과인 8이 반환되고, 7과 8을 더하는 연산을 수행합니다.
7과 8을 더한 연산 결과가 반환되고, 15에서 1을 빼는 연산을 수행합니다. 결과적으로 14가 반환됩니다.
이렇듯 수식 트리는 연산의 순서가 명확하고, 연산의 과정을 쉽게 파악할 수 있는 이진 트리의 일종입니다. 이제 수식 트리를 구성하는 방법에 대해서 고민할 차례입니다. 그런데 중위 표기법의 수식을 곧장 수식 트리로 표현하는 것은 복잡하고도 힘든 일입니다. 하지만 후위 표기법의 수식을 수식 트리로 표현하는 것은 비교적 간단합니다. 따라서 중위 표기법의 수식을 후위 표기법의 수식으로 변환하여 이를 이용해 수식 트리로 만드는 프로그램을 작성합니다.
수식 트리를 만들기 위해 우리는 앞서 정의했던 이진 트리와 스택을 활용해야 합니다. 이진 트리를 정의한 파일의 이름이 다음과 같다고 가정하겠습니다.
- BinaryTree.h
- BinaryTree.h
그리고 다음은 수식 트리의 표현을 위한 헤더 파일입니다.
//ExpressionTree.h 헤더 파일로 저장
#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H
#include "BinaryTree.h"
BTreeNode* MakeExpTree(char exp[]); //수식 트리 구성
int EvaluateExpTree(BTreeNode* bt); //수식 트리 계산
void ShowPrefixTypeExp(BTreeNode* bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode* bf); //중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode* bt); //후위 표기법 기반 출력
#endif위 헤더 파일에서,
BTreeNode* MakeExpTree(char exp[]); //수식 트리 구성위 함수는 후위 표기법의 수식을 문자열의 형태로 입력받으며, 이를 기반으로 수식 트리를 구성하고 그 수식 트리의 주소 값, 정확히는 수식 트리의 루트 노드의 주소 값을 반환합니다.
int EvaluateExpTree(BTreeNode* bt); //수식 트리 계산위 함수는 인자로 전달된 수식 트리의 수식을 계산하여 그 결과를 반환하는 함수입니다. 마지막으로 수식 트리의 구성을 검증하기 위해서 다음 세 함수를 추가로 정의했습니다. 이들은 각자 수식 트리의 수식을 전위, 중위, 후위 표기법으로 출력하는 기능의 함수입니다.
void ShowPrefixTypeExp(BTreeNode* bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode* bf); //중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode* bt); //후위 표기법 기반 출력위 세 함수들은 트리의 순회와 관련이 있어서 구현이 어렵지는 않습니다. 예를 들어서 수식 트리를 후위 순회하면서 노드의 데이터를 출력하면 그 결과가 후위 표기법의 수식이 됩니다.
이제부터 함수를 구현해 볼 차례입니다. 먼저 수식 트리를 구성하는 MakeExpTree 함수의 구현을 위해서, 후위 표기법의 수식을 수식 트리로 표현하는 방법을 알아야 합니다. 아래의 수식을 대상으로 수식 트리를 구성하는 방법을 고민해 보길 바랍니다.
1 2 + 7 *
앞서 후위 표기법의 수식을 계산할 때는 다음과 같은 알고리즘을 따랐습니다.
- 맨 앞에서부터 읽는다.
- 읽은 데이터가 피연산자면 우선 스택에 저장한다.
- 읽은 데이터가 연산자면 스택에서 데이터를 2개 꺼내어, 두 번째 피연산자를 첫 번째 피연산자로 연산하고, 그 결과를 스택에 저장한다.
후위 표기법의 수식을 계산하는 수식 트리의 구성도 이런 알고리즘과 똑같은 알고리즘을 따릅니다. 차이가 있다면 데이터 그 자체를 스택에 저장하는 것이 아닌, 데이터를 가지고 있는 노드의 주소를 스택에 저장한다는 것입니다. 만약 읽은 데이터가 피연산자라면 해당 피연산자를 새로운 노드에 저장하고, 그 노드의 주소를 스택에 저장합니다. 그리고 읽은 데이터가 연산자라면 해당 연산자를 새로운 노드에 저장하고, 스택에서 두 개의 노드 주소를 꺼내어 두 번째 노드를 왼쪽, 첫 번째 노드를 오른쪽에 연결합니다. 그리고 그렇게 완성된 트리의 루트 노드의 주소를 다시 스택에 저장합니다.
이를 구현하면 다음과 같습니다.
BTreeNode* MakeExpTree(char exp[]) //수식 트리 구성
{
Stack stack; //스택 생성
int expLen = strlen(exp); //수식의 길이 저장
int i;
for (i = 0; i < expLen; i++)
{
BTreeNode* newTreeNode = (BTreeNode*)malloc(sizeof(BTreeNode)); //새로운 노드 생성
if (newTreeNode == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
newTreeNode->left = NULL;
newTreeNode->right = NULL;
if (isdigit(exp[i])) //데이터가 피연산자라면
{
SetData(newTreeNode, exp[i] - '0'); //새로운 노드에 피연산자 저장
}
else //데이터가 연산자라면
{
SetData(newTreeNode, exp[i]); //새로운 노드에 연산자 저장
MakeRightSubTree(newTreeNode, SPop(&stack)); //스택에서 꺼낸 노드를 새로운 노드의 오른쪽에 연결
MakeLeftSubTree(newTreeNode, SPop(&stack)); //스택에서 꺼낸 노드를 새로운 노드의 왼쪽에 연결
}
SPush(&stack, newTreeNode); //새로운 노드 주소를 스택에 저장
}
return SPop(&stack); //완성된 수식 트리의 루트 노드의 주소 반환
}따로 자세한 설명은 하지 않고, 위 코드의 주석만 보아도 이해가 될 것으로 생각됩니다.
다음은 수식 트리를 계산하는 함수인
int EvaluateExpTree(BTreeNode* bt); //수식 트리 계산위 함수를 정의할 차례지만 책에서는 이 함수의 정의를 미루고 아직 알려주지 않고 있습니다. 그래서 제가 직접 구현해 본 함수를 보이겠습니다.
int EvaluateExpTree(BTreeNode* bt) //수식 트리 계산
{
int leftData, rightData;
//왼쪽 혹은 오른쪽 자식 노드의 데이터가 피연산자라면 피연산자 저장
//연산자라면 해당 서브 트리를 계산
leftData = (bt->left->data >= 0 && bt->left->data <= 9) ? bt->left->data : EvaluateExpTree(bt->left);
rightData = (bt->right->data >= 0 && bt->right->data <= 9) ? bt->right->data : EvaluateExpTree(bt->right);
switch (bt->data)
{
case '+':
return leftData + rightData;
case '-':
return leftData - rightData;
case '*':
return leftData * rightData;
case '/':
return leftData / rightData;
default:
printf("정의되지 않은 연산자가 포함되어 있습니다.\n");
exit(1);
}
}위 함수도 비교적 간단한 함수입니다. 다만 재귀 함수라는 점에서 조금 주의해야 합니다.
다음은 세 가지 표기법으로 수식을 출력하는 세 함수입니다.
void ShowPrefixTypeExp(BTreeNode* bt) //전위 표기법 기반 출력
{
PreorderTraverse(bt, ShowNodeData);
}
void ShowInfixTypeExp(BTreeNode* bt) //중위 표기법 기반 출력
{
InorderTraverse(bt, ShowNodeData);
}
void ShowPostfixTypeExp(BTreeNode* bt) //후위 표기법 기반 출력
{
PostorderTraverse(bt, ShowNodeData);
}위 코드에서 ShowNodeData는 함수입니다. 각 세 함수 내에서 ShowNodeData 함수를 매개변수로 받는 또 다른 세 함수를 호출하고 있습니다. 먼저 ShowNodeData함수는 다음과 같이 정의되었습니다.
void ShowNodeData(BTreeNode* bt)
{
if (bt->data >= 0 && bt->data <= 9)
{
printf("%d", bt->data);
}
else
{
printf("%c", bt->data);
}
}해당 노드의 데이터가 숫자냐 연산자냐에 따라서 출력 방식을 달리 하고 있습니다.
void PreorderTraverse(BTreeNode* bt, Action act); //전위 순회
void InorderTraverse(BTreeNode* bt, Action act); //중위 순회
void PostorderTraverse(BTreeNode* bt, Action act); //후위 순회그리고 위 함수들은 트리를 순회하는 방식에 따라 세 가지로 나뉘는 함수입니다. 각자의 순회 방식을 따라서 Action act로 전달받은 함수를 호출합니다. 정의는 다음과 같이 되어 있습니다.
void PreorderTraverse(BTreeNode* bt, Action act) //전위 순회
{
if (bt == NULL) return;
act(bt);
PreorderTraverse(bt->left, act);
PreorderTraverse(bt->right, act);
}
void InorderTraverse(BTreeNode* bt, Action act) //중위 순회
{
if (bt == NULL) return;
InorderTraverse(bt->left, act);
act(bt);
InorderTraverse(bt->right, act);
}
void PostorderTraverse(BTreeNode* bt, Action act) //후위 순회
{
if (bt == NULL) return;
PostorderTraverse(bt->left, act);
PostorderTraverse(bt->right, act);
act(bt);
}Action은 함수 포인터입니다. Action은 typedef을 이용해서 다음과 같이 재정의되었습니다.
typedef void(*Action)(BTreeNode*);솔직히 이번 시간에는 설명이 너무 부족한 것 같습니다. 제게 언제든지 물어봐주시면 그때 제가 성심성의껏 추가 설명을 해드리겠습니다;
수식 트리의 구현이 모두 끝났으므로 이를 main 함수를 통해 확인할 차례입니다. 사용된 모든 파일을 보이고, 다음의 main 함수를 정의하여 그 실행결과를 확인하겠습니다.
//LBStack.h 헤더 파일로 저장
#ifndef LBSTACK_H
#define LBSTACK_H
#include "BinaryTree.h"
#define TRUE 1
#define FALSE 0
typedef BTreeNode* Data;
typedef struct Node
{
Data data;
struct Node* next;
} Node;
typedef struct LBStack
{
Node* head;
} LBStack;
typedef LBStack Stack;
void StackInit(Stack* pstack);
int SIsEmpty(Stack* pstack);
void SPush(Stack* pstack, Data data);
Data SPop(Stack* pstack);
Data SPeek(Stack* pstack);
#endif//LBStack.c 소스 파일로 저장
#include "LBStack.h"
#include <stdio.h>
#include <stdlib.h>
void StackInit(Stack* pstack)
{
pstack->head = NULL;
}
int SIsEmpty(Stack* pstack)
{
return (pstack->head == NULL) ? TRUE : FALSE;
}
void SPush(Stack* pstack, Data data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
newNode->data = data;
if (pstack->head == NULL)
{
newNode->next = NULL;
}
else
{
newNode->next = pstack->head;
}
pstack->head = newNode;
}
Data SPop(Stack* pstack)
{
Node* delNode = pstack->head;
Data delData = delNode->data;
pstack->head = delNode->next;
free(delNode);
return delData;
}
Data SPeek(Stack* pstack)
{
return pstack->head->data;
}//BinaryTree.h 헤더 파일로 저장
#ifndef BINARYTREE_H
#define BINARYTREE_H
typedef int BTData;
typedef struct BTreeNode
{
BTData data;
struct BTreeNode* left;
struct BTreeNode* right;
} BTreeNode;
typedef void(*Action)(BTreeNode*);
BTreeNode* MakeBTreeNode(void);
BTData GetData(BTreeNode* bt);
void SetData(BTreeNode* bt, BTData data);
BTreeNode* GetLeftSubTree(BTreeNode* bt);
BTreeNode* GetRightSubTree(BTreeNode* bt);
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub);
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub);
void PreorderTraverse(BTreeNode* bt, Action act); //전위 순회
void InorderTraverse(BTreeNode* bt, Action act); //중위 순회
void PostorderTraverse(BTreeNode* bt, Action act); //후위 순회
void DeleteSubTree(BTreeNode* bt); //ADT에는 정의되지 않은 함수, 직접 구현
#endif//BinaryTree.c 소스 파일로 저장
#include "BinaryTree.h"
#include <stdlib.h>
#include <stdio.h>
BTreeNode* MakeBTreeNode(void)
{
BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
BTData GetData(BTreeNode* bt)
{
return bt->data;
}
void SetData(BTreeNode* bt, BTData data)
{
bt->data = data;
}
BTreeNode* GetLeftSubTree(BTreeNode* bt)
{
return bt->left;
}
BTreeNode* GetRightSubTree(BTreeNode* bt)
{
return bt->right;
}
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub)
{
if (main->left != NULL)
{
DeleteSubTree(main->left);
}
main->left = sub;
}
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
if (main->right != NULL)
{
DeleteSubTree(main->right);
}
main->right = sub;
}
void PreorderTraverse(BTreeNode* bt, Action act) //전위 순회
{
if (bt == NULL) return;
act(bt);
PreorderTraverse(bt->left, act);
PreorderTraverse(bt->right, act);
}
void InorderTraverse(BTreeNode* bt, Action act) //중위 순회
{
if (bt == NULL) return;
InorderTraverse(bt->left, act);
act(bt);
InorderTraverse(bt->right, act);
}
void PostorderTraverse(BTreeNode* bt, Action act) //후위 순회
{
if (bt == NULL) return;
PostorderTraverse(bt->left, act);
PostorderTraverse(bt->right, act);
act(bt);
}
//입력받은 노드와 그 후손 노드들을 모두 삭제하는 함수, 직접 구현
void DeleteSubTree(BTreeNode* bt)
{
if (bt->right != NULL)
{
DeleteSubTree(bt->right);
}
if (bt->left != NULL)
{
DeleteSubTree(bt->left);
}
if (bt->data >= 0 && bt->data <= 9)
{
printf("%d를 삭제합니다.\n", bt->data);
}
else
{
printf("%c를 삭제합니다. \n", bt->data);
}
free(bt);
}//ExpressionTree.h 헤더 파일로 저장
#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H
#include "BinaryTree.h"
BTreeNode* MakeExpTree(char exp[]); //수식 트리 구성
int EvaluateExpTree(BTreeNode* bt); //수식 트리 계산
void ShowPrefixTypeExp(BTreeNode* bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode* bt); //중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode* bt); //후위 표기법 기반 출력
#endif//ExpressionTree.c 소스 파일로 저장
#include "ExpressionTree.h"
#include "LBStack.h"
#include <string.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
BTreeNode* MakeExpTree(char exp[]) //수식 트리 구성
{
Stack stack; //스택 생성
int expLen = strlen(exp); //수식의 길이 저장
int i;
for (i = 0; i < expLen; i++)
{
BTreeNode* newTreeNode = (BTreeNode*)malloc(sizeof(BTreeNode)); //새로운 노드 생성
if (newTreeNode == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
newTreeNode->left = NULL;
newTreeNode->right = NULL;
if (isdigit(exp[i])) //데이터가 피연산자라면
{
SetData(newTreeNode, exp[i] - '0'); //새로운 노드에 피연산자 저장
}
else //데이터가 연산자라면
{
SetData(newTreeNode, exp[i]); //새로운 노드에 연산자 저장
MakeRightSubTree(newTreeNode, SPop(&stack)); //스택에서 꺼낸 노드를 새로운 노드의 오른쪽에 연결
MakeLeftSubTree(newTreeNode, SPop(&stack)); //스택에서 꺼낸 노드를 새로운 노드의 왼쪽에 연결
}
SPush(&stack, newTreeNode); //새로운 노드 주소를 스택에 저장
}
return SPop(&stack); //완성된 수식 트리의 루트 노드의 주소 반환
}
int EvaluateExpTree(BTreeNode* bt) //수식 트리 계산
{
int leftData, rightData;
//왼쪽 혹은 오른쪽 자식 노드의 데이터가 피연산자라면 피연산자 저장
//연산자라면 해당 서브 트리를 계산
leftData = (bt->left->data >= 0 && bt->left->data <= 9) ? bt->left->data : EvaluateExpTree(bt->left);
rightData = (bt->right->data >= 0 && bt->right->data <= 9) ? bt->right->data : EvaluateExpTree(bt->right);
switch (bt->data)
{
case '+':
return leftData + rightData;
case '-':
return leftData - rightData;
case '*':
return leftData * rightData;
case '/':
return leftData / rightData;
default:
printf("정의되지 않은 연산자가 포함되어 있습니다.\n");
exit(1);
}
}
void ShowNodeData(BTreeNode* bt)
{
if (bt->data >= 0 && bt->data <= 9)
{
printf("%d", bt->data);
}
else
{
printf("%c", bt->data);
}
}
void ShowPrefixTypeExp(BTreeNode* bt) //전위 표기법 기반 출력
{
PreorderTraverse(bt, ShowNodeData);
}
void ShowInfixTypeExp(BTreeNode* bt) //중위 표기법 기반 출력
{
InorderTraverse(bt, ShowNodeData);
}
void ShowPostfixTypeExp(BTreeNode* bt) //후위 표기법 기반 출력
{
PostorderTraverse(bt, ShowNodeData);
}//main.c 소스 파일로 저장
#include "ExpressionTree.h"
#include <stdio.h>
int main(void)
{
char exp[] = "412+7*+5/";
BTreeNode* eTree = MakeExpTree(exp);
printf("전위 표기법의 수식 : ");
ShowPrefixTypeExp(eTree);
printf("\n");
printf("중위 표기법의 수식 : ");
ShowInfixTypeExp(eTree);
printf("\n");
printf("후위 표기법의 수식 : ");
ShowPostfixTypeExp(eTree);
printf("\n");
printf("연산의 결과 : %d\n", EvaluateExpTree(eTree));
DeleteSubTree(eTree);
return 0;
}
/*
실행결과
전위 표기법의 수식 : /+4*+1275
중위 표기법의 수식 : 4+1+2*7/5
후위 표기법의 수식 : 412+7*+5/
연산의 결과 : 5
5를 삭제합니다.
7를 삭제합니다.
2를 삭제합니다.
1를 삭제합니다.
+를 삭제합니다.
*를 삭제합니다.
4를 삭제합니다.
+를 삭제합니다.
/를 삭제합니다.
*/'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 09. 우선순위 큐의 이해 (0) | 2021.03.18 |
|---|---|
| Chapter 08. 수식 트리(Expression Tree)의 구현 (2) (0) | 2021.03.18 |
| Chapter 08. 이진 트리의 순회 (0) | 2021.03.16 |
| Chapter 08. 이진 트리의 구현 (0) | 2021.03.16 |
| Chapter 08. 트리의 개요 (0) | 2021.03.16 |