[스택] 백준 1918번 후위표기식

백준 1918번

후위표기식

분명히 예전에 후위표기식 문제는 자료구조를 공부할 때 풀어봤다고 생각했는데, 생각하는데 오래 걸렸다. 너무 시간이 오래 걸려 구글링하여 규칙을 정리해서 풀었다.

기본적으로 피연산자 (A~Z)는 출력한다.

연산자( +-*/, ‘(‘, ‘)’ )가 들어온 경우는 네 가지 경우로 나눈다.

+- : 같은 우선 순위

*/: 같은 우선 순위

---

+- 는 */보다 우선순위가 낮다.

( : 열린괄호

) : 닫힌괄호, 열린 괄호가 나올 때까지 출력

큰 조건은 이미 스택에 들어있는 연산자들 중 자신보다 같거나 큰 우선순위를 가지고 있는 연산자들은 모두 pop 한뒤 push 하는 것이다.

여기에는 간단한 이유가 있는데,

1. 자신보다 큰 우선순위를 가지는 연산자는 자신보다 먼저 계산되어야 한다.
2. 자신과 같은 우선 순위를 가지는 연산자도 먼저 계산되어야 한다.
   1. 후위식은 여러 방법으로 표현될 수 있는데, 특별한 규칙이 없는 경우 왼쪽에 있는 것부터 차례로 계산되기 때문이다.
3. 자신보다 낮은 우선순위를 가지는 연산자보다는 자신이 먼저 계산되어야 한다.

조건은 세 가지이다.

1. 닫힌 괄호가 나올 경우 열린 괄호가 나올 때까지 스택에 있는 연산자들을 출력한다.

2. +- 연산자일 경우 스택이 빌 때까지, 혹은 (가 나올때까지 스택에 있는 모든 연산자들을 출력한다.

   +,-,*,/를 출력해야 하는 경우이기 때문에 ( 가 나오기 전까지 모두 출력한다.

3. */연산자일 경우 스택의 top이 * 나/ 인 동안(자신과 같은 우선순위가 나오기 전까지) 스택을 비운다.

   *,/를 출력해야 하는 경우이다.

과정이 끝난 경우 스택에 남아있는 연산자들을 모두 출력한다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

    void flush(stack<char> &operators){
    while(!operators.empty()){
        cout << operators.top();
        operators.pop();
    }
}
int main(){
   string inp;

   cin >> inp;
   stack<char> operators; 
   for(int i=0;i<inp.size();i++){
       if(inp[i]=='('){
           operators.push(inp[i]);
       }
       else if(inp[i]==')'){
           while(operators.top()!='('){
               cout << operators.top();
               operators.pop();
           }
           operators.pop();
       }
       else if(inp[i]=='+' || inp[i]=='-'){
           while(!operators.empty()&&(operators.top()!='(')){
               cout << operators.top();
               operators.pop();
           }
           operators.push(inp[i]);
       }
       else if(inp[i]=='*'||inp[i]=='/'){
           while(!operators.empty()&&(operators.top()=='*'||operators.top()=='/')){
                cout << operators.top();
                operators.pop();
           }
           operators.push(inp[i]);
       }
       else{
           cout << inp[i];
       }
   }
     while(!operators.empty()){
       cout << operators.top();
       operators.pop();
   }
   return 0;
}