수식 트리 (Expression Tree)

수식을 표현하는데 사용되는 이진 트리

수식 트리는 하나의 연산자가 두 개의 피연산자를 가진다고 가정한다.

수식 트리는 다음의 조건을 가진다.

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

3 * 4 + (8 - 6) 수식을 이진 트리로 표현하게 되면 다음 아래의 그림과 같이 된다.

피연산자(3, 4, 6, 8)는 모두 잎 노드이고, 연산자(+, *, -)는 루트 노드이거나 가지 노드 이다.

수식 트리에서는 왼쪽 하위 트리, 오른쪽 하위 트리를 거쳐 루트 노드 순으로 순회하는 하위 순회를 사용한다.

수식 트리의 구축

일반적으로 사용하는 수식을 표기하는 중위 표기식은 컴퓨터가 처리하기에 적합하지 않으므로 먼저 수식을 후위 표기식으로 변환한다.

(중위 표기식을 후위 표기식으로 변환하는 방법 - http://kbms.tistory.com/10)

'3 * 4 + (8 - 6)' 수식을 후위 표기식으로 바꾸면 '3 4 * 8 6 - +' 이다

수식 트리 구축 알고리즘

1. 수식의 뒤에서부터 앞으로 읽는다.
2. 수식의 제일 마지막이 루트 노드이다. (후위 표기식의 마지막은 언제나 연산자)
3. 수식에서 읽은 토큰이 연산자인 경우 가지 노드가 되고 이 다음 2개의 토큰은 오른쪽 자식과 왼쪽 자식 노드가 된다. (하지만 다음 토큰에서 연산자인 경우에는 이 토큰으로 부터 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰이 왼쪽 자식 노드이다.)
4. 수식에서 읽은 토큰이 숫자이면 잎 노드이다.

'3 4 * 8 6 - +' 수식을 트리로 구축하는 과정

3 4 * 8 6 - +

가장 마지막인 '+'연산자가 루트 노드가 된다.

3 4 * 8 6 - +

다음 토큰으로 '-'연산자를 읽어 루트노드의 왼쪽 자식 노드가 된다.

3 4 * 8 6 - +

다음 토큰 두 개는 숫자(피연산자)이므로 각각 '-'노드의 양쪽 자식이 된다.

3 4 * 8 6 - +

다음 토큰으로 '*'(연산자)로 루트 노드인 '+'노드의 왼쪽 자식 노드가 된다.

3 4 * 8 6 - +

나머지 토큰인 숫자(피연산자)는 '*'노드의 양쪽 자식 노드가 된다.

완성된 수식 트리를 확인 할 수 있다.

수식 트리 구현 소스코드

#ifndef EXPRESSION_TREE_H

#define EXPRESSION_TREE_H

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef char ElementType;

typedef struct tagETNode 

{

    struct tagETNode* Left;

    struct tagETNode* Right;

    ElementType Data;

} ETNode;

ETNode*   ET_CreateNode( ElementType NewData );

void      ET_DestroyNode( ETNode* Node );

void      ET_DestroyTree( ETNode* Root );

void      ET_PreorderPrintTree( ETNode* Node );

void      ET_InorderPrintTree( ETNode* Node );

void      ET_PostorderPrintTree( ETNode* Node );

void      ET_BuildExpressionTree( char* PostfixExpression, ETNode** Node );

double    ET_Evaluate( ETNode* Tree );

#endif EXPRESSION_TREE_H

#include "ExpressionTree.h"

ETNode* ET_CreateNode( ElementType NewData )

{

    ETNode* NewNode = (ETNode*)malloc( sizeof(ETNode) );

    NewNode->Left    = NULL;

    NewNode->Right   = NULL;

    NewNode->Data    = NewData;

    return NewNode;

}

void ET_DestroyNode( ETNode* Node )

{

    free(Node);

}

void ET_DestroyTree( ETNode* Root )

{

    if ( Root == NULL )

        return;

    ET_DestroyTree( Root->Left );

    ET_DestroyTree( Root->Right );

    ET_DestroyNode( Root );

}

void ET_PreorderPrintTree( ETNode* Node )

{

    if ( Node == NULL )

        return;

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

    ET_PreorderPrintTree( Node->Left );

    ET_PreorderPrintTree( Node->Right );

}

void ET_InorderPrintTree( ETNode* Node )

{

    if ( Node == NULL )

        return;

    

    printf( "(" );

    ET_InorderPrintTree( Node->Left );

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

    ET_InorderPrintTree( Node->Right );

    printf( ")" );

}

void ET_PostorderPrintTree( ETNode* Node )

{

    if ( Node == NULL )

        return;

    

    ET_PostorderPrintTree( Node->Left );

    ET_PostorderPrintTree( Node->Right );

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

}

void ET_BuildExpressionTree( char* PostfixExpression, ETNode** Node )

{

    ETNode* NewNode = NULL;

    int  len        = 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;

}