[BOJ] 1918 후위표기식

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

후위표기식은 스택의 대표주자라 할 만큼 중요한 내용이다.

알고리즘은 간단하다.

1. 열린 괄호 -> push

2. 닫힌 괄호 -> 열린 괄호가 나올때까지 pop

3. 피연산자 -> 그대로 출력

4. 연산자 -> 자기보다 우선순위가 낮거나, 열린 괄호가 나오거나, 스택이 빌 때까지 pop 후 push

코드는 이를 그대로 구현했다.

4번에 열린 괄호가 나오는 것을 별도로 처리해주지 않은데 주의.

난이도는 1.5/5 정도?

#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int pr(char c)
{
    if(c=='(') return 0;
    else if(c=='+' || c=='-') return 1;
    else if(c=='*' || c=='/') return 2;
}
 
int main()
{
    stack<char> S;
    string str;
    cin>>str;
 
    for(int i=0;i<str.size();i++)
    {
        char c=str.at(i);
        if('A'<=c && c<='Z') cout<<c;
        else if(c=='(') S.push(c);
        else if(c==')')
        {
            while(S.top()!='(')
            {
                cout<<S.top();
                S.pop();
            }
            S.pop();
        }
        else
        {
            while(!S.empty() && pr(S.top())>=pr(c))
            {
                cout<<S.top();
                S.pop();
            }
            S.push(c);
        }
    }
    while(!S.empty())
    {
        cout<<S.top();
        S.pop();
    }
    return 0;
}