[자료구조] 수식 트리(Expression Tree) - 코딩밥

수식 트리란?

그 이름 그대로 수식을 표현하는 이진 트리이므로 수식 이진 트리라고 부르기도 합니다.

하나의 연산자당 2개의 피연산자가 필요하기 때문에 수식 트리는 다음 두 가지 규칙을 가집니다.

1. 피연산자는 잎 노드이다.
2. 연산자는 뿌리 노드 또는 가지 노드이다.

또한 이러한 방식으로 뿌리 노드를 연산자로, 왼쪽 서브 트리의 결과값과 오른쪽 서브 트리의 결과값을 파연산자로 하여 마지막 연산을 해주면 답이 됩니다. 즉 수식 트리는 하위 수식 트리의 계산 결과값을 피연산자로 삼아 계산하여 결과를 얻습니다.

이러한 수식 트리의 성질에 적합한 노드 순회 방법은 후위 순회입니다.

---

수식 트리 구현하기

-알고리즘

1. 수식을 뒤에서부터 앞쪽으로 읽어나가며 토큰을 취한다.
2. 수식에서 제일 마지막에 있는 토큰으로 뿌리 노드를 생성한다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.
3. 읽어낸 토큰이 연산자인 경우 가지 노드를 생성하며 이 토큰 다음에 따라오는 2개의 토큰으로 각각 오른쪽 자식 노드와 왼쪽 자식 노드를 생성한다. 단, 다음 토큰도 연산자인 경우 이 토큰에서 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰으로 왼쪽 자식 노드를 생성한다.
4. 읽어낸 토큰이 숫자인 경우 잎 노드를 생성한다.

-코드

void ET_BuildExpressionTree(char* PostfixExpression, ETNode** Node){	//수식 트리 구축
    int len = (int)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;
}