후위 표기식 (feat. 백준, 1918번)

후위 표기식
https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    map<char, int> chk;
    chk['+'] = chk['-'] = 0;
    chk['*'] = chk['/'] = 1;
    chk['('] = chk[')'] = -1;
    string str;
    stack<char> st;
    cin >> str;
    for(auto& ch : str){
        if('A' <= ch && ch <= 'Z')
            cout << ch;
        else if(ch == '(')
            st.push(ch);
        else if(ch == ')'){
            while(st.top() != '(')
                cout << st.top(), st.pop();
            st.pop();
        }
        else{
            while(!st.empty() && chk[st.top()] >= chk[ch])
                cout << st.top(), st.pop();
            st.push(ch);
        }
    }
    while(!st.empty())
        cout << st.top(), st.pop();
	return 0;
}
// *&)*@*

 

반응형

1. 알파벳은 그대로 출력해줍니다.
2. '(' 는 스택에 삽입하고, ')' 는 출력하진 않고 스택에서 '(' 가 나올때까지 스택을 출력&비워줍니다.
3. 각 연산은 '*', '/' 가 우선순위가 높으므로 해당 연산식이 나올때까지 스택을 비워줍니다.