[BOJ] 백준 1918 후위표기식

[BOJ] 백준 1918 후위표기식

문제 링크 : https://www.acmicpc.net/problem/1918


이 문제는, 자료구조를 공부함에 있어 교과서에 꼭 서술되는 유형 입니다.
스택을 이용하여 push/pop 하면 되는 문제입니다.
처음 볼때는 막막 하지만, 규칙 몇가지만 알고 있다면 풀 수 있습니다.




규칙
1. 피연산자인 A,B... 는 바로바로 출력 해줍니다.
2. 연산자 +, -, *, / 그리고 괄호 ( , ) 는 서로 우선순위가 있습니다.
2-1) 우선순위가 낮은 연산자가 들어올경우, 스택의 Top에 그보다 높거나 같은순위의 연산자가 있을경우 그 높은순위의 연산자를 pop 해줍니다.
2-2) 더하기와 빼기는 연산자들 중 우선순위가 가장 낮습니다. 따라서 스택에 덧셈 혹은 뺄셈을 넣을 예정이라면 현재 스택에 있는 곱셈, 나눗셈 연산자를 스택이 비거나 왼쪽괄호 ( 를 만날때 까지 pop 합니다.
2-3) 곱셈과 나눗셈을 스택에 넣어야 한다면 같은 우선순위를 가지는 곱셈,나눗셈 연산자가 스택에 있을경우 pop 해줍니다.
2-4) 오른쪽괄호 ) 가 나왔을 때, 왼쪽괄호를 만날때까지 모두 pop 해줍니다.
3. 스택에 남아있는 원소가 있을 경우, 모두 출력해 줍니다.




소스 코드 :

#include 
#include 
#include 
using namespace std;
int main()
{
 string s;
 cin >> s;
 stack st;
 for (int i = 0; i < s.length(); i++) {

  if (isalpha(s[i])) { // 피연산자의 경우 바로 출력.
   cout << s[i];
   continue;
  }
  if (s[i] == '(') { // 왼쪽괄호는 바로 스택에 넣어줌.
   st.push(s[i]); 
   continue;
  }
  else if (s[i] == '*' || s[i] == '/') { // * / 을 넣어야 할 경우 
   if (!st.empty()) {
    while (st.top() == '/' || st.top() == '*') { // 동일 우선순위인 /와 *을 만날경우 pop.
     cout << st.top();
     st.pop();
     if (st.empty()) break;
    }
    st.push(s[i]);
   }
   else {
    st.push(s[i]);
   }
  }
  else if (s[i] == '-' || s[i] == '+') { // + 와 - 을 넣어야 할 경우
   if (!st.empty()) {
    while (st.top() != '(' ) { // 같거나 높은 우선순위 + - / * 모두 pop 한다.
     cout << st.top();
     st.pop();
     if (st.empty()) break;
    }
    st.push(s[i]);
   }
   else {
    st.push(s[i]);
   }
  }
  else if (s[i] == ')') {
   while (st.top() != '(') { // ) 넣어야 할 경우 ( 을 만날때까지 모두 pop.
    cout << st.top();
    st.pop();
    if (st.empty()) break;
   }
   st.pop();
  }
 }
 while (!st.empty()) { // 잔여요쇼 pop
  cout << st.top();
  st.pop();
 }
}