Expression Tree(수식 트리)

1. Expressiont Tree

이진트리로 만들 수 있는 대표적인 것중에 하나가 수식트리입니다. 수식트리는 우리가 앞에서 했던 Stack을 이용해 사칙연산을 계산했던 것과 같이 트리를 이용해 사칙연산을 계산하는 것입니다.

단말노드가 모두 숫자로 이루어져있고, 단말노드를 제외한 노드들은 전부 수식으로 채워져있습니다. 그럼 여기서 궁금한게 수식트리는 중위법 후위법 전위법중 어느 방식을 채용했는지 입니다. 3개 다 아닙니다. 수식트리는 수식트리입니다. 자식노드 2개와 부모노드의 연산자를 통해 계산을 한 것을 연산자의 자리에 대입하면서, 계산하는 식입니다.

따라서 수식트리는 순서가 명확하고, 연산의 과정을 쉽게 파악할 수 있는 이진트리의 일종입니다.

헤더파일

ExpressionTree.h

#ifndef EXPRESSION_TREE_H
#define EXPRESSION_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char ElementType;

typedef struct tagETNode {
	struct tagETNode* Left;
	struct tagETNode* Right;

	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_BuildExpressionTree(char* PostfixExpression, ETNode** Node); -> 수식트리로 만드는 함수
double ET_Evaluate(ETNode* Tree); -> 수식트리를 계산하는 함수

#endif

Binary Tree에서 달라진 것은 ET_BuildExpressionTree ET_Evaluate함수입니다. 나머지는 이진트리에서 봤던 함수들이어서 소스파일에서는 저 두함수만 보고 넘어가겠습니다.

하지만 수식트리인 만큼 전위순회는 전위식, 중위순회는 중위식, 후위순회는 후위식으로 출력됩니다.

소스파일

ExpressionTree.c

#include "ExpressionTree.h"

ETNode* ET_CreateNode(ElementType NewData) {
	ETNode* NewNode = (ETNode*)malloc(sizeof(ETNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

void ET_DestroyNode(ETNode* Node) {
	free(Node);
}

void ET_DestroyTree(ETNode* Root) {
	if (Root == NULL) {
		return;
	}

	ET_DestroyTree(Root->Left);
	ET_DestroyTree(Root->Right);
	ET_DestroyNode(Root);
}

void ET_PreorderPrintTree(ETNode* Node) {
	if (Node == NULL) {
		return;
	}

	printf(" %c", Node->Data);

	ET_PreorderPrintTree(Node->Left);
	ET_PreorderPrintTree(Node->Right);
}

void ET_InorderPrintTree(ETNode* Node) {
	if (Node == NULL) {
		return;
	}

	printf("(");
	ET_InorderPrintTree(Node->Left);

	printf(" %c", Node->Data);

	ET_InorderPrintTree(Node->Right);
	printf(")");
}

void ET_PostorderPrintTree(ETNode* Node) {
	if(Node == NULL) {
		return;
	}

	ET_PostorderPrintTree(Node->Left);
	ET_PostorderPrintTree(Node->Right);
	printf(" %c", Node->Data);
}

void ET_BuildExpressionTree(char* PostfixExpression, ETNode** Node) {
	int len = strlen(PostfixExpression);
	char Token = PostfixExpression[len - 1];
	PostfixExpression[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;
	}
}

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->Left);
		Right = ET_Evaluate(Tree->Right);

		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;
}

이진트리에서 추가된 두 함수만 살펴보면

void ET_BuildExpressionTree(char* PostfixExpression, ETNode** Node) {
	int len = strlen(PostfixExpression); -> 후위식 길이 저장
	char Token = PostfixExpression[len - 1]; -> 배열 맨 끝값 저장
	PostfixExpression[len - 1] = '\0'; -> 배열 맨 끝값 \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;
	}
}

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->Left); -> 왼쪽 자식 호출
		Right = ET_Evaluate(Tree->Right); -> 오른쪽 자식 호출

		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초기화
		Temp[0] = Tree->Data; -> Temp에 데이터 저장
		Result = atof(Temp); -> 문자를 숫자로 바꾸기
		break;
	}

	return Result; -> 결과 반환
}

트리는 말 그대로 재귀적인 성향이 강하기 때문에, 재귀호출이 자주 일어나는 것을 볼 수 있습니다.

실행예시

그럼 바로 컴파일해보겠습니다.
ExpressionTreeMain.c

#include "ExpressionTree.h"

int main() {
	ETNode* Root = NULL;

	char PostfixExpression[20] = "71*52-/";
	ET_BuildExpressionTree(PostfixExpression, &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");

	printf("Evaluation Result : %f\n", ET_Evaluate(Root));

	//트리 소멸
	ET_DestroyTree(Root);

	return 0;
}

결과

Preorder...
 / * 7 1 - 5 2

Inorder...
((( 7) *( 1)) /(( 5) -( 2)))

Postorder...
 7 1 * 5 2 - /
Evaluation Result : 2.333333