(5)[Chapter4]수식트리 조립, 출력, 연산(코드구현)

#수식 트리[한자리 수만 가능한 수식 트리입니다.]

1_ 문자열 후위 수식으로 입력시, 중위 수식 트리로 이진트리 조립

Chapter4_3_수식트리_후위수식문자열_중위트리생성메소드_직접해보기.pdf

2.36MB

• 후위 수식으로 입력된 문자열을 역순으로 스캔
• 재귀호출 한다.
• 매개변수  : 입력된 문자열의 주소, 트리의 Root의 이중포인터
• 문자 1개가 연산자 =>  노드할당과 문자1개 노드에 대입  => 오른쪽, 왼쪽 순으로 재귀 호출
• 문자 1개가 피연산자 => 노드 할당, 문자1개 노드에 대입 => x(★즉, 연산자 재귀함수반환 == 노드 포인터 부모로 다시 올라가기)

<중위 트리 조립 메소드>

2_ 중위 수식 트리를 중위 순회로 출력 

• Left를 재귀 호출 시(NULL이 아니라면,) => '(' 출력
• Right를 재귀 호출 시 (NULL이 아니라면) => ')' 출력

<중위순회를 이용한 중위식 출력 메소드>

 

3_ 중위 수식 트리를 후위 순회를 통해 연산 결과값 계산, 출력하기

 

• 매개변수 : 트리의 Root 포인터 (재귀)
• 반환형 : double
• ▲트리의 data는 "문자형"이기에 => 임시 문자열 Tmp가 필요 => atof()메소드를 이용하여, 값을 저장 변환 합니다.
• ★꼭 예시트리로 호출과 반환되는 순서를 직접 해봐야 합니다.

※코드 순서

3_1) 임시 double형 left, right, result 변수를 0으로 초기화 , 임시 문자열 Tmp[2] ={0} 초기화

3_2) 노드의 data 추출 , 검사

• data가 연산자일 경우

=> left , right 순으로, 재귀 호출과 double형 left , right에 반환하여, 저장(★순서 중요)

=> data가 + , - , * , / 에 따라 연산 결과를 result에 저장

• data가 피연산자일 경우

=> Temp 문자열에 노드의 data를 저장 (이유 : atof()메소드 사용을 위해 자료형 맞추기)

=> atof()메소드로 result에 data값 저장

3_3)마지막 result를 반환

 

<중위트리의 모든 노드를 연산 결과값 계산 메소드>

 

#전체 코

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define SIZE 100
#pragma warning (disable : 4996)
 
 
//트리 노드 구조체
typedef char element;
 
typedef struct _BTNode {
    struct _BTNode* left;
    struct _BTNode* right;
    element data;
}BTNode;
 
//노드 생성 메소드
BTNode* CreateNode(element data) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
 
    return newNode;
}
 
void InOrder(BTNode* root) {
    // 예외 조건
    if (root == NULL) return;
 
    // 왼쪽 서브트리 순회
    if (root->left != NULL) {
        // 왼쪽 서브트리가 있는 경우 연산자 노드 앞에 괄호 출력
        printf("( ");
        InOrder(root->left);
    }
 
    // 현재 노드 데이터 출력 (연산자)
    printf("%c ", root->data);
 
    // 오른쪽 서브트리 순회
    if (root->right != NULL) {
        InOrder(root->right);
        // 오른쪽 서브트리가 있는 경우 연산자 노드 뒤에 괄호 출력
        printf(") ");
    }
}
 
 
//노드 1개 메모리 해제 메소드
void FreeNode(BTNode* node) {
    free(node);
}
 
//트리 메모리 해제 메소드 (재귀, ★후위순회)
void FreeTree(BTNode* root) {
    if (root == NULL) return;
 
    //LR 재귀
    if (root->left != NULL) FreeTree(root->left);
    if (root->right != NULL) FreeTree(root->right);
 
    //D 구현부
    FreeNode(root);
 
}
 
//★후위수식으로 입력된 문자열의 1개씩 역순으로 scan에서, 트리 완성 메소드
//재귀, 역순 스캔, 트리의 root 이중 포인터
void ETree(char* input, BTNode** root) {
    int len = strlen(input);
    //예외 조건
    if (len == 0) return;
    //역순으로 1개 문자를 검사용 문자변수c 에 저장
    char c = input[len - 1];
    //마지막을 NULL 처리
    input[len - 1] = '\0';
 
    if (c == '+' || c == '-' || c == '*' || c == '/') {
        //연산자 일 경우
 
        //(1)_ 노드 할당 , c를 노드에 대입
        (*root) = CreateNode(c);
        //(2)_ 오른쪽 자손 순으로 포인터 이동 (재귀 호출)
        ETree(input, &((*root)->right));
        //(3)_ 왼쪽 재귀 호출 (포인터 이동)
        ETree(input, &((*root)->left));
        //(4)_ 오른쪽 왼쪽 모두 배치됐다면, 반환 (포인터 부모노드로 이동)
 
    }
    else {
        //피연산자 일 경우 
        (*root) = CreateNode(c);
    }
}
 
double ETreeCal(BTNode* root) {
    char tmp[2] = { 0 };
 
    double left = 0;
    double right = 0;
    double result = 0;
 
 
    //예외조건
    if (root == NULL) return;
 
    char c = root->data;
 
    if (c == '+' || c == '-' || c == '*' || c == '/') {
        //연산자일 경우
        left = ETreeCal(root->left);
        right = ETreeCal(root->right);
 
        if (c == '+') {
            result = left + right;
        }
        else if (c=='-') {
            result = left - right;
        }
        else if (c == '*') {
            result = left * right;
        }
        else if (c == '/') {
            result = left / right;
        }
 
        
    }
    else {
        //피연산자일 경우
        //문자열에 피연산자 문자형으로 임시저장
        tmp[0] = root->data;
 
        //atof메소드를 이용해, 문자열 값을 double 형으로 변환
        result = atof(tmp);
 
        //값 반환
 
    }
    
    return result;
}
 
int main() {
 
    char input[SIZE] = { 0 };
    double result = 0;
 
    scanf("%s", input);
 
    BTNode* tree = NULL;
 
    ETree(input, &tree);//★트리의 포인터 매개변수 대입시, 노드의 주소로 대입해야함(자료형이 이중포인터시)
 
    InOrder(tree);
    printf("\n");
 
    result = ETreeCal(tree);
 
    printf("%.2lf\n", result);
 
    FreeTree(tree);
 
    return 0;
}