[SWEA] 1232 사칙연산(c++)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD

SW Expert Academy

풀이 과정

• 예시에서 나온 트리가 (9/(6-4))*3를 나타내는 것을 보고 post-order 방식으로 구현되어 있는 트리임을 알았습니다.
• 루트에서 부터 left, right 순서대로 계속 탐색을 해서 가장 아래에 있는 노드에 도달하고, 노드가 그냥 상수라면 다시 부모노드로가서 해당하는 연산자에 맞게 계산하는 방식으로 재귀적으로 구현해야 겠다고 생각했습니다.

풀이 코드

#include<iostream>
#include<string>

#define MAX 1001
using namespace std;

struct Node{
    int number;
    string value;
    Node* left;
    Node* right;
};

float result;
Node tree[MAX];

bool isOper(string c){
    if(c == "+" || c == "-" || c == "*" || c == "/")
        return true;
    return false;
}

Node* makeNode(int num, string data){
    tree[num].number = num;
    tree[num].value = data;
    tree[num].left = NULL;
    tree[num].right = NULL;

    return &tree[num];
}

void cal(Node* cur){
    if (cur != 0){
        cal(cur->left);
        cal(cur->right);

        if(cur->value == "+"){
            result = stof(cur->left->value) + stof(cur->right->value);
            cur->value = to_string(result);
        }else if(cur->value == "*"){
            result = stof(cur->left->value) * stof(cur->right->value);
            cur->value = to_string(result);
        }else if(cur->value == "/"){
            result = stof(cur->left->value) / stof(cur->right->value);
            cur->value = to_string(result);
        }else if(cur->value == "-"){
            result = stof(cur->left->value) - stof(cur->right->value);
            cur->value = to_string(result);
        }
    }
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	int test_case;
	int T = 10;
	int num_of_node;
    int num;
    int left;
    int right;
    string data;

	for(test_case = 1; test_case <= T; ++test_case)
	{
        cin >> num_of_node;

        for(int i = 0; i < num_of_node; i++){
            cin >> num >> data;

            Node* new_node = makeNode(num, data);
            
            if(isOper(data)){
                cin >> left >> right;
                tree[num].left = &tree[left];
                tree[num].right = &tree[right];
            }
        }

        cal(&tree[1]);
        cout << '#' << test_case << ' ' << static_cast<int>(stof(tree[1].value)) << '\n';

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

개선 사항

• cal 함수에서 계산을 하고 난 뒤의 결과값을 다시 string으로 변환해 저장하므로써 stof 부분에서 에러가 나지 않도록 하였습니다. 처음에 입력을 할 때부터 float으로 입력받으면 이 과정을 줄일 수 있을 것입니다.
• Node struct에서 operator를 나타내는 char 값과 상수를 나타내는 float값을 따로 저장하도록 하여 개선시킬 수 있을 것입니다.

개선 코드

#include<iostream>
#include<string>

#define MAX 1001
using namespace std;

struct Node{
    int number;
    float value; // 숫자를 저장
    char op; // 연산자를 저장
    Node* left;
    Node* right;
};

float result;
Node tree[MAX];

bool isOper(string c){
    if(c == "+" || c == "-" || c == "*" || c == "/")
        return true;
    return false;
}

Node* makeNode(int num, string data){
    tree[num].number = num;
    if(isOper(data)) {
        tree[num].op = data[0]; // 연산자 저장
        tree[num].value = 0; // 연산자인 경우, value는 사용하지 않음
    } else {
        tree[num].value = stof(data); // 숫자 저장
        tree[num].op = 'N'; // 'N'은 숫자를 나타냄
    }
    tree[num].left = NULL;
    tree[num].right = NULL;

    return &tree[num];
}

void cal(Node* cur){
    if (cur != NULL){
        cal(cur->left);
        cal(cur->right);

        if(cur->op != 'N'){ // 연산자인 경우
            switch(cur->op) {
                case '+':
                    result = cur->left->value + cur->right->value;
                    break;
                case '-':
                    result = cur->left->value - cur->right->value;
                    break;
                case '*':
                    result = cur->left->value * cur->right->value;
                    break;
                case '/':
                    result = cur->left->value / cur->right->value;
                    break;
            }
            cur->value = result;
        }
    }
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int test_case;
    int T = 10;
    int num_of_node;
    int num;
    int left, right;
    string data;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        cin >> num_of_node;

        for(int i = 0; i < num_of_node; i++){
            cin >> num >> data;

            Node* new_node = makeNode(num, data);
            
            if(isOper(data)){
                cin >> left >> right;
                tree[num].left = &tree[left];
                tree[num].right = &tree[right];
            }
        }

        cal(&tree[1]);
        cout << '#' << test_case << ' ' << static_cast<int>(tree[1].value) << '\n';
    }
    return 0;
}