[BOJ/C언어]1935번_후위 표기식2

https://www.acmicpc.net/problem/1935

#문제 풀기 전 알아야 할 개념

1_ 수식트리 만드는 과정 ( [https://kojammin.tistory.com/22] 을 참고해라)

2_ 입력된 후위수식의 문자열에 중복된 문자로 입력했을 시, 처리하는 아이디어 (※예제 입력2)

 내 풀이 : 알파벳 히스토그램 (★더 좋은 아이디어가 있으시다면, 알려주시면 절밖고 배우겠습니다.)

 

3_ 후위수식 => 중위수식 계산 처리 간략한 순서 :

① : 문자열의 역순으로 Scan하면서, 피연산자 / 연산자 에 따라 노드 할당, 생성 (Etree 메소드) 

↓

② : 중위 순회를 통해 트리를 돌면서, 수식을 계산 (EtreeCal메소드) 

↓

③ : 다시 후위 순회를 통해 트리 전체의 노드들을 메모리 해제 (FreeTree메소드)

 

##코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define SIZE 26
 
int arr_int[SIZE]; // 피연산자 값 배열
 
// 이진트리 구조체
typedef char element;
 
typedef struct _BTNode {
    struct _BTNode* L;
    struct _BTNode* R;
    element data;
} BTNode;
 
// 노드 생성, 할당, 초기화 메소드
BTNode* CreateNode(element data) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    newNode->L = NULL;
    newNode->R = NULL;
    newNode->data = data;
 
    return newNode;
}
 
// 후위 표기식을 역순으로 스캔하여 트리를 생성하는 메소드
void ETree(char* input, BTNode** root) {
    int len = strlen(input);
 
    if (len == 0) return;
 
    char c = input[len - 1];
    input[len - 1] = '\0';
 
    if (c == '+' || c == '-' || c == '*' || c == '/') {
        *root = CreateNode(c);
        ETree(input, &((*root)->R));
        ETree(input, &((*root)->L));
    }
    else if (c >= 'A' && c <= 'Z') {
        *root = CreateNode(c);
    }
}
 
// 수식 트리 중위 순회로 계산하는 메소드
double ETreeCal(BTNode* root) {
    if (root == NULL) return 0;
 
    double left = 0;
    double right = 0;
    double result = 0;
 
    char c = root->data;
 
    if (c == '+' || c == '-' || c == '*' || c == '/') {
        left = ETreeCal(root->L);
        right = ETreeCal(root->R);
 
        if (c == '+') result = left + right;
        else if (c == '-') result = left - right;
        else if (c == '*') result = left * right;
        else if (c == '/') result = left / right;
    }
    else {
        result = arr_int[c - 'A'];
    }
 
    return result;
}
 
// 트리 메모리 해제 메소드 (후위순회)
void FreeTree(BTNode* node) {
    if (node == NULL) return;
 
    FreeTree(node->L);
    FreeTree(node->R);
    free(node);
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    getchar();
 
    char postfix[101];
    scanf("%s", postfix);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr_int[i]);
    }
 
    BTNode* tree = NULL;
    ETree(postfix, &tree);
 
    double result = ETreeCal(tree);
    printf("%.2lf\n", result);
 
    FreeTree(tree);
 
    return 0;
}