[백준][C++] 1918: 후위 표기식

문제

풀이

• 스택을 이용한다.
• 피연산자는 바로 answer의 뒤에 추가한다. 
• 연산자는 다음으로 처리된다.
  • 스택이 비어있다면 스택에 연산자를 push한다.
  • 연산자는 스택의 top과 우선순위를 비교하여 자신보다 우선순위가 낮을 때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, 스택에 자신을 push한다.
• ' ( '는 바로 스택에 push한다.
• ' ) '는 스택에서 ' ( '가 나올때까지 top을 answer의 뒤에 추가하고 스택을 pop한다. 그 후, ' ( '를 스택에서 삭제한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <unordered_map>

using namespace std;

// 연산자 우선순위
unordered_map<char, int> priority = {
    {'(', 0},
    {'-', 1},
    {'+', 1},
    {'*', 2},
    {'/', 2}
};

int main()
{
    string s;
    stack<char> st;
    string answer;

    cin >> s;

    for (int i = 0; i < s.size(); ++i)
    {
        if (65 <= int(s[i]) && int(s[i]) <= 90)
        {
            answer.push_back(s[i]);
        }
        else if (s[i] == '(')
        {
            st.push(s[i]);
        }
        else if (s[i] == ')')
        {
            // '('가 top일 때까지 top을 answer의 끝에 추가하고 pop
            while (st.top() != '(')
            {
                answer.push_back(st.top());
                st.pop();
            }
            // '('를 pop
            st.pop(); 
        }
        else
        {
            // 스택의 top이 s[i]보다 낮을 때까지 top을 answer의 끝에 추가하고 pop
            while (!st.empty() && priority.find(s[i])->second <= priority.find(st.top())->second)
            {
                answer.push_back(st.top());
                st.pop();
            }
            
            st.push(s[i]);
        }
    }

    // 스택에 남은 연산자를 answer의 끝에 추가
    while (!st.empty())
    {
        answer.push_back(st.top());
        st.pop();
    }

    cout << answer;

    return 0;
}