[BOJ][C++] 백준 1918번: 후위 표기식

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

1918번: 후위 표기식

 

풀이

피연산자는 바로 답 문자열에 넣는다.

연산자는 스택에 넣어서 관리한다.

 

닫힌 괄호가 나오면

스택 내에 열린 괄호가 나올 때까지 스택에 있는 연사자들을 뽑아서 답 문자열에 넣는다.

 

연산자를 스택에 넣을 때 스택 내 연산자가 현재 연산자보다 우선순위가 높거나 같다면

스택에 있는 연산자를 다 뽑아서 답 문자열에 넣는다

#include <iostream>
#include <stack>

using namespace std;

int priority(char c) {
    if(c=='*' || c=='/') return 1;
    if(c=='+' || c=='-') return 2;
    if(c=='(' || c==')') return 3;
    return 0;
}

int main() {
    stack<char> op;
    string ans = "";
    
    string input;
    cin >> input;
    
    for(char i : input) {
        if(priority(i)==0) { // 피연산자
            ans += i;
        } else if(i=='(') {
            op.push(i);
        } else if(i==')') {
            while(!op.empty() && op.top()!='(') {
                ans += op.top();
                op.pop();
            }
            op.pop();
        } else { // 연산자 *,/,+,-
            while(!op.empty() && priority(op.top()) <= priority(i)) {
                ans += op.top();
                op.pop();
            }
            op.push(i);
        }
    }
    while(!op.empty()) {
        ans += op.top();
        op.pop();
    }
    
    cout << ans;
}