baekjoon 1918:후위 표기식

baekjoon 1918 후위 표기식

1918번 후위 표기식

접근

stack안의 우선순위가 항상 오름차순으로 유지된다.
그럼 pop할때는 우선순위가 높은 애들 먼저 pop이 된다.
a*b/c 이런거도 *들어가있다가 먼저 pop되고 /들어가게 된다.
그러면 어 나랑 우선순위 같은 애들있으면 먼저 pop해서 계산하라는 것이다.
왜? 같이 있으면 우선순위가 같기 때문에 헷갈리니까 먼저 아싸리 pop해서 계산 끝내놓자는 마인드
그리고 높은애들이 먼저 pop되면 후위 표기식에서 왼쪽에 있으니까 먼저 계산됨.
우선순위 높은애들 –> 먼저 계산 (합당)
그리고 괄호로 묶인 애들은 사실 안에서 계산이 끝난다는 거니까 여전히 괄호로 감싸져 있을 것이다.
그니까 )나오면 (나올 때까지 pop

코드

#include <iostream>
#include <stack>
using namespace std;
int priority(char c);
int main(){

  string s; cin >> s;
  stack<char> st;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == '(') st.push(s[i]);
    else if(s[i] == ')'){
      while(st.top() != '('){ //)이면 (나올 때 까지 pop한다.
        cout << st.top();
        st.pop();
      }
      st.pop();
    }
    else if(s[i] != '+' && s[i] != '-' && s[i] != '*' && s[i] != '/'){
      cout << s[i]; //피연산자는 그대로 출력
    }
    else if(st.empty()){
      st.push(s[i]); //연산자는 stack 비어있으면 그냥 stack에 push
    }
    else if(priority(s[i])>priority(st.top())){
      st.push(s[i]); //우선순위가 top보다 더 높으면 push
    }
    else{
      while(!st.empty() && priority(s[i])<=priority(st.top())){
        cout << st.top(); //우선순위가 top보다 낮거나 같으면 pop
        st.pop();
      }
      st.push(s[i]);
    }
  }
  while(!st.empty()){
    cout << st.top();
    st.pop();
  }
  return 0;
}
int priority(char c){
  if(c == '*' || c == '/') return 2;
  else if(c == '+' || c == '-') return 1;
  else return 0;
}

추가 정보

후위 표기식을 계산할 때도 stack을 이용해서 한다.