BOJ 1918 후위 표기식

문제

중위 표기식을 후위 표기식으로 바꾸기

복잡도 분석

• 시간복잡도 : O(n) - 스택 사용
• 공간복잡도 : O(n)

접근법

피연산자는 바로 출력하고

연산자의 경우 top에 있는 연산자가 현재 우선순위보다 높거나 같다면 pop

A+B-C

AB+C- 이렇게 나와야 하니까

괄호는 우선순위를 가장 낮게 설정해서 push한다. 다음 연산자들이 위에 쌓이도록…
그 다음 닫는 괄호를 만나면 여는 괄호를 만날때까지 스택의 모든 연산자를 pop 한다

풀이

#include <bits/stdc++.h>
using namespace std;

set<char> s = {'+','-','*','/'};

bool is_alpha(char x){
    return ('A' <= x && x <='Z');
}

bool is_operator(char x){
    if(s.find(x)==s.end()) return false;
    return true;
}

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    deque<char> q;
    string inp; cin >> inp;

    for(int i=0;i<size(inp);i++){
        if (is_alpha(inp[i])){
            cout << inp[i];
        }
        if (is_operator(inp[i])){
            while (!q.empty() && priority(q.back()) >= priority(inp[i])){
                cout << q.back();
                q.pop_back();
            }
            q.push_back(inp[i]);
        }
        if (inp[i]=='('){
            q.push_back('(');
        }
        if (inp[i]==')'){
            while (q.back() != '('){
                cout << q.back();
                q.pop_back();
            }   
            q.pop_back();
        }
    }
    while(!q.empty()){
        if (q.back()=='('){
            q.pop_back();
        }
        else {
        cout << q.back();
        q.pop_back();
        }
    }
    return 0;
}

연산자 우선순위 함수를 만드는걸 생각하기가 힘들었음. 예전에는 트리 순회 이용해서 풀었던걸로 기억함.