백준 1918 - 후위 표기식

문제 설명 

 

 

후위표기식2 와 달리 계산하는 것이 아닌 중위표기식을 후위표기식으로 바꾸는 방법이다.

 

=>연산자를 stack에 넣는 것으로 한다. 

=> ( 여는 괄호가 나오면 여는 괄호를 무조건 stack에 쌓는다. 

=> ) 닫는 괄호가 나오면 (여는 괄호가 나올 때까지 stack을 pop하며 찾는다. 

=> stack안에 연산자들은 위에 있는 연산자가 아래에 있는 연산자보다 우선순위가 높아야한다. (같아서도 안됨!) 

=> ( 여는 괄호의 경우를 감안하여 코드를 짜야한다. 

 

*** 왜 나는 한 문제를 푸는데 기본적으로 한시간이 쓰이는지.... 조금 더 빨리 답을 찾아가는 습관을 들여야겠다. 

 

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

stack<char> st;

void postfix(char oper)
{
    if(oper == '(') // open operator
    {
        st.push(oper);
    }
    else if(oper == ')') //close operator
    {
        while(st.top() != '(')
        {
            cout<<st.top();
            st.pop();
        }
        st.pop();
    }
    else // when normal operator
    {
       if(oper == '*' || oper == '/')
       {
           while(!st.empty() && (st.top() == '*' || st.top() == '/' )  )
           {
               cout<<st.top();
               st.pop();
           }// 이게 더 작은 경우니까.....
           st.push(oper);
       }
        else if( oper== '+' ||oper == '-')
        {
            while(!st.empty() &&  ( st.top() != '(' ) ) // ( 여는 괄호가 나올 때까지 다 뺀다.
            {
                cout<<st.top();
                st.pop();
            }
            st.push(oper);
        }
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    string middle;
    cin>>middle;
    

    
    for(int i=0; i<middle.length(); ++i)
    {
        if(middle[i] != '+' && middle[i] != '-' && middle[i] != '*' && middle[i] != '/'  && middle[i] != '(' && middle[i] != ')')//case miidle[i] is alphabet
        {
            cout<<middle[i];
        }
        else
        {
            postfix(middle[i]);
        }
    }
    while(!st.empty())
    {
        cout<<st.top();
        st.pop();
    }
    return 0;
}