[C++] SWEA 1232 - 사칙연산

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD&categoryId=AV141J8KAIcCFAYD&categoryType=CODE&problemTitle=1232&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 트리를 입력받는다

2. 트리를 연산한 결과를 출력한다.

 

<해법>

1. 트리를 구현하는 방법

=> 저는 노드 구조체를 만들어서 구현하였습니다. 구조체에는 data와 왼쪽 자식, 오른쪽자식의 index가 있습니다.

 

2. 트리를 연산하는 방법

=> 저는 트리를 후위순회 하였습니다. 또한, 숫자는 leaf노드에만 존재하므로 노드의 데이터가 연산자면 자식노드들을 탐색하고, 숫자노드면 바로 숫자 데이터를 return하는 것으로 구현하였습니다.

 

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
struct node {
    string data;
    int leftNode, rightNode;
};
 
int N;
node arr[1001];
int answer;
 
bool isOper(string s) {
    if (s == "+" || s == "-" || s == "*" || s == "/") return true;
    return false;
}
 
double calculate(double a, string oper, double b) {
    double output = 0;
    if (oper == "+") output = a + b;
    else if (oper == "-") output = a - b;
    else if (oper == "*") output = a * b;
    else output = a / b;
    return output;
}
 
double postOrder(int idx) {
    if (!isOper(arr[idx].data)) return stoi(arr[idx].data);
 
    double ret = 0;
    ret = calculate(postOrder(arr[idx].leftNode), arr[idx].data, postOrder(arr[idx].rightNode));
    return ret;
}
 
void solution() {
    answer = postOrder(1);
}
 
int main() {
    int test_case;
    int T;
    T = 10;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        N = 0;
        for (int i = 0; i < 1001; i++) arr[i] = { "",0,0 };
        answer = 0;
 
        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            int idx;
            string data;
            cin >> idx >> data;
            arr[idx].data = data;
            if (isOper(data)) {
                int leftNode, rightNode;
                cin >> leftNode >> rightNode;
                arr[idx].leftNode = leftNode, arr[idx].rightNode = rightNode;
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

자료구조 트리와 재귀함수에 대해 알아볼 수 있는 문제였습니다.