[백준,c++] 1918번 - 후위 표기식

문제

1918번: 후위 표기식

 

코드

#include <iostream>
#include <stack>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s, ans; cin>>s;
    stack<char>st;
    for(char c: s){
        if(c=='(') st.push(c);
        else if(c==')'){
            while(st.top()!='('){
                cout<<st.top();
                st.pop();
            }
            st.pop();
        }
        else if(c =='*'|| c =='/' || c =='+' || c=='-'){
            if(c=='*'|| c=='/'){
                while(!st.empty() && (st.top()=='*' || st.top() == '/')){
                    cout<<st.top();
                    st.pop();
                }
                st.push(c);
            }
            else{
                while(!st.empty() && st.top()!='('){
                    cout<<st.top();
                    st.pop();
                }
                st.push(c);
            }
        }
        else cout<<c;
        
    }
    while(!st.empty()){
        if(st.top()!='(') cout<<st.top();
        st.pop();
    }
}

 

풀이

1935번: 후위 표기식2

위 후기 표기식2가 후위 표기식을 기준으로 값을 계산하는 문제였다면 이 문제는 중위 표기식을 후위 표기식으로 만드는 문제입니다.

위 문제의 풀이 아이디어는 다음과 같습니다.

1. 괄호 혹은 연산자가 아닌 알파벳일 경우 바로 출력한다.
2. 여는 괄호일 경우 스택에 추가한다.
3. 닫는 괄호일 경우 여는 괄호가 나올 때까지 스택에 있는 값을 차례대로 전부 출력한다.
4. 연산자일 때 우선순위가 높은 * 혹은 / 인 경우 스택에 또 다른 우선순위가 높은 연산자인 * 혹은 / 가 나올 때까지 스택에 있는 값을 전부 출력한다.
5. 연산자일 때 상대적으로 우선순위가 낮은 + 혹은 - 일 경우 스택의 값이 여는 괄호가 아닐 때까지 전부 출력한다.
6. 마지막으로 스택에 남아있는 값들이 있을 수 있기 때문에 스택의 값을 전부 출력한다.

한번 (A + B * C ) - D / E 를 입력으로 예를 들어보겠습니다. 출력으로는 ABC*+DE/- 가 나와야 할 것입니다.