백준 1918 후위 표기식

STL Stack을 이용하여 구현한다.
중위 표기를 후위 표기를 바꾸기 위해서 해야하는 행동
1. ( 은 스택에 넣는다.
2. )은 ( 가 나올 때까지 Stack을 비운다.
3. + - * / 는 Stack이 비어있는지 확인한다.
3-1 Stack이 비어있지 않는 경우 현재 연산자와 Stack top에 있는 연산자를 비교한다.
3-1-1 top 연산자가 우선 순위가 높은 경우 출력하고 다음 top도 3-1 행동을 반복한다.
4. 현재 연산자를 stack에 넣어준다.

---

#include <iostream>
#include <stack>
using namespace std;

int priority(char c) {
    switch (c){
        case '(': case ')': return 0;
        case '+': case '-': return 1;
        case '*': case '/': return 2;
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    stack<char> st;
    for(char c: s){
        if( c >= 'A' && c <= 'Z' ) cout << c;
        else if( c == '(' ) st.push(c);
        else if( c == ')'){
             while(!st.empty()){
                char op = st.top();
                st.pop();
                if( op == '(' ) break;
                else cout << op;
            }
        } else {
            while(!st.empty()){
                char op = st.top();
                if( priority(c) <= priority(op)){
                    st.pop();
                    cout << op;
                } else break;
            }
            st.push(c);
        } 
    }
    while(!st.empty()){
        cout << st.top();
        st.pop();
    }
}

먼저 배열을 사용하여 구현하는 것이 훨씬 빠르다. 현 문제는 길이가 100이 넘지 않아서 배열사이즈을 100으로만 설정해줘도 크게 문제 없고 Vector로 구현하는 것보다 빠르다.

배열로 Stack을 구현해서 문제를 풀어도 되지만 귀찮으니까 STL Stack을 이용한다.

위 문제는 시간 0 ms가 걸리면서 끝난다.

하지만 위 코드상

            while(!st.empty()){
                char op = st.top();
                if( priority(c) <= priority(op)){
                    st.pop();
                    cout << op;
                } else break;
            }

이런 부분에서 st.top() 함수를 자주 사용하여 비교하거나 출력할 때 사용했더니 시간 초과가 나서 이번 기회로 함수 호출을 자주하면 안되겠다는 생각을 하게 되었습니다.