[Data Structure] Tree를 이용한 수식 계산

 우리는 예전에 스택을 이용해서 중위(infix), 후위(postfix) 방식의 수식 계산을 다뤘었다. 이것을 트리를 이용해서 할 수도 있다. 트리를 preorder, inorder, postorder 방식으로 traversal 하는 것과 같다.

 여기서는 트리를 이용해 후위 방식으로 수식을 처리해 볼 것이다. 여기서 트리는 피연산자는 항상 단말노드에 존재하며 연산자는 비단말노드로 구성된다.

 이러한 수식 계산을 위해 트리를 구성한 후에 재귀를 이용해 탐색을 한다. 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하고 그 값을 가지고 계산을 해주는 식이다. 여기서 리턴값들이 0 인 것은 수식이기 때문이다.

 코드를 보도록 하자. 금방 이해가 갈 것이다.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int evaluate(TreeNode *root){
    // 재귀 호출 방식을 사용한다
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
    int op1 = evaluate((TreeNode*)root->left);
    int op2 = evaluate((TreeNode*)root->right);
    switch (root->data) {
        case '+':
            return op1+op2;
        case '-':
            return op1-op2;
        case '*':
            return op1*op2;
        case '/':
            return op1/op2;
    }
    return 0;
}

int main(){
    TreeNode n1 = {1,NULL,NULL};
    TreeNode n2 = {4,NULL,NULL};
    TreeNode n3 = {'*',&n1,&n2};
    TreeNode n4 = {16,NULL,NULL};
    TreeNode n5 = {25,NULL,NULL};
    TreeNode n6 = {'+',&n4,&n5};
    TreeNode n7 = {'+',&n3,&n6};
    TreeNode *exp = &n7;
    
    printf("%d\n",evaluate(exp));
    return 0;
}