[BOJ] 백준 1918 후위 표기식 c++ (스택)

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

1918번: 후위 표기식

---

풀이

컴퓨터과에서 저학년때 배우는 수식.. 이 문제는 중위표기식을 후위표기식으로 고치는 문제이다.

막막할 수 있지만 생각해보면 단순하다. 우선순위와 연산자를 처리해야 하므로 stack에 조건부로 pop, push를 처리해주면 된다.

먼저 문자열을 입력받고 인덱스를 순회하며 경우에 따라 처리한다.

 

알파벳 대문자인 경우

바로 정답으로 출력한다. (연산자와 관련없음)

'(' 인 경우

괄호의 경우 추후 ')'가 나올때 모두 출력해주어야 하므로 스택에 push한다.

')' 인 경우

'('가 나올때까지 모두 출력&pop한다.

'*', '/' 인경우

곱하기 나누기는 우선순위가 더하기/빼기보다 높으므로 스택의 top이 *, / 인 경우에 출력&pop을 해준다.

(왜냐하면 먼저 들어온 *, / 이므로 후위표기식에서 먼저 출력해주어야 하기 때문)

else if(str[i] == '*' || str[i] == '/'){
    while(!st.empty() && (st.top() == '*' || st.top() == '/')){
        cout << st.top();
        st.pop();
    }
    st.push(str[i]);
}

그 후 스택에 push한다.

'+', '-' 인 경우

곱하기/나누기보다 우선순위가 낮으므로 '('이 아니면 모두 출력한다.

---

코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string str, ans;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> str;

    stack<char> st;

    for(int i = 0; i < str.length(); i++){
        if(str[i] >= 'A' && str[i] <= 'Z'){
            cout << str[i];
            continue;
        }

        if(str[i] == '(')
            st.push(str[i]);
        else if(str[i] == ')'){
            while(!st.empty() && st.top() != '('){
                cout << st.top();;
                st.pop();
            }
            st.pop();
        }
        else if(str[i] == '*' || str[i] == '/'){
            while(!st.empty() && (st.top() == '*' || st.top() == '/')){
                cout << st.top();
                st.pop();
            }
            st.push(str[i]);
        }
        else if(str[i] == '+' || str[i] == '-'){
            while(!st.empty() && st.top() != '('){
                cout << st.top();
                st.pop();
            }
            st.push(str[i]);            
        }
    }
    while(!st.empty()){
        cout << st.top();
        st.pop();
    }
    return 0;
}