BOJ 1918 - 후위 표기식

문제

아래와 같은 조건을 만족하는 중위 표기식이 주어질 때 후위 표기식으로 변환하는 문제이다.

• 알파벳 대문자로 이루어진 피연산자는 한 번씩만 등장
• -가 가장 앞에 오거나 AB와 같이 *가 생략되는 수식은 주어지지 않음
• 표기식은 알파벳 대문자, +, -, *, /, (, )로만 이루어지고, 길이는 100이하임

풀이

연산자의 우선순위를 아래와 같이 설정한다.

• *, / : 1
• +, - : 2
• ( : 3

중위 표기식을 읽으면서 알파벳은 변환된 후위 표기식 문자열 ans에 바로 추가한다.
연산자일 경우 아래 조건에 따라 연산자를 저장하는 스택 st로 처리한다.

• st가 비어있거나 top이 (일 경우 현재 연산자 push
• 현재 연산자가 )일 경우 (가 나올 때까지 st의 top pop
• 현재 연산자가 st의 top보다 우선 순위가 높을 경우(숫자가 낮을 경우) 현재 연산자 push
• 현재 연산자가 st의 top과 우선 순위가 같을 경우 st의 top을 ans에 넣고 pop, 현재 연산자를 push
  • A*B*C와 같이 우선 순위가 동일할 경우 AB*C*와 같이 계산 순서가 보장되어야 함
• 현재 연산자가 st의 top보다 우선 순위가 낮을 경우 st의 top보다 우선 순위가 높아질 때까지 top pop 이후 현재 연산자 push
  • A+B*C+D와 같은 경우 ABC*+D+이 되어야 하기 때문

소스코드

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using lld = long long;

int getp(char o) {
    if (o == '*' || o == '/')
        return 1;
    if (o == '+' || o == '-')
        return 2;
    if (o == '(') return 3;
}

int isOp(char c) {
    if (c == '*' || c == '/' || c == '+' || c == '-' || c == '(' || c == ')')
        return 1;
    else
        return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string m, ans;
    stack<char> st;
    cin >> m;
    for (int i = 0; i < m.length(); i++) {
        if (isOp(m[i])) {
            if (st.empty() || m[i] == '(')
                st.push(m[i]);
            else if (m[i] == ')') {
                while (st.top() != '(') {
                    ans.insert(ans.end(), st.top());
                    st.pop();
                }
                st.pop();
            } else if (getp(st.top()) > getp(m[i]))
                st.push(m[i]);
            else if (getp(st.top()) == getp(m[i])) {
                ans.insert(ans.end(), st.top());
                st.pop();
                st.push(m[i]);
            } else {
                while (!st.empty() && (getp(st.top()) <= getp(m[i]))) {
                    ans.insert(ans.end(), st.top());
                    st.pop();
                }
                st.push(m[i]);
            }
        } else
            ans.insert(ans.end(), m[i]);
    }
    while (!st.empty()) {
        ans.insert(ans.end(), st.top());
        st.pop();
    }
    cout << ans << '\n';
    return 0;
}

풀고나서

• A*B*C의 순서를 보장해야 하고 괄호가 추가되어 좀 더 구현 문제에 가까운 것 같다.