뇌를 자극하는 알고리즘 - 4. 트리 : Expression Tree

구현소스

ExpressionTree.h

#ifndef EXPRESSION_TREE_H
#define EXPRESSION_TREE_H

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

typedef double Element;

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

	Element Data;

} ETNode;

// 노드생성
ETNode* ET_CreateNode(Element 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

--------------------------------------

ExpressionTree.cpp

#include "ExpressionTree.h"

ETNode* ET_CreateNode(Element 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 ;

	if(Node->Data == '+' || Node->Data == '-' || Node->Data == '*' || Node->Data == '/')
		printf("%c ", (char) Node->Data);
	else
		printf("%.2lf ", Node->Data);

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


}

// 중위 순회
void ET_InorderPrintTree(ETNode* Node){
	if(Node==NULL)
		return ;

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

	if(Node->Data == '+' || Node->Data == '-' || Node->Data == '*' || Node->Data == '/')
		printf("%c", (char) Node->Data);
	else
		printf("%.2lf", Node->Data);

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


}

// 후위 순회
void ET_PostorderPrintTree(ETNode* Node){
	if(Node==NULL)
		return ;
	ET_PostorderPrintTree(Node->Left);
	ET_PostorderPrintTree(Node->Right);

	if(Node->Data == '+' || Node->Data == '-' || Node->Data == '*' || Node->Data == '/')
		printf("%c ", (char) Node->Data);
	else
		printf("%.2lf ", Node->Data);

}

void ET_BuildExpressionTree(char* PostfixExpression, ETNode** Node){
	

	int len = strlen(PostfixExpression);
	int temp= len-1;
	int i;
	double Token = 0;
	
	for(i=len-1; i>=0 ; i--)
	{	if(PostfixExpression[i]==' ')
			break;
	}// 입력 단위 구분을 공백으로 했기때문에 i는 공백인 인덱스를 가리키게 되고
	
	if( temp - i == 1) // 공백과 temp의 차가 1이라면 한자리 숫자이거나 연산자가 된다.
	{
		// 연산자일 경우
		if(PostfixExpression[temp] == '+' || PostfixExpression[temp] == '-' || 
			PostfixExpression[temp] == '*' || PostfixExpression[temp] == '/')
			Token = PostfixExpression[temp];
		// 한자리 숫자일 경우
		else
		{
			char str[2] = {0};

			str[0] = PostfixExpression[temp];

			Token = atof(str);
		}
	}
	else // 공백과 temp의 차가 1외의 숫자라면 두자리 이상의 숫자이거나 소수점이 들어간 수가 된다.
	{
		int j;
		int str_count=0;
		char str[10] = {0};

		// 공백 앞에서부터 그 수를 읽어 들임
		for(j=i+1; j < len ; j++)
		{
			str[str_count++] = PostfixExpression[j];
		}

		Token = atof(str);
	}
	if(i>=0)
		PostfixExpression[i] = '\0';
	

	// 토큰이 연산자인 경우
	if(Token == '+' || Token == '-' || Token == '*' || Token == '/')
	{
		*Node = ET_CreateNode(Token);
		ET_BuildExpressionTree(PostfixExpression, &(*Node)->Right );
		ET_BuildExpressionTree(PostfixExpression, &(*Node)->Left );
	}
	// 토큰이 숫자인 경우
	else
	{
		*Node = ET_CreateNode(Token);
	}
}

double ET_Evaluate(ETNode* Tree){
	double Result=0;
	double Left=0, Right = 0;
	

	//어차피 단말노드들은 피연산자들일테니 굳이 안써도 될듯..
	//if(Tree==NULL)
	//	return 0;

	// 트리의 데이터가 연산자인 경우
	if(Tree->Data == '+' || Tree->Data == '-' || Tree->Data == '*' || Tree->Data == '-')
	{
		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;
	}
	// 트리의 데이터가 피연산자의 경우 데이터를 리턴한다.
	else{
		return Tree->Data;
	}

	return Result;

}

---------------------------------------

main.cpp

#include "ExpressionTree.h"

int main()
{
	ETNode* Root = NULL;
	
	
	// ** 수식 트리 문제점
	// '+' == 43
	// '-' == 45
	// '*' == 42
	// '/' == 47
	// ' ' == 32
	// 에 해당하는 숫자가 들어가면 이상하게 되거나 아에 안될수있음 ㅠㅠ....

	// 그냥 double 형 이랑 char형 노드를 두개 선언해서 이걸 해결할걸 그랬나...
	// - 그래도 내가 만든 방법으론 해결이 안될거 같기도 하고 흠..일단 넘어가자. Pass Pass
	
	char PostFix[40] = "100 90.5 - 1 2 * +";

	ET_BuildExpressionTree(PostFix,&Root);

	printf("Preorder : ");
	ET_PreorderPrintTree(Root);
	printf("\n");

	printf("Inorder : ");
	ET_InorderPrintTree(Root);
	printf("\n");

	printf("Inorder : ");
	ET_PostorderPrintTree(Root);
	printf("\n");

	printf("Result : ");
	printf("%.2lf\n",ET_Evaluate(Root));
	

	return 0;
}

---------------------------------------

실행결과