[C언어]49일차 - 수식트리 (이것이 c 자료구조와 알고리즘이다)

 

수식 트리는 이름 처럼 수식을 표현하는 이진 트리이다.

 

두가지 규칙이 있다.

 

1.피연산자는 잎 노드이다.

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

 

 

피연산자 1, 2, 7, 8은 모두 잎 노드.

 

연산자들은 모두 뿌리 노드이거나 가지 노드이다.

 

 

뿌리 노드와 가지 노드 모두 피연산자를 양쪽 자식으로 가진다.

 

여기에서 피연산자는 수 일 수도 있고, 다른 식일 수도 있다.

 

 

 

이처럼 수식 트리는 가장 아래에 있는 하위 수식 트리(잎 노드)로 부터 수 또는 계산 결괏값을 병합해 올라가는 과정을 반복하며 계산을 수행한다. 

 

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

 

후위 순회는 왼쪽 하위트리 -> 오른쪽 하위트리 -> 뿌리 노드 순으로 순회하기 때문이다.

 

 

수식 트리 구축 방법

 

1.수식을 뒤에서 부터 앞쪽으로 읽어 나가며 토큰을 취한다.

 

2.수식에서 제일 마지막에 있는 토큰으로 뿌리 노드를 생성한다.

 

후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.

 

3.읽어낸 토큰이 연산자인 경우, 가지 노드를 생성하며 이 토큰 다음에 따라오는 2개의 토큰으로 각각 오른쪽 자식 노드와 왼쪽 자식 노드를 생성한다.

 

단, 다음 토큰도 연산자인 경우 이 토큰에서 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰으로 왼쪽 자식 노드를 생성한다.

 

4.읽어낸 토큰이 숫자인 경우 잎 노드를 생성한다.

 

 

중위 표현식

 

 

후위 표현식

 

 

뒤쪽에서 토큰을 읽으면서 수식 트리 만들기 시작.

 

제일 마지막 노드가 + 연산자이기 때문에 + 연산자로 뿌리를 만든다.

 

하나의 연산자가 2개의 피연산자를 취한다는 규칙에 따르면 + 연산자를 담고 있는 뿌리 노드는 연산에 필요한 피연산자 2개를 요구한다.

 

그래서 다음 토큰 2개를 읽어 들여 자식 노드로 만들어 붙여야 한다.

 

하지만 그렇게 안된다.

 

읽어 들인 2개의 토큰 모두 숫자라면 문제가 없지만, 2개 중 첫번째 토큰이 연산자라면 두번째 토큰을 첫 번째 토큰의 피연산자로 사용해야 하기 때문이다.

 

그래서 토큰을 하나씩만 읽어 들여서 먼저 그 토큰이 연산자인지 숫자인지 확인해야 한다. 

 

 

- (마이너스) 노드는 연산자 노드라서 양쪽으로 피연산자 자식이 필요하다.

 

다음 토큰이 8과 7이니 각각 자식으로 만들어 넣는다.

 

이 과정을 반복한다.

 

 

 

수식트리 구축

1.매개 변수로 입력된 후위 표기식을 뒤 부터 읽어 토큰 하나를 분리한다.

 

2.읽어낸 토큰이 연산자라면 이는 2개의 피연산자가 뒤에따라온다.

 

3.이 경우 방금 읽어낸 연산자 토큰을 노드에 연결하고, 바로 이어서 buildExpressionTree() 를 두 번 호출하여 뒤따라오는 피연산자 둘을 연산자 노드의 양쪽 자식으로 연결 한다.

 

4.처음 읽은 토큰이 피연산자인 경우, 해당 토큰을 노드에 입력하고 함수를 반환한다.

 

 

 

수식트리 계산

 

1.노드에 담긴 토큰을 연산자인 경우와 피연산자인 경우로 나눠서 처리한다.

 

2.토큰이 연산자일 때는 트리의 바닥(잎)부터 계산 결과를 병합하여 올라가도록 노드의 양쪽 자식에 대하여 ET_Evaluate() 를 재귀 호출 한다.

 

3.재귀 호출한 ET_Evaluate() 가 값을 반환하면 왼쪽 수식 트리의 계산 결과는 Left 변수에, 오른쪽 수식 트리의 계산 결과는 Right 변수에 저장된다.

 

4.그 다음에는 연산자의 종류에 따라 덧셈, 뺄셈, 곱셈, 나눗셈을 수행한다.

 

 

 

 

 

 

전체 코드

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

#define ElementType char


//MARK: 노드 구조체
typedef struct tagSBTNode
{
    struct tagSBTNode* Left;
    struct tagSBTNode* Right;
    ElementType Data;
} SBTNode;


//MARK: 노드 생성
SBTNode* createNode(ElementType NewData){
        
    //malloc 함수를 이용해서 SBTNode 구조체 크기 만큼 자유 저장소에 메모리를 할당한다.
    SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));
    NewNode->Left = NULL;
    NewNode->Right = NULL;
    NewNode->Data = NewData;
    
    return NewNode;
};

//MARK: 노드 소멸
void destroyNode(SBTNode* Node){
    free(Node);
}

//MARK: 전위순회
void preOrderPrint(SBTNode* Node){
    if (Node == NULL) {
        return;
    }
    
    printf("%c " ,Node->Data);
    
    preOrderPrint(Node->Left);
    preOrderPrint(Node->Right);
    
    
}

//MARK: 중위순회
void inOrderPrint(SBTNode* Node){
    if (Node == NULL) {
        return;
    }
    
    inOrderPrint(Node->Left);

    printf("%c " ,Node->Data);
    
    inOrderPrint(Node->Right);
    
    
}

//MARK: 후위순회
void postOrderPrint(SBTNode* Node){
    if (Node == NULL) {
        return;
    }
    
    postOrderPrint(Node->Left);
    postOrderPrint(Node->Right);
    printf("%c " ,Node->Data);
}

//MARK: 트리 소멸
// 트리를 파괴할 때는 반드시 잎 노드 부터 자유 저장소(힙)에서 제거해야 한다.
// 따라서 잎 노드부터 방문하여 뿌리 노드까지 거슬러 올라가며 방문하는 후위순회를 이용하면
// 이진트리 전체를 문제 없이 소멸 시킬 수 있다.
void destroyTree(SBTNode* Node){
    
    if (Node == NULL) {
        return;
    }
    
    //왼쪽 하위 트리 소멸
    destroyTree(Node->Left);
    
    //오른쪽 하위 트리 소멸
    destroyTree(Node->Right);
    
    //뿌리 노드 소멸
    destroyNode(Node);
    
}


void buildExpressionTree(char* postfixExpression, SBTNode** Node){
    
    //수식의 제일 마지막 Token을 꺼내고, 빈값을 채운다.
    int len = strlen(postfixExpression);
    char Token = postfixExpression[len - 1];
    postfixExpression[len - 1] = '\0';
    
    
    switch (Token) {
        //연산자일 경우
        case '+': case '-': case '*': case '/':
            (*Node) = createNode(Token);
            buildExpressionTree(postfixExpression, &(*Node)->Right);
            buildExpressionTree(postfixExpression, &(*Node)->Left);
            
            break;
        //피연산자인 경우
        default:
            (*Node) = createNode(Token);
            break;
    }
}


double evaluate(SBTNode* 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 = evaluate(Tree->Left);
            Right = 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;
}





//MARK: main
int main(int argc, const char * argv[]) {
       
    
    
    SBTNode* Root = NULL;

    char postFixExpression[20] = "71*52-/";

    buildExpressionTree(postFixExpression, &Root);
    

    printf("1.preOrderPrint ... \n");
    preOrderPrint(Root);
    printf("\n\n");
    
    printf("2.inOrderPrint ... \n");
    inOrderPrint(Root);
    printf("\n\n");
    
    printf("3.postOrderPrint ... \n");
    postOrderPrint(Root);
    printf("\n\n");
    
    
    printf("Evaluation Result : %f \n" , evaluate(Root));
    
    
    destroyTree(Root);
    
    return 0;
}

 

 

출력

1.preOrderPrint ... 
/ * 7 1 - 5 2 

2.inOrderPrint ... 
7 * 1 / 5 - 2 

3.postOrderPrint ... 
7 1 * 5 2 - / 

Evaluation Result : 2.333333 
Program ended with exit code: 0