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

SW Expert Academy

문제

사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(9/(6-4))*3”을 이진 트리로 표현한 것이다.
임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과에 해당 연산자를 적용한다.

사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이를 계산한 결과를 출력하는 프로그램을 작성하라.
계산 중간 과정에서의 연산은 모두 실수 연산으로 한다.

입력

총 10개의 테스트 케이스가 주어진다. (총 테스트 케이스의 개수는 입력으로 주어지지 않는다)
각 테스트 케이스의 첫 줄에는 정점의 개수 N(1≤N≤1000)이 주어진다. 그다음 N 줄에 걸쳐 각 정점의 정보가 주어진다.
정점이 정수면 정점 번호와 양의 정수가 주어지고, 정점이 연산자이면 정점 번호, 연산자, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점 번호가 차례대로 주어진다.
정점 번호는 1부터 N까지의 정수로 구분된고 루트 정점의 번호는 항상 1이다.
위의 예시에서, 숫자 4가 7번 정점에 해당하면 “7 4”으로 주어지고, 연산자 ‘/’가 2번 정점에 해당하면 두 자식이 각각 숫자 9인 4번 정점과 연산자 ‘-’인 5번 정점이므로 “2 / 4 5”로 주어진다.

풀이

#include <iostream>
#include <cstring>
#include <cstdlib>
 
using namespace std;
 
int N;
int Number[1001], Firstchild[1001], Secondchild[1001];
char Operator[1001];
int Answer;
void postorder(int root)
{
    if (Operator[root] )
    {
        postorder(Firstchild[root]);
        postorder(Secondchild[root]);
        if (Operator[root] == '+')
        {
            Number[root] = Number[Firstchild[root]] + Number[Secondchild[root]];
        }
        else if (Operator[root] == '-')
        {
            Number[root] = Number[Firstchild[root]] - Number[Secondchild[root]];
        }
        else if (Operator[root] == '*')
        {
            Number[root] = Number[Firstchild[root]] * Number[Secondchild[root]];
        }
        else if (Operator[root] == '/')
        {
            Number[root] = Number[Firstchild[root]] / Number[Secondchild[root]];
        }
    }
}
int main(int argc, char** argv)
{
    int test_case;
    //freopen("system_input.txt", "r", stdin);
    for (test_case = 1; test_case <= 10; ++test_case)
    {
        int i;
        memset(Firstchild, 0, sizeof(int) * 1001);
        memset(Secondchild, 0, sizeof(int) * 1001);
        memset(Number, 0, sizeof(int) * 1001);
        memset(Operator, 0, sizeof(char) * 1001);
 
        cin >> N;
        for (i = 0; i < N; i++)
        {
            int addr;
            char buf[100];
 
            cin >> addr;
            cin >> buf;
            if ((buf[0] == '+') || (buf[0] == '-') || (buf[0] == '*') || (buf[0] == '/'))
            {
                Operator[addr] = buf[0];
                cin >> Firstchild[addr] >> Secondchild[addr];
            }
            else Number[addr] = atoi(buf);
        }
        postorder(1);
        // 표준출력(화면)으로 답안을 출력합니다.
        cout << "#" << test_case;
        cout << " " << Number[1] << endl;;
    }
 
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

해결방법

문제의 설명을 보면 알 수 있듯이 후위순회를 진행하면 되는 문제입니다.
다만, 제출하기 페이지에 들어가면 후위순회가 구현되어 있어서 일부 코드만 작성해주면 문제 해결이 쉽게 가능한 문제입니다.