[SWEA] 1232 사칙연산

출처: SWEA

Approach

이진트리를 구성한 다음 후위순회를 하는 문제이다.

아래 Input Case를 분석해보자.

 Input 

1 - 2 3

2 - 4 5

3 10

4 88

5 65

 

 Output 

13

- 1번 노드에 (-) 연산과 자식노드로 2, 3번 노드

- 2번 노드에 (-) 연산과 자식노드로 4, 5번 노드

- 3번 노드에 10, 4번 노드에 88, 5번 노드에 65

트리 형태는 아래와 같다.

▶ (88 - 65) - 10 = 23 - 10 = 13

 

트리 형태 구현은 구조체를 이용한다.

 

후위 순회는 아래처럼 구현한다.

부모 노드에서 연산자(+ - * /)에 해당하는 경우

왼쪽 자식 노드 & 오른쪽 자식 노드로 재귀 탐색해서 연산 결과를 return 받는 방식이다.

후위 순회말고도 전위 / 중위 순회는 트리 자료구조에서 대표적으로 공부해야하는 탐색 방식이다.

---

#include <stdio.h>

const int MAX_N = 1000 + 2;
struct Node {
    char opr;
    int value, left, right;
}tree[MAX_N];
int N, idx, L, R;
char str[100];

int postorder(int idx) {
    switch (tree[idx].opr)
    {
    case '+':
        return postorder(tree[idx].left) + postorder(tree[idx].right);
        break;
    case '-':
        return postorder(tree[idx].left) - postorder(tree[idx].right);
        break;
    case '*':
        return postorder(tree[idx].left) * postorder(tree[idx].right);
        break;
    case '/':
        return postorder(tree[idx].left) / postorder(tree[idx].right);
        break;
    default:
        return tree[idx].value;
        break;
    }
}

int main(void)
{
    for (int tc = 1; tc <= 10; ++tc)
    {
        scanf("%d", &N); // 정점 개수
        for (int i = 0; i < N; i++)
        {
            scanf("%d %s", &idx, str);
            if (str[0] == '+' || str[0] == '-' ||
                str[0] == '*' || str[0] == '/')
            {
                scanf("%d %d", &L, &R);
                // 연산자와 왼쪽, 오른쪽 자식 노드
                tree[idx] = { str[0], 0, L, R };
                continue;
            }
            // 일반 정수인 경우
            int temp = str[0] - '0';
            for (int j = 1; str[j] != NULL; j++) {
                temp = (temp * 10) + (str[j] - '0');
            }
            // 자식노드가 없으면 해당 번호에 입력
            tree[idx] = { 0, temp, 0, 0 };
        }
        printf("#%d %d\n", tc, postorder(1));
    }
    return 0;
}