[수식트리]
[수식트리]
수식을 표현하는 이진트리 . 수식 이진 트리라고 부르기도 한다 .
일반적으로 수식트리는 하나의 연산자가 두개의 피연산자를 취한다는 가정하에 다음 두가지 규칙을 가진다 .
- 피연산자는 잎 노드이다 .
- 연산자는 루트노드 / 혹은 가지노드이다 .
[예제]
1*2+(7+8)
루트노드/가지노드는 피연산자 (수 / 식)를 양쪽 자식으로 둔다 .
이런 방법으로 수식트리는 가장 아래에 있는 하위 수식 트리로부터 수 또는 계산결과를
병합해 올라가는 과정을 반복하며 계산을 수행한다 .
이러한 수식트리의 성질에는 후위순회(왼쪽 노드- 오른쪽 노드 - 루트 노드)가 알맞다 .
양쪽 하위 트리에서부터 결과값을 병합해 올라와야 하기때문이다 .
[수식트리의 구축]
[수식트리]
컴퓨터가 처리하기 좋은 후위 표기식을 이용해 트리를 구축하는 것이 수월하다 .
후위 표기식에 기반한 수식 트리 구축 알고리즘은 다음과 같다 .
- 수식을 뒤에서 부터 앞으로 읽어 나간다 .
- 수식에서 제일 마지막 토근은 루트 노드가 된다 . 후위 표기식 가장 마지막 토큰은 항상 연산자이다.
- 수식에서 읽어낸 토큰이 연산자라면 가지노드가 , 이 토큰 다음 두개의 토큰은 오른쪽,왼쪽 자식노드가 된다 . (다음 토큰에도 연속해서 연산자인 경우 이 토큰으로 부터 만들어진 하위 트리가 완성된 이후 읽어낸 토큰이 왼쪽 자식 노드가 된다)
- 수식에서 읽어낸 토큰이 숫자면 이 노드는 잎 노드이다 .
[예제]
1 2 * 7 8 - +
1. 마지막 토큰인 + 가 루트 노드가 된다 .
2. 다음 토큰이 연산자 - 이므로 두번째 토큰은 첫번째 토큰의 피 연산자가 된다 .
3. 다음 토큰 - 는 연산자이므로 다음 토큰 7,8 은 오른쪽 왼쪽의 자식이 된다 . 새로운 자식은 연산자이니 자식이 없는 잎 노드이다 . 이렇게 + 노드의 오른쪽 하위 수식 트리가 완성되었으니 왼쪽 자식으로 넘어간다 .
4.* 는 +의 왼쪽 자식이 된다 .
5.1,2는 *의 왼쪽,오른쪽 자식 노드가 되고 수식을 모두 읽었으니 전체 수식트리 완성
[수식트리의 주요연산]
[수식트리 구축하기]
매개변수로 입력된 후위 표기식을 뒤부터 읽어 토큰 하나를 분리한다 .
읽어낸 토큰이 연산자라면 뒤 두개의 피연산자가 뒤 따라온다 .
이 경우 연산자 토큰을 노드에 연결 , ET_BuildExpressionTree()를 두번 호출하여 따라오는 피연산자
둘을 양쪽 자식으로 결합한다 . 처음 읽은 토큰이 피연산자라면 토큰을노드에 입력 함수를 반환한다 .
void ET_BuildExpressionTree(char* PostfixExpression , ETNode** Node)
{
int len=strlen(PostfixExpression);
char Token=PostfixExpression[len-1];
PostficExpression[len-1]='\0';
switch(Token)
{
case '+':case '-': case '/': case '*' :
(*Node) = ET_CreateNode(Token);
ET_BuildExpressionTree(PostfixExpression , &(*Node)->Right);
ET_BuildExpressionTree(PostfixExpression , &(*Node)->Left);
break;
default:
(*Node)=ET_CreateNode(Token);
break;
}
}
[수식트리 계산하기]
앞서 만든 수식트리의 노드에 담긴 토큰을 확인하고 , 연산자 / 피연산자 나누어 처리한다 .
- 노드의 양쪽 자식에 대해 ET_Evaluate()를 재귀호출한다 . 재귀호출하여 반환된 왼쪽트리의 계산결과는 left변수에 오른쪽 수식 트리의 결과는 Right변수에 저장한다 . 이후 연산자의 종류에 따라 계산을 수행한다
- 피연산자라면 토큰에 담겨있던 값을 수로 변환해 반환한다 .
double EV_Evaluate(ETNode* Tree)
{
char Temp[2];
double Left = 0;
double Right = 0;
double Result =0;
if(Tree == NULL)
return 0;
switch(Tree -> Data)
{
case '+':case'-':case '*': case '/':
Left = ET_Evaluate(Tree->Left);
Right = ET_Evaluate(Tree -> Rigjt);
if(Tree->Data =='+' result =Left+Right;
else if(Tree->Data == '-' result = Left - Right;
else if(Tree->Data == '*' result = Left * Right;
else if(Tree->Data == '/' result = Left / Right;
break;
default :
memset(Temp , 0 ,sizeof(Temp));
Temp[0]=tree->Data;
Result = atof(Temp);
break;
}
return Result;
}
[수식트리의 구현]
[ET.h]
#ifndef ET
#define ET
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char ElementType;
typedef struct tagETNode
{
tagETNode* LeftNode;
tagETNode* RightNode;
ElementType Data;
}ETNode;
//노드 생성
ETNode* ET_CreateNode(ElementType NewData);
//노드 삭제
void ET_DestroyNode(ETNode* Node);
//트리 삭제
void ET_DestroyTree(ETNode* Root);
//전위 순회
void ET_PreorderPrintTree(ETNode* Node);
//중위 순회
void ET_InorderPrintTree(ETNode* Node);
//후위 순회
void ET_PostorderPrintTree(ETNode* Node);
//후위표기식을 트리로
void ET_BuildExpressioinTree(char* PostfixExpression, ETNode** Node);
//트리를 계산
double ET_Evaluate(ETNode* Tree);
#endif // !ET
[ET.cpp]
#include"ET.h"
//노드 생성
ETNode* ET_CreateNode(ElementType NewData)
{
ETNode* NewNode = (ETNode*)malloc(sizeof(ETNode));
NewNode->LeftNode = NULL;
NewNode->RightNode = NULL;
NewNode->Data = NewData;
return NewNode;
}
//노드 삭제
void ET_DestroyNode(ETNode* Node)
{
free(Node);
}
//트리 삭제
void ET_DestroyTree(ETNode* Root)
{
if (Root == NULL)
return;
ET_DestroyNode(Root->LeftNode);
ET_DestroyNode(Root->RightNode);
ET_DestroyNode(Root);
}
//전위 순회
void ET_PreorderPrintTree(ETNode* Node)
{
if (Node == NULL)
return;
printf("%c", Node->Data);
ET_PreorderPrintTree(Node->LeftNode);
ET_PreorderPrintTree(Node->RightNode);
}
//중위 순회
void ET_InorderPrintTree(ETNode* Node)
{
if (Node == NULL)
return;
printf("(");
ET_InorderPrintTree(Node->LeftNode);
printf("%c", Node->Data);
ET_InorderPrintTree(Node->RightNode);
printf(")");
}
//후위 순회
void ET_PostorderPrintTree(ETNode* Node)
{
if (Node == NULL)
return;
ET_PostorderPrintTree(Node->LeftNode);
ET_PostorderPrintTree(Node->RightNode);
printf("%c", Node->Data);
}
//후위표기식을 트리로
void ET_BuildExpressioinTree(char* PostfixExpression, ETNode** Node)
{
int length = strlen(PostfixExpression);
//토큰을 받아온다
char Token = PostfixExpression[length - 1];
//받아온 부분은 널문자로 초기화 (strlen은 NULL 전까지의 길이 반환)
PostfixExpression[length - 1]='\0';
//토큰의 유형에 따라
switch (Token)
{
//연산자라면
case '+':case '-':case '*':case '/':
{
//노드에는 나를 넣어주고 (두개) 오른쪽 -> 왼쪽 노드에서 다시 토큰값을 받아 처리를 한다 .
(*Node)= ET_CreateNode(Token);
ET_BuildExpressioinTree(PostfixExpression,&(*Node)->RightNode);
ET_BuildExpressioinTree(PostfixExpression, &(*Node)->LeftNode);
break;
}
default:
//피연산자라면 노드에 나를 넣는다.
(*Node) = ET_CreateNode(Token);
break;
}
}
//트리를 계산
double ET_Evaluate(ETNode* Tree)
{
char Temp[2];
double Left = 0;
double Right = 0;
double Result = 0;
if (Tree == NULL)
return 0;
//트리의 데이터에 따라 분기
switch (Tree->Data)
{
//연산자라면
case '+':case '-':case '*':case '/':
{
//왼쪽 계산
Left=ET_Evaluate(Tree->LeftNode);
//오른쪽 계산
Right= ET_Evaluate(Tree->RightNode);
//나온 데이터를 연산하여 반환
if (Tree->Data == '+')Result = Left + Right;
else if (Tree->Data == '-')Result = Left - Right;
else if (Tree->Data == '/')Result = Left / Right;
else if (Tree->Data == '*')Result = Left * Right;
break;
}
default:
//피연산자라면 나를 반환 .
//쓰레기값 없이 초기화
memset(Temp, 0, sizeof(Temp));
Temp[0] = Tree->Data;
//문자열을 숫자로
Result = atof(Temp);
break;
}
return Result;
}
[Test.cpp]
#include "ET.h"
int main(void)
{
ETNode* Root = NULL;
char PostfixExpressioin[20] = "71*52-/";
ET_BuildExpressioinTree(PostfixExpressioin, &Root);
printf("Preorder ... \n");
ET_PreorderPrintTree(Root);
printf("\n\n");
printf("Inorder ... \n");
ET_InorderPrintTree(Root);
printf("\n\n");
printf("Postorder ... \n");
ET_PostorderPrintTree(Root);
printf("\n\n");
printf("Evaluate Result : %f\n", ET_Evaluate(Root));
ET_DestroyNode(Root);
printf("종료");
return 0;
}
'자료구조' 카테고리의 다른 글
[ 자료구조 ] 정렬 - 01 . 정렬 알고리즘 (0) | 2023.02.13 |
---|---|
[ 자료구조 ] 트리 - 04 . 분리 집합 (0) | 2023.02.11 |
[ 자료구조 ] 트리 - 02 . 이진트리 (0) | 2023.02.07 |
[자료구조] 트리 - 01 . 트리 기초 다지기 (0) | 2023.02.06 |
[자료구조] 큐 - 03 . 링크드 큐 (0) | 2023.02.02 |