Tree - 수식 트리 (Expression Tree)

 

앞 서 만든 이진트리를 만드는 도구를 활용하여 이진트리 구조 중 하나인 수식트리를 만들어보자

 

1. 수식트리란?

출처: 열혈자료구조

중위,후위,전위 표기법과 같은 여러가지 표기법 중 하나로 메모리에 수식을 표기하는 방식이다.

루트 노드에 연산자를, 두 개의 자식노드에 피연산자를 두어 연산이 진행된다. 이를 그림으로 표기하면 위와 같다.

이러한 수식트리의 장점은 한번 트리를 완성해두면, 중위,후위,전위 표기법으로 쉽게 전환할 수 있다.

 

2. 구현

 

중위표기법을 바로 수식트리로 나타내는 것보다 중위표기법을 후위표기법으로 전환한 뒤에 수식트리로 나타내는 것이 간편하므로, 여기서는 후위표기법을 수식트리로 변환하는 과정만 보일 것이다.

 

수식트리를 표현하기 위한 도구 : 1. Stack, 2 BTree 

 

헤더 

#ifndef __EXPRESSTION_H

#define __EXPRESSTION_H

#include "BTree.h"

BTreeNode* MakeExpTree(char exp[]);

int EvaluateExpTree(BTreeNode* btn);

void ShowPrefixType(BTreeNode* btn);

void ShowInfixType(BTreeNode* btn);

void ShowPostfixType(BTreeNode* btn);

#endif

소스

#include "CStack.h"

#include <stdlib.h>

#include <ctype.h>

#include <string.h>

#include"ExpresstionTree.h"

BTreeNode* MakeExpTree(char exp[]){

    Stack st;

    int len = strlen(exp);

    StackInit(&st);

    BTreeNode* node;

    for(int i=0; i<len ;i++){

        node = MakeBTreeNode();

        if(isdigit(exp[i])){

         SetData(node,exp[i]-'0');

        }else{

            MakeRightSubTree(node,pop(&st));

            MakeLeftSubTree(node,pop(&st));

            SetData(node,exp[i]);

        }

        push(&st,node);

    }

   

    return pop(&st);

}

int EvaluateExpTree(BTreeNode* btn){

    int op1,op2;

    if(btn->left == NULL && btn->right == NULL){

        return btn->data;

    }

    op1 = EvaluateExpTree(GetLeftSubTree(btn));

    op2 = EvaluateExpTree(GetRightSubTree(btn));

    switch (btn->data)

    {

        case '+':  return op1+op2;

        case '-':  return op1-op2;

        case '*':  return op1*op2;

        case '/':  return op1/op2;

    }

    return 0;

}

void ShowPrefixType(BTreeNode* btn){

   PreorderTraverse(btn,showdata);

}

void ShowInfixType(BTreeNode* btn){

    InorderTraverse(btn,showdata);

}

void ShowPostfixType(BTreeNode* btn){

    PostorderTraverse(btn,showdata);

}

void showdata(int data){

    if(0<=data && data>=9){

        printf("%d ",data);

    }else {

        printf("%c ",data);

    }

}

void ShowInfix1(BTreeNode* btn){

    if(btn == NULL) return;

    if(btn->left != NULL || btn->right !=NULL)

    printf("( ");

    ShowInfix1(GetLeftSubTree(btn));

    showdata(btn->data);

    ShowInfix1(GetRightSubTree(btn));

   

    if(btn->left != NULL || btn->right !=NULL)

    printf(" )");

}

 

BTreeNode* MakeExpTree(char exp[]) 

수식트리를 구성하기 위한 함수로 후위 표기식을 입력받아 내부적으로 수식트리를 완성해도 return한다.

int EvaluateExpTree(BTreeNode* btn); 수식트리를 계산하는 함수이다.

void ShowPrefixType(BTreeNode* btn); - 수식트리 -> 전위표기

void ShowInfixType(BTreeNode* btn);  - 수식트리 -> 중위표기

void ShowPostfixType(BTreeNode* btn); - 수식트리 -> 후위표기

 

2.1 전개과정

 

 1 2 + 7 * 의 후위표기식이 있다고 가정해보자. 이를 수식트리로 변환하기 위해서

 

-> 연산자 순서대로 왼쪽에서 오른쪽으로 연산자가 나열됨

-> 해당 연산자의 두 피연산자는 연산자 앞에 나열됨

 

트리 아래쪽에 위치한 연산자들 부터 연산이 진행되므로 트리의 구성은 위에서 아래로 구성하는 것이아니라 아래에서 위로 구성하는 형태가 될 것이다. 

*마치 재귀적 함수를 계산하는 듯한 형태로 구성하는 것 처럼 보일 수 있다. 

 

1 2 + 7 * --> 1과 2는 피연산자이므로 각각의 BTreeNode를 구성해 stack에 담는다.

+7* / stack : 1,2  --> 연산자를 만났다 연산자를 루트노드로 왼쪽과 오른쪽에 피연산자 노드를 연결하고, 다시 스택에 담는다

* 이때 연산자 BTreeNode포인터만 스택에 넣어두어도 이미 연결되어 있음으로 괜찮다!

 

--> 위 과정을 계속 반복한 뒤 마지막에 스택에 담긴 포인터를 반환한다.

 

2.2 수식 트리 계산 

 

int EvaluateExpTree(BTreeNode* btn) 이 함수를 통해 수식트리를 계산하고자 한다.

 

모든 노드에 접근하여 계산해야 하므로, 재귀적으로 함수를 구성해야한다. 

 

종료조건 : 

 if(btn->left == NULL && btn->right == NULL) return btn->data;

리프노드부터 시작해서 루트노드의 연산자를 통해 연산해야하므로, 후위 순회의 조건으로 재귀함수를 구성해야한다.

또한 재귀함수의 호출이 리프노드에 도달했을 때 더이상 함수를 호출하지 않고, 리프노드의 값을 리턴해야하므로, 종료조건은 리프노드인지 아닌지를 검사하는 위와 같은 식으로 구성할 수 있을 것이다.  

 

 

출처: 윤성우 - 열혈자료구조