수식 이진 트리 (Expression Binary Tree)

수식 트리 

 

수식을 표현하는 이진트리 입니다. 

 

수식트리는 아래의 두 가지 규칙을 따릅니다.

 

피연산자는 잎노드 이다. 

연산자는 루트노드 또는 가지노드이다.  

 

 

수식 트리 만들기 - Build() 함수 

 

연산자의 경우, 토큰으로 새 노드를 생성하여 연결합니다.

그리고 Build() 함수를 재귀호출 하여 다음에 오는 노드 두개를 새 노드의 자식으로 연결합니다. 

 

피연산자의 경우, 토큰으로 새 노드를 생성합니다. 

 

// 수식 트리 구축하기 
void BuildTree(char* postfixExp, Node** node) {

	// 맨 뒤 부터 하나씩 토큰을 읽는다. 
	int len = strlen(postfixExp);
	char token = postfixExp[len - 1];
	postfixExp[len-1] = '\0';

	switch (token) {
		//연산자라면, 2번 BuildTree 재귀호출.
	case '+': case '-': case '*': case '/':
		(*node) = CreateNode(token); //노드에 연결 
		BuildTree(postfixExp, &(*node)->right); // 식을 '뒤부터'읽으니까 오른쪽부터.
		BuildTree(postfixExp, &(*node)->left);
		break;
		
	default: //피연산자라면 노드 생성 
		(*node) = CreateNode(token);
		break;
	}
}

 

 

수식 트리 계산하기 - Calculate() 함수

 

연산자인 경우, 두 자식의 아래 노드들의 연산 결과가 먼저 필요하므로,

두 자식을 파라미터로 넘겨서 Calculate() 함수를 재귀 호출합니다.

  

피연산자인 경우, 토큰에 담겨있던 수를 double형으로 변환하여 반환합니다. 

 

double Calculate(Node* tree) {
	
	double left, right, result = 0;
	char tempChar[2];

	if (tree == NULL) {
		return 0;
	}

	switch (tree->data) {
		case '+': case '-': case '*': case '/':
			left = Calculate(tree->left);
			right = Calculate(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(tempChar, 0, sizeof(tempChar));
			tempChar[0] = tree->data;
			result = atof(tempChar);
			break;
	}

	return result;
}