수식 트리
수식을 표현하는 이진트리 입니다.
수식트리는 아래의 두 가지 규칙을 따릅니다.
피연산자는 잎노드 이다.
연산자는 루트노드 또는 가지노드이다.
수식 트리 만들기 - 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;
}
728x90
