SW Expert 1232. [S/W 문제해결 기본] 9일차 - 사칙연산(D4)

문제 출처 : SW Expert

SW Expert Academy

Q. 사칙 연산을 이진 트리로 표현할 때, 연산의 결과를 계산하는 프로그램을 작성하시오. 

단, 정점에 대한 정보는 입력으로 주어진다.

 

문제에서 이진 트리로 표현한다고 했지만 배열을 이용하면 간단하게 풀 수 있는 문제입니다.

이 문제는 방법은 중위순회를 이용해 해결하면 되죠. 저는 입력을 처리하는 데에서 약간 애를 먹었네요.

아예 하나의 스트링으로 받아서 케이스를 구분하는 방향으로 입력을 처리했습니다.

정점의 값이 연산일 때, 자식 정점 번호도 주어지는 데, 저는 자식 번호는 무조건 *2, *2 + 1 이라고 생각해서 풀었는데, 아니더라구요. 

자식 번호 또한 따로 처리해줘야했습니다.

#include<iostream>
#include<cstring>
#include<string>
 
using namespace std;
 
string s[1001];
 
long long inorder(int num) {
    if (s[num][1] > '9' || s[num][1] < '0') { // 연산일 때,
        int num1 = 0; //자식노드 1
        int num2 = 0; //자식노드 2
        int i = 3; //자식노드가 주어지는 시작 인덱스
 
        while (1) {
            if (s[num][i] == ' ') {
                break;
            }
            num1 *= 10;
            num1 += s[num][i] - '0';
            i++;
        }
        i++;
        while (s[num].size() > i ) {
            if (s[num][i] == ' ') {
                break;
            }
            num2 *= 10;
            num2 += s[num][i] - '0';
            i++;
        }
        if (s[num][1] == '+') {
            return inorder(num1) + inorder(num2); // + 중위순회
        }
        else if (s[num][1] == '-') {
            return inorder(num1) - inorder(num2); // - 중위순회
 
        }
        else if (s[num][1] == '*') {
            return inorder(num1) * inorder(num2); // * 중위순회
 
        }
        else if (s[num][1] == '/') {
            return inorder(num1) / inorder(num2); /// 중위순회
 
        }
    }
    else {
        int size = s[num].size();
        long long sum = 0;
 
        for (int i = 1; i < size; i++) {
            sum *= 10;
            sum += s[num][i] - '0';
        }
        return sum;
    }
    
}
int main() {
    int T = 10;
    int idx = 0;
 
    while (idx++ < T) {
        int n;
 
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            int num;
            string c;
 
            cin >> num;
            getline(cin, c);
 
            s[num] = c;
        }
        /*for (int i = 1; i <= n; i++) {
            cout << s[i][1] << endl;
        }*/
        long long result = inorder(1);
 
        cout << "#" << idx << " " << result << endl;
 
    }
}

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!