[백준 1918번] 후위 표기식 (C++)

문제링크 : https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string s;
stack<char>st;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> s;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i] >= 'A' && s[i] <= 'Z') cout << s[i]; //문자는 그냥 출력
        else if (s[i] == '(') st.push(s[i]);
        else if (s[i] == ')')
        {
            while(st.top() != '(') // 괄호 사이값 출력
            {
                cout << st.top();
                st.pop();
            }
            st.pop(); // '(' 삭제
        }
        else if (s[i] == '+' || s[i] == '-')
        {
            while(!st.empty() && st.top()!= '(') // '(' 제외 다 출력 (우선순위 제일 낮음)
            {
                cout << st.top();
                st.pop();
            }
            st.push(s[i]);
        }
        else if (s[i] == '*' || '/')
        {
            while(!st.empty() && (st.top()=='*' || st.top() == '/')) //*나 /만 출력
            {
                cout << st.top();
                st.pop();
            }
            st.push(s[i]);
        }
        
    }

    while(!st.empty())
    {
        cout << st.top();
        st.pop();
    }


    return 0;
}

스택을 활용한 문제이다.

정보처리기사를 공부하면서 후위표기식에 대한 문제를 제법 풀어봤었기 때문에 다소 친근하게 느껴진 문제이기도 하다.

 

기본적으로 문자는 바로 출력해주고, 연산자에 대해서만 스택에 넣어주면 된다.

여기서 문제는 스택에 넣은 연산자를 우선순위에 따라서 출력해주어야하고, 괄호에 따라서 또 우선순위가 달라질 수 있음에 유의해야 한다.

 

그래서 ( 괄호일때도 마찬가지로 스택에 넣어준다.

이후 )괄호가 스택에 들어오면 괄호 사이의 연산자를 출력해주고 ( 괄호를 스택에서 없애준다.

() 괄호가 우선순위가 제일 높다.

 

다음으로 우선순위가 높은 것은 * 또는 / 이다.

현재 값이 해당 연산자일때 스택에서 해당 연산자만 출력하도록 하고 스택에 현재 값을 넣어준다.

 

제일 우선순위가 낮은 것은 + 또는 - 이다.

현재 값이 해당 연산자일때 스택에서 ( 제외한 모든 값들을 출력하고 스택에 현재 값을 넣어준다.

 

우선순위에 따른 계산을 모두 마친후 마지막으로 현재 스택에 남은 값들을 출력하여 마무리해준다.

 

여기서 주의해야할 것은 스택은 후입선출이기 때문에 우선순위가 제일 낮은 +나 -에 대한 계산이 먼저 이루어져야 한다.

그렇지 않으면 스택에 쌓은 순서가 +,-보다 *,/ 가 먼저 쌓여있어서 우선순위가 높은 *,/가 늦게 출력되는 경우가 발생한다.