BOJ - 1918. 후위 표기식

www.acmicpc.net/problem/1918

1918번: 후위 표기식

경우의 수는 크게 네 가지로 나누어주고 stack을 사용해서 구현하였다.

1. 피연산자가 입력된 경우

2. 여는 괄호 '(' 가 입력된 경우

3. 닫는 괄호 ')' 가 입력된 경우

4. 연산자가 입력된 경우

 

각각의 경우에 대해 어떤 일이 벌어져야하는지 생각해보았다.

1. 피연산자가 입력된 경우

    피연산자가 입력되었을 경우에는 우선 출력한다. (후위표기식이기 때문에 연산자는 피연산자 이후에 나오기 때문)

2. 여는 괄호 '(' 가 입력된 경우

    특별한 액션이 발생하지 않고 스택안에 우선 넣어준다.

3. 닫는 괄호가 ')' 가 입력된 경우

    닫는 괄호가 입력된 경우 스택을 탐색하여 가장 최근에 나온 '(' 까지의 연산자를 출력한다.

  

(스택이 비었는데 스택의 top을 구하려거나 pop 을 하려면 런타임 에러가 발생할 수도 있기 때문에 스택이 비어있는지 검사하는 조건도 포함해준다.)

출력한 연산자는 스택에서 pop해준다. 연산자를 다 pop해줬으면 , 괄호 안에 있는 덩어리들이 모두 출력됬다는 뜻이므로 마지막으로 열린 괄호도 pop 해주면 된다.

 

4. 연산자가 입력된 경우

연산자가 입력된 경우는 두 가지로 또 나뉘게 된다.

+, - 연산보다 *,/ 연산이 먼저 수행되기 때문에 우선순위는 *,/ 가 더 높다.

 

4-1 우선순위가 높은 *, / 연산의 경우

우선순위가 높은 연산자는 낮은 연산자보다 먼저 수행된다.

스택의 top에 있는 연산자가 *이나 / 라면 스택의 top을 출력하고 pop해준다

(스택 안에 +, - 나 +,- 사이에 끼어있는 *,/는 남아있어진다.)

 

 

4-2 우선순위가 낮은 +, - 연산의 경우

 스택은 우선 순위가 낮은 연산자부터 큰 연산자 순으로 쌓여야 한다.

그렇기 때문에 먼저 스택 내에 있는 연산자들을 차례대로 출력해준 이후 그 위에 새로 입력할 연산자(+,-)를 삽입해준다.

( 괄호로 감싸져 있는 경우도 있기 때문에, 열린 괄호가 등장할때까지라는 조건을 함께 추가해줘야한다.)

 

 

스택안에 연산자들이 남아있을 수도 있는데 남은 연산자들을 top에서부터 순차적으로 출력해준다.

 

최종코드

 

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string str;
    cin>>str;
    stack<char> op;
    for(int i=0;i<str.size();i++){
        if(str[i]=='('){//여는 괄호인 경우 - ok
            op.push(str[i]);
        }else if(str[i]==')'){//닫는 괄호인 경우 - ok
            while(op.top()!='(' && !op.empty()){
                cout<<op.top();
                op.pop();
            }
            op.pop(); //'('도 pop해준다.

        }
        //스택은 우선순위가 낮으면 밑에 깔려야함 (높은게 위에 가도록)
        else if(str[i]=='+' || str[i]=='-'){ //우선순위가 낮은 연산자인 경우
            if(op.empty() || op.top()=='('){
                op.push(str[i]);
            }else{
                while(!op.empty() && op.top()!='('){
                    cout<<op.top();
                    op.pop();
                }
                op.push(str[i]);
            }
        }else if(str[i]=='*' || str[i]=='/'){//우선순위가 높은 연산자인 경우
            if(op.empty() || op.top()=='('){
                op.push(str[i]);
            }else{
                while(!op.empty() && (op.top()=='*' || op.top()=='/')){
                    cout<<op.top();
                    op.pop();
                }
                op.push(str[i]);
            }
        }else{//알파벳인 경우 - ok
            cout<<str[i];
        }
    }
    while(!op.empty()){
        cout<<op.top();
        op.pop();
    }



    return 0;
}