[C++] 백준 1918번: 후위 표기식 - Stack

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

1918번: 후위 표기식

 

처음에는 상당히 애를 먹었던 문제

 

처음에 접근했던 방식은

(+) 연산자나 (-) 연산자는 (*) 연산자와 (/) 연산자보다 우선순위가 밀리기때문에 바로바로 출력하지 않고

뒤에 나오는 연산자를 기다리다가 출력을 하는 형식으로,

(*)연산자와 (/)연산자는 우선순위는 높지만 뒤에 또 (*)연산자나 (/)연산자가 나오게 된다면 연속적으로 이루어지기에

역시 저장을 한 후 출력을 하는 형식으로,

괄호가 포함되면 괄호가 나오기 전까지 어쩌구저쩌구..

 

상당히 복잡하게 생각했었는데,

가만 생각해보니 그냥 전부 저장을 한 후 괄호가 나오기 전까지 출력을 해주면 되는 문제였다..

단지 (+)연산자나 (-)연산자가 나왔을 때는 무지성 저장을,

(*)연산자와 (/)연산자가 나왔을 경우 저장된 기호가 (*)연산자와 (/)연산자가 나올 때까지 출력을 해주면 된다.

#include <iostream>
#include <stack>
using namespace std;
int main(){
    string s; cin >> s;
    stack<char>st;
    for(int i=0; i<s.length(); 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.empty() && st.top()!='('){
                cout << st.top();
                st.pop();
            }
            if(!st.empty() && st.top()=='(') 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]=='*' || s[i]=='/'){
            while(!st.empty() && st.top()!='(' && st.top()!='+' && st.top()!='-') {
                cout << st.top();
                st.pop();
            }
            st.push(s[i]);
        }
    }
    while(!st.empty()){
        cout << st.top();
        st.pop();
    }
}