후위 표기식

후위 표기식은 꽤 유명한 문제인데 스택을 사용해야 한다.

기호는 +,-,*,/,(,)만 등장한다.

문제를 풀기 위한 스텝을 보면

일단 문자 A,B같은게 나오면 그냥 출력한다.

기호가 나오면 스택에 넣는데 넣기 전에 자기보다 우선순위가 높은 것들을 출력해야 한다.

+,-는 자기보다 먼저 등장한 +나 -, 그리고 *,/가 전부 다 우선순위가 높기 때문에 (가 나오기 전까지 다 출력해야 한다.

if(eq[i]=='+' || eq[i]=='-'){
    while(!st.empty()){
        if(st.top()=='(') break;
        printf("%c",st.top());
        st.pop();
    }
    st.push(eq[i]);
}

*,/는 자기보다 먼저 등장한 *,/만 출력하면 된다.

else if(eq[i]=='*' || eq[i]=='/'){
    while(!st.empty()){
        if(!(st.top()=='*' || st.top()=='/')){
                break;
        }
        printf("%c",st.top());
        st.pop();
    }
    st.push(eq[i]);
}

(는 그냥 push하면 되고 )가 나오면 (가 나올 때까지 출력하면 된다.

else if(eq[i]=='('){
    st.push(eq[i]);
}
else if(eq[i]==')'){
    while(st.top()!='('){
        printf("%c",st.top());
        st.pop();
    }
    st.pop();
}

간단한 문제지만 좀 헷갈렸던 거 같다.

아래는 전체 코드이다.

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>st;
char eq[10004];
int main()
{
    scanf("%s",eq);
    for(int i=0;i<strlen(eq);i++){
        if(eq[i]=='+' || eq[i]=='-'){
            while(!st.empty()){
                if(st.top()=='(') break;
                printf("%c",st.top());
                st.pop();
            }
            st.push(eq[i]);
        }
        else if(eq[i]=='*' || eq[i]=='/'){
            while(!st.empty()){
                if(!(st.top()=='*' || st.top()=='/')){
                        break;
                }
                printf("%c",st.top());
                st.pop();
            }
            st.push(eq[i]);
        }
        else if(eq[i]=='('){
            st.push(eq[i]);
        }
        else if(eq[i]==')'){
            while(st.top()!='('){
                printf("%c",st.top());
                st.pop();
            }
            st.pop();
        }
        else{
            printf("%c",eq[i]);
        }
    }
    while(!st.empty()){
        printf("%c",st.top());
        st.pop();
    }

}