[ 백준 1918 ] 후위 표기식 (C++)

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

후위 표기식에 대한 설명은 '알고리즘' 파트에서 '중위 표기식을 후위 표기식으로 변환 후 계산'글에 정리해놨다. 링크 바로가기! 

 

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

/*
 1. 피연산자는 무조건 출력
 2. 연산자인 경우
    1) top보다 우선순위 크면 push
    2) top보다 우선순위 작거나 같으면 pop 후 반복
 3. '('는 무조건 push
 4. ')'가 나타나면 '(' 만날때까지 pop 후 출력
 5. 피연산자가 더이상 없으면 stack에 있는거 전부 pop 후 출력
*/

int priority(char ch){
    if(ch == '+' || ch == '-') return 1;
    if(ch == '*' || ch == '/') return 2;
    return 0;
    // '('는 원래 우선순위가 가장 높지만 top에 '('가 있는 경우를 고려해줘야 하기 때문에 0으로 설정
}

int main(){
    string input, ans;
    stack<char> s;
    char c;
    
    cin >> input;
    
    for(int i = 0; i < input.length(); i++){
        c = input[i];
        
        // 1. 피연산자는 출력
        if(c >= 'A' && c <= 'Z'){
            ans += c;
            continue;
        }
        
        // 2. 스택이 비어있는 경우 또는 '('인 경우 push
        if(s.empty() || c == '('){
            s.push(c);
            continue;
        }
        
        // 3. ')'인 경우 '(' 만날때까지 출력
        if(c == ')'){
            while(s.top() != '('){
                ans += s.top();
                s.pop();
            }
            s.pop(); // '('는 삭제
            continue;
        }
        
        // 4. top보다 우선순위 크면 push
        if(priority(s.top()) < priority(c)){
            s.push(c);
        }
        
        // 5. top보다 우선순위 작거나 같으면 pop 후 반복
        else{
            while(!s.empty() && priority(s.top()) >= priority(c)){
                ans += s.top();
                s.pop();
            }
            s.push(c);
        }
    }
    
    // 6. 스택이 안 비었으면 전부 출력
    while(!s.empty()){
        ans += s.top();
        s.pop();
    }
    
    cout << ans << endl;
    
    return 0;
}