문제

1918번: 후위 표기식

풀이

문제에도 설명되어 있지만 후위 표기식은 피 연산자가 연산자 앞에 위치하며 연산자끼리의 우선순위를 비교하여 그 순서가 결정되고 괄호가 필요 없게 됩니다. 우선 순위가 높은 연산자가 낮은 연산자보다 먼저 배치됩니다. 중요한건 연산자들 사이의 우선순위를 비교하여 어떻게 순서대로 배치할 것인지가 되겠습니다.

사실 스택을 이용하면 쉽게 해결할 수 있습니다. 후위표기식의 계산 과정도 스택으로 구현할 수 있듯이 이 문제도 스택으로 구현할 수 있습니다.
연산자의 종류와 우선순위를 담는 스택이 있을 때, 스택의 값과 새로운 연산자의 우선순위를 비교하여 새로운 연산자의 우선순위가 더 낮을 때까지 스택의 값을 출력하여 순서대로 정답 배열에 입력합니다.

문제에서는 괄호에 대한 우선순위도 고려해야 합니다.
(가 주어진다면 앞으로 나올 연산자들의 우선순위를 +2 해주고,
)가 주어진다면 다시 -2 해주어 관리합니다.
문제에서 항상 올바른 괄호짝을 입력으로 줄테니 우선순위가 꼬일 일은 없네요.

입력으로 주어진 식에 대해 모두 처리 했다면 스택에 남아있는 연산자들을 차례대로 출력하여 정답 배열에 입력합니다.

코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    string fomu;
    vector<pair<char, int>> operatorStack;
    vector<char> answer;
    cin >> fomu;

    int globalPri = 0;
    for (auto ch : fomu)
    {
        int localPri;
        switch(ch)
        {
            case('('):
                globalPri += 2;
                break;
            case(')'):
                globalPri -= 2;
                break;

            case('+'):
            case('-'):
                localPri = 1;
                
                while (!operatorStack.empty() && operatorStack.back().second >= localPri + globalPri)
                {
                    answer.push_back(operatorStack.back().first);
                    operatorStack.pop_back();
                }
                operatorStack.push_back({ch, localPri+globalPri});
                break;

            case('*'):
            case('/'):
                localPri = 2;
                
                while (!operatorStack.empty() && operatorStack.back().second >= localPri + globalPri)
                {
                    answer.push_back(operatorStack.back().first);
                    operatorStack.pop_back();
                }
                operatorStack.push_back({ch, localPri+globalPri});
                break;

            default:
                answer.push_back(ch);
                break;
        }
    }
    while (!operatorStack.empty())
    {
        answer.push_back(operatorStack.back().first);
        operatorStack.pop_back();
    }
        
    for(auto a  : answer)
        cout << a;
    cout << endl;
    return 0;
}