백준 1918 후위 표기식

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

#include <iostream>
#include <stack>

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s;
    string ans;


    cin >> s;

    stack<char> st;

    for (int i = 0; i < s.size(); i++) {
        if (isalpha(s[i])) {
            ans.push_back(s[i]);
        } else {
            if (s[i] == '(') {
                st.push(s[i]);
            } else if (s[i] == ')') {
                while (!st.empty() && st.top() != '(') {
                    ans.push_back(st.top());
                    st.pop();
                }
                st.pop();
            } else if (s[i] == '*' || s[i] == '/') {
                while (!st.empty() && (st.top() == '*' || st.top() == '/')) {
                    ans.push_back(st.top());
                    st.pop();
                }
                st.push(s[i]);
            } else if (s[i] == '+' || s[i] == '-') {
                while (!st.empty() && st.top() != '(') {
                    ans.push_back(st.top());
                    st.pop();
                }
                st.push(s[i]);
            }
        }
    }

    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }

    cout << ans;



    return 0;
}

1. 문제

중위 표기식이 주어진다. 이 때 이와 동일한 후위 표기식을 출력하라. 단, 식은 알파벳 대문자만이 첫 문자로 주어지며, 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있다.

 

2. 풀이

 주어진 대문자 외 수식 기호의 우선순위는 다음과 같다.

• (, )
• *, /
• +, -

위 식을 보면 기호가 나타날 때, 우선 순위가 높은 기호가 뒤에, 우선순위가 낮은 기호가 앞에 나오는 것을 볼 수 있다. 같은우선순위의 기호가 있을 경우 뒤 쪽에 나온 기호가 우선순위가 낮으므로 앞에 나와야 한다. 따라서 스택을 사용하여 이 문제를 풀 수 있다.

if (isalpha(s[i])) {
            ans.push_back(s[i]);
        }

우선 문자의 경우 그대로 정답 배열에 넣어준다.

if (s[i] == '(') {
    st.push(s[i]);
} else if (s[i] == ')') {
    while (!st.empty() && st.top() != '(') {
        ans.push_back(st.top());
        st.pop();
    }
    st.pop();
}

 가장 우선순위가 높은 괄호 기호를 보자. 괄호를 닫는 기호가 나올 경우 괄호를 여는 기호가 나올 때 까지 스택의 기호를 ans에 추가하고 pop한다. 괄호가 가장 높은 우선순위이므로 괄호 안의 기호는 이 시점에서 모두 적혀야 한다.

else if (s[i] == '*' || s[i] == '/') {
    while (!st.empty() && (st.top() == '*' || st.top() == '/')) {
        ans.push_back(st.top());
        st.pop();
    }
    st.push(s[i]);
} else if (s[i] == '+' || s[i] == '-') {
    while (!st.empty() && st.top() != '(') {
        ans.push_back(st.top());
        st.pop();
    }
    st.push(s[i]);
}

 같은 이유로 해당 기호가 나올 경우 기호의 우선순위에 맞춰 ans를 작성하고 스택에서 pop한다. +, -는 가장 낮은 우선순위이므로 다음 (가 나와서 우선순위가 막힐 때 까지만 pop 한다.

while (!st.empty()) {
    ans.push_back(st.top());
    st.pop();
}

 연산이 끝나고 스택에 남은 기호를 ans에 추가하고 이를 출력하면 정답을 구할 수 있다.