[ch 08-4] 수식 트리의 구현_2(구현)

[소스 코딩]

※ 이진 트리는 이전에 구현한 'BinaryTree2.h', 'BinaryTree2.c'를 활용

※ 스택은 이전에 구현한 'ListBaseStack.h', 'ListBaseStack.c'를 활용

■ ExpressionTree.h

#ifndef EXPRESSIONTREE_H_
#define EXPRESSIONTREE_H_
 
#include "BinaryTree2.h"
 
BTreeNode * MakeExpTree(char exp[]);        // 입력 받은 후위 표기법 수식을 수식 트리로 변환
int EvaluateExpTree(BTreeNode * bt);        // 수식 트리의 연산
 
void ShowPrefixTypeExp(BTreeNode * bt);     // 변환된 수식 트리를 전위 표기법으로 출력
void ShowInfixTypeExp(BTreeNode * bt);      // 변환된 수식 트리를 중위 표기법으로 출력
void ShowPostfixTypeExp(BTreeNode * bt);    // 변환된 수식 트리를 후위 표기법으로 출력
 
#endif

■ ExpressionTree.c

#include <stdio.h>
#include <string.h>   // 사용 함수: strlen
#include <ctype.h>    // 사용 함수: isdigit
#include "ListBaseStack.h"
#include "BinaryTree2.h"
 
// 입력 받은 후위 표기법 수식을 수식 트리로 변환 //
BTreeNode * MakeExpTree(char exp[])
{
    Stack stack;
    BTreeNode * pnode;
 
    int expLen = strlen(exp);
    int i;
 
    StackInit(&stack);
 
    for(i=0; i<expLen; i++)
    {
        pnode = MakeBTreeNode();
 
        if(isdigit(exp[i]))
        {
            SetData(pnode, exp[i]-'0');
        }
        else
        {
            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)
{
//    InorderTraverse(bt, ShowNodeData);
 
    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);
}

■ 각 함수의 설명

// 입력 받은 후위 표기법 수식을 수식 트리로 변환 //
BTreeNode * MakeExpTree(char exp[])
{
    Stack stack;
    BTreeNode * pnode;
 
    int expLen = strlen(exp);
    int i;
 
    StackInit(&stack);
 
    for(i=0; i<expLen; i++)
    {
        pnode = MakeBTreeNode();
 
        if(isdigit(exp[i]))
        {
            SetData(pnode, exp[i]-'0');
        }
        else
        {
            MakeRightSubTree(pnode, SPop(&stack));
            MakeLeftSubTree(pnode, SPop(&stack));
            SetData(pnode, exp[i]);
        }
 
        SPush(&stack, pnode);
    }
 
    return SPop(&stack);
}

- 스택 구조체 'stack' 선언

- 대상이 되는 노드를 가리킬 포인터 변수 'pnode' 선언

- 수식의 길이를 나타내기 위해 'expLen'을 'strlen' 함수를 사용하여 입력 받은 수식의 길이를 저장

- 'StackInit'함수로 'stack' 초기화

--- 수식 트리로 변환하는 반복문 시작 ---

- 'pnode'에 이진 트리 노드를 생성하여 저장

  ※ 왼쪽, 오른쪽이 'NULL' 값인 노드

// 수식에서 조회한 문자가 '숫자(피연산자)'일 경우

- 숫자(정수)로 변환하여 생성한 노드의 데이터로 저장

// 수식에서 조회한 문자가 '문자(연산자)'일 경우

- 스택에서 피연산자 노드를 꺼내어 노드(pnode)의 오른쪽 서브트리로 연결

- 스택에서 피연산자 노드를 꺼내어 노드(pnode)의 왼쪽 서브트리로 연결

- 노드(pnode)의 데이터에 연산자를 저장

- 완성된 수식 트리(pnode)를 다시 스택에 넣음

--- 수식 트리로 변환하는 반복문 종료 ---

- 수식에서 더 이상 변환할 문자가 없으면 스택에서 완성된 수식 트리를 꺼내어 반환

// 수식 트리의 연산 //
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;
}

- 피연산자를 저장할 'op1', 'op2'를 선언

// 현재 노드의 왼쪽 서브트리의 노드 값이 'NULL'이고 오른쪽 서브트리의 노드 값이 'NULL'일 경우

- 현재 노드를 다시 반환

  ※ 단일 노드 상태를 의미하기에 더 이상 하위 노드를 조회할 필요가 없음

- 'op1'에는 현재 수식 트리의 연산과정을 현재 노드의 '왼쪽 서브트리'를 재귀 반복을 통해 진행하여 최종적으로 연산된

  단일 노드의 값을 저장

- 'op2'에는 현재 수식 트리의 연산과정을 현재 노드의 '오른쪽 서브트리'를 재귀 반복을 통해 진행하여 최종적으로 연산된

  단일 노드의 값을 저장

// 현재 노드의 문자(연산자)의 종류에 따라 다르게 처리

- '+'일 경우 왼쪽 피연산자와 오른쪽 피연산자를 '더한' 결과를 반환

- '-'일 경우 왼쪽 피연산자에서 오른쪽 피연산자를 '뺀' 결과를 반환

- '*'일 경우 왼쪽 피연산자에서 오른쪽 피연산자를 '곱한' 결과를 반환

- '/'일 경우 왼쪽 피연산자에서 오른쪽 피연산자를 '나눈' 결과를 반환

- 최종적으로 '0'을 반환

  ※ 이미 이전 과정에서 정상적인 반환 값들이 존재하기에 해당 함수를 정상적으로 종료한다는 의미로 작성만 함

// 노드의 데이터 출력 //
void ShowNodeData(int data)
{
    if(0<=data && data<=9)
        printf("%d ", data);
 
    else
        printf("%c ", data);
}

// 노드에 저장된 값이 '숫자'일 경우(수식에서 한 자리의 숫자(0~9까지)만 입력 받음)

- 정수형 데이터 출력

// 노드에 저장된 값이 '문자'일 경우

- 문자형 데이터 출력

// 변환된 수식 트리를 전위 표기법으로 출력 //
void ShowPrefixTypeExp(BTreeNode * bt)
{
    PreorderTraverse(bt, ShowNodeData);
}

- 완성된 수식 트리를 전위 순회하여 전위 표기법으로 출력

  ※ 전위 순회 함수 'PreorderTraverse'는 'BinaryTree2.c' 소스에 정의되어 있음

// 변환된 수식 트리를 중위 표기법으로 출력 //
void ShowInfixTypeExp(BTreeNode * bt)
{
//  InorderTraverse(bt, ShowNodeData);
 
    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(") ");
}

※ 소괄호 처리에 대한 부분이 추가되어 다른 표기법과 일부 다름

★ 주석으로 처리된 부분만 처리하고 아래 내용은 삭제할 경우 '소괄호'가 없는 중위 표기법으로 출력됨

// 현재 노드의 왼쪽 또는 오른쪽에 연결된 노드가 있을 경우

- 소괄호 '('를 출력

- 중위 순회 과정을 진행(중위 표기법으로 출력하는 과정)

  ※ 중위 순회 함수 'InorderTraverse'는 'BinaryTree2.c' 소스에 정의되어 있음

// 현재 노드의 왼쪽 또는 오른쪽에 연결된 노드가 있을 경우

- 소괄호 ')'를 출력

// 변환된 수식 트리를 후위 표기법으로 출력 //
void ShowPostfixTypeExp(BTreeNode * bt)
{
    PostorderTraverse(bt, ShowNodeData);
}

 

- 완성된 수식 트리를 후위 순회하여 후위 표기법으로 출력

  ※ 후위 순회 함수 'PostorderTraverse'는 'BinaryTree2.c' 소스에 정의되어 있음

■ ExpressionTreeMain.c

#include <stdio.h>
#include "ExpressionTree.h"
 
int main(void)
{
    char exp[] = "71-2/";                    // 후위 표기법 수식 입력
    BTreeNode * eTree = MakeExpTree(exp);    // 후위 표기법 수식을 수식 트리로 변환
 
    printf("전위 표기법의 수식: ");
    ShowPrefixTypeExp(eTree);                // 완성된 수식 트리를 전위 표기법으로 출력
    printf("\n\n");
 
    printf("중위 표기법의 수식: ");
    ShowInfixTypeExp(eTree);                 // 완성된 수식 트리를 중위 표기법으로 출력
    printf("\n\n");
 
    printf("후위 표기법의 수식: ");
    ShowPostfixTypeExp(eTree);               // 완성된 수식 트리를 후위 표기법으로 출력
    printf("\n\n");
 
    printf("연산의 결과: %d \n", EvaluateExpTree(eTree));    // 수식 트리의 연산 결과를 출력
 
    return 0;
}

■ 실행결과