BOJ 1918 후위 표기식 [C++]

고생 많이 한 문제였다. 먼저 처음 접하는 내용이라 문제 자체가 직관적으로 와닿지가 않았다.

그래서 작게 분해해서 풀기로 했다. 알고리즘 분류는 스택이라 되어있는데 재귀함수를 사용했다.

뭐 재귀함수도 결국 스택이니까.

수학에서 연산자 우선순위는 ()  >  */  > +-순서이다.

proc 함수 내부에서 이 세 연산자를 순서대로 처리하도록 하고

괄호의 경우 괄호 내부의 식을 다시 proc 함수의 파라미터로 전달해 재귀호출하였다.

 

괄호 안에 괄호가 또 있고 짝이 맞지 않는 닫힘괄호에 의해 잘못된 ss값을 구하는 것을 방지하기 위해 스택과 비슷한 원리로 열림 괄호는 n++, 닫힘괄호는 n--를 해주었다.

 

그리고 괄호를 처리하여 각각의 문자열을 문자열 벡터 vec에 넣어주었다. vec의 각 값은 문자 하나가 될 수도 있지만 char가 아닌 string으로 처리한다.

예를 들어 s = A*(B+C)라면

vec = {A, proc(B+C)} = {A, BC+}가 된다.

 

 

2번째 반복문에서는 단위별로 *, /를 처리해준다. vec을 순회하다 *또는 /를 만나면 변수 cond의 값을 변화시키고 vec의 다음 인덱스를 앞 인덱스에 붙이고 그 뒤에 연산자를 붙여준다.

 

3번째 반복문에서도 앞과 같은 원리로 +-를 처리한다.

 

proc함수의 마지막 반복문은 잘게 쪼개진 vec3 벡터의 각 문자열을 하나의 ret문자열로 합치는 과정이다.

 

#include <bits/stdc++.h>
#define INF 987654321

using namespace std;


string proc(string s) {
    string ret;
    vector<string> vec;
    

    for (int i = 0; i < s.length(); i++) {
        string ss;
        if (s[i] == '(') {
            int n = 1;
            while (n > 0) {
                i++;
                if (s[i] == '(') n++;
                else if (s[i] == ')') { n--; }

                if (n == 0) break;
                ss.push_back(s[i]);
            }
            //cout << ss << endl;
            ss = proc(ss);
        }
        else if (s[i] != ')') {
            ss.push_back(s[i]);
        }

        vec.push_back(ss);
    }


    /*for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << "!!" << endl;
    }*/


    
    
    int cond = 0;//{none, multiply, divide, plus, minus}


    vector<string> vec2;

    for (int i = 0; i < vec.size(); i++) {

        if (cond == 1 || cond == 2) {
            string temp = vec2.back().append(vec[i]);
            if (cond == 1)
                temp.append("*");
            else
                temp.append("/");
            vec2.pop_back();
            vec2.push_back(temp);
            cond = 0;
        }


        else if (vec[i].compare("*") == 0) cond = 1;
        else if (vec[i].compare("/") == 0) cond = 2;

        else vec2.push_back(vec[i]);

    }

    vector<string> vec3;

    for (int i = 0; i < vec2.size(); i++) {

        if (cond == 3 || cond == 4) {
            string temp = vec3.back().append(vec2[i]);
            if (cond == 3)
                temp.append("+");
            else
                temp.append("-");
            vec3.pop_back();
            vec3.push_back(temp);
            cond = 0;
        }


        else if (vec2[i].compare("+") == 0) cond = 3;
        else if (vec2[i].compare("-") == 0) cond = 4;

        else vec3.push_back(vec2[i]);

    }

    

    for (int i = 0; i < vec3.size(); i++) {
        ret.append(vec3[i]);
    }
    return ret;
}




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string buf;

    cin >> buf;

    cout << proc(buf);


    return 0;

}

 

 

소스코드는 위와 같고 푸는데 오래걸렸지만 제출 원트에 성공해서 기분은 좋았다.