[BOJ] 1918 후위표기식 C++

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

1918번: 후위 표기식

일반적인 계산식(중위 표기식)이 주어졌을 때, 이를 후위 표기식으로 바꾸는 문제이다. 괄호가 들어가서 예외 처리를 많이 해야 하는 문제이지만 다행히 사람들이 많은 반례를 구해놓아서 쉽게 구할 수 있었다.

후위->중위, 중위->후위로 변환할 때는 stack을 이용하면 된다. 또, 이 문제를 풀 때 개념은 계산순서의 우위를 이용해야 한다는 것이다.

1. * ,  / 이 올 경우 자신보다 계산순서가 낮은 ( , - , + 가 나올 때 까지 pop을 해준다.

2. - , +가 올 경우 자신보다 계산순서가 낮음 ( 가 나올 때 까지 pop을 해준다.

3. )가 올 경우 ( 가 나올 때 까지 pop을 해준다.

괄호의 계산 우선순위가 꼴찌라는 것이 핵심!(항상 괄호 안에 있는 식을 먼저 계산해야 하므로)

 

코드

#include <iostream>

#include <stack>

#include <string>

using namespace std;

stack<char> st;

string s;

int main(){

    cin>>s;

    for(int i=0;i<s.size();i++){

        if(('A'<=s[i]&&s[i]<='Z')||s[i]=='('){

            st.push(s[i]);

        }else if(s[i]=='*'||s[i]=='/'){

            while(!st.empty()){

                if(st.top()=='('||st.top()=='+'||st.top()=='-') break;

                cout<<st.top();

                st.pop();

            }

            st.push(s[i]);

        }else if(s[i]=='-'||s[i]=='+'){

            while(!st.empty()){

                if(st.top()=='(') break;

                cout<<st.top();

                st.pop();

            }

            st.push(s[i]);

        }else if(s[i]==')'){

            while(st.top()!='('){

                cout<<st.top();

                st.pop();

            }

            st.pop();

        }

    }

    while(!st.empty()){

        cout<<st.top();

        st.pop();

    }

    return 0;

}