Chap08. 수식 트리

https://www.geeksforgeeks.org/expression-tree/

 

- 위와 같은 트리를 수식트리라고 한다.

 

- 수식 트리는 이진 트리를 이용해 수식을 표현해 놓은 것이며, 이진 트리와 구분되는 별개의 것이 아니다.

 

- 수식 트리는 중위 표기법을 사용하지도 후위 표기법을 사용하지도 않는다. 수식 트리는 그냥 수식 트리일 뿐이며 수식을 표현하는 또 다른 방법일 뿐이다. 

 

- 수식 트리의 연산은 루트 노드에 저장된 연산자의 연산을 하되, 두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 한다.

 

- 우리가 중위 표기법으로 다음과 같은 수식을 작성하면 7 + 4 * 3, 컴파일러는 이를 수식 트리로 표현해서 계산한다. 

 

 

---

수식 트리의 구현 방식  

- 중위 표기법을 수식 트리로 표현하는것은 복잡하므로, 중위 표기법을 후위 표기법으로 바꾼 후 수식 트리로 표현한다.

 

- 수식 트리에서는 트리의 아래쪽에 위치한 연산자들의 연산이 먼저 진행되므로, 후위 표기법의 수식에서 먼저 등장하는 피연산자와 연산자를 이용해 트리의 하단을 만들고, 점진적으로 트리의 윗부분을 구성해 나간다.

 

후위 표기법의 수식을 수식 트리로 

후위 표기법의 수식을 수식 트리로 표현하는데는 스택 자료구조가 필요하다.

 

• 피연산자(숫자 or 트리) 를 만나면 무조건 스택으로 옮긴다
• 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내 자식 노드로 연결한다. 먼저 꺼낸 피연산자가 오른쪽, 두번째가 왼쪽 자식 노드가 된다. 
• 자식 노드를 연결해서 만들어진 트리를 다시 스택으로 옮긴다. 이때 자식 노드들은 모두 연결되어 있는 상태이기 때문에 트리의 루트 노드의 주소값만 스택으로 옮기면 된다.

 

후위 표기법 수식을 받아 수식 트리를 생성해 루트 노드의 주소값 반환 하는 함수: 

BTreeNode  *MakeExpTree(char *exp)
{
    Stack stack;
    StackInit(&stack);
    BTreeNode *pnode;

    int expLen = strlen(exp);
    int i;

    for(i = 0; i < expLen; i++)
    {
        pnode = MakeBTreeNode();

        // 피연산자라면
        if(isdigit(exp[i]))
        {
            SetData(pnode, exp[i]-'0');
        }
        else // 연산자라면
        {
            // stack에서 pop하 노드를 서브트리로 만듦
            MakeRightSubTree(pnode, SPop(&stack));
            MakeLeftSubTree(pnode, SPop(&stack));
            SetData(pnode, exp[i]);
        }
        SPush(&stack, pnode);
    }
    return SPop(&stack);
}

 

---

수식 트리의 순회 

수식 트리의 장점은 수식 트리의 순회 결과를 통해 나타난다.

 

전위 순회하여 데이터를 출력하면 전위 표기법의 수식

중위 순회하여 데이터를 출력하면 중위 표기법의 수식

후위 순회하여 데이터를 출력하면 후위 표기법의 수식 으로 표현된다.

 

 

---

수식 트리 구현 

 

ExpressionTree.h

/*
 * 수식 트리 구현
 */
#ifndef CHAP08_EXPTREE_EXPRESSIONTREE_H
#define CHAP08_EXPTREE_EXPRESSIONTREE_H

#include "BinaryTreeTraversal.h"

// 후위 표기법 수식을 받아 expression tree 생성해 루트의 주소값 반환
BTreeNode *MakeExpTree(char *exp);
// 수식 트리 계산
int EvaluateExpTree(BTreeNode *bt);

// pre, in, post fix 기반 표비법 출력
void ShowPrefixTypeExp(BTreeNode *bt);
void ShowInfixTypeExp(BTreeNode *bt);
void ShowPostfixTypeExp(BTreeNode *bt);


#endif //CHAP08_EXPTREE_EXPRESSIONTREE_H

ExpressionTree.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
#include "ExpressionTree.h"

BTreeNode  *MakeExpTree(char *exp)
{
    Stack stack;
    StackInit(&stack);
    BTreeNode *pnode;

    int expLen = strlen(exp);
    int i;

    for(i = 0; i < expLen; i++)
    {
        pnode = MakeBTreeNode();

        // 피연산자라
        if(isdigit(exp[i]))
        {
            SetData(pnode, exp[i]-'0');
        }
        else // 연산자라면
        {
            // stack에서 pop하 노드를 서브트리로 만듦
            MakeRightSubTree(pnode, SPop(&stack));
            MakeLeftSubTree(pnode, SPop(&stack));
            SetData(pnode, exp[i]);
        }
        SPush(&stack, pnode);
    }
    return SPop(&stack);
}

int EvaluateExpTree(BTreeNode *bt)
{
    //
    return 0;
}

// 함수 포인터로 전달됨
void ShowNodeData(int data)
{
    if(0 <= data && data <= 9) // 피연산자
        printf("%d ", data);
    else // 연산자
        printf("%c ", data);
}

void ShowPrefixTypeExp(BTreeNode *bt)
{
    PreorderTraverse(bt, ShowNodeData);
}

void ShowInfixTypeExp(BTreeNode *bt)
{
    if(bt == NULL) return;

    if(bt->left != NULL || bt->right != NULL) printf(" ( ");

    ShowInfixTypeExp(bt->left);
    ShowNodeData(bt->data);
    ShowInfixTypeExp(bt->right);

    if(bt->left != NULL || bt->right != NULL) printf(" ) ");
}

void ShowPostfixTypeExp(BTreeNode *bt)
{
    PostorderTraverse(bt, ShowNodeData);
}

ExpressionTreeMain.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
#include "ExpressionTree.h"

BTreeNode  *MakeExpTree(char *exp)
{
    Stack stack;
    StackInit(&stack);
    BTreeNode *pnode;

    int expLen = strlen(exp);
    int i;

    for(i = 0; i < expLen; i++)
    {
        pnode = MakeBTreeNode();

        // 피연산자라
        if(isdigit(exp[i]))
        {
            SetData(pnode, exp[i]-'0');
        }
        else // 연산자라면
        {
            // stack에서 pop하 노드를 서브트리로 만듦
            MakeRightSubTree(pnode, SPop(&stack));
            MakeLeftSubTree(pnode, SPop(&stack));
            SetData(pnode, exp[i]);
        }
        SPush(&stack, pnode);
    }
    return SPop(&stack);
}

int EvaluateExpTree(BTreeNode *bt)
{
    int op1, op2;

    // 단말노드라면 피연산자(숫자)를 리턴함
    if(GetLeftSubTree(bt) == NULL && GetRightSubTree(bt) == NULL)
        return GetData(bt);

    op1 = EvaluateExpTree(GetLeftSubTree(bt));
    op2 = EvaluateExpTree(GetRightSubTree(bt));

    switch(GetData(bt))
    {
        case '+':
            return op1 + op2;
        case '-':
            return op1 - op2;
        case '*':
            return op1 * op2;
        case '/':
            return op1 / op2;
    }
    return 0;
}

// 함수 포인터로 전달됨
void ShowNodeData(int data)
{
    if(0 <= data && data <= 9) // 피연산자
        printf("%d ", data);
    else // 연산자
        printf("%c ", data);
}

void ShowPrefixTypeExp(BTreeNode *bt)
{
    PreorderTraverse(bt, ShowNodeData);
}

void ShowInfixTypeExp(BTreeNode *bt)
{
    if(bt == NULL) return;

    if(bt->left != NULL || bt->right != NULL) printf(" ( ");

    ShowInfixTypeExp(bt->left);
    ShowNodeData(bt->data);
    ShowInfixTypeExp(bt->right);

    if(bt->left != NULL || bt->right != NULL) printf(" ) ");
}

void ShowPostfixTypeExp(BTreeNode *bt)
{
    PostorderTraverse(bt, ShowNodeData);
}

 

수식 트리의 결과를 반환하는 EvaluateExpTree() 함수도 마찬가지로 재귀적으로 호출된다.

---

문제 08-2 [중위 표기법의 소괄호]

다음과 같이 연산자가 저장된 노드를 만났을때 여는 소괄호 '(' 를 출력하고, 두 번째 피연산자까지 출력 한후에 닫는 소괄호를 출력해 주면 된다.

void ShowInfixTypeExp(BTreeNode *bt)
{
    if(bt == NULL) return;

    if(bt->left != NULL || bt->right != NULL) printf(" ( ");

    ShowInfixTypeExp(bt->left);
    ShowNodeData(bt->data);
    ShowInfixTypeExp(bt->right);

    if(bt->left != NULL || bt->right != NULL) printf(" ) ");
}