문제

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

  • 알파벳 대문자로 이루어진 피연산자는 한 번씩만 등장
  • -가 가장 앞에 오거나 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+이 되어야 하기 때문
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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의 순서를 보장해야 하고 괄호가 추가되어 좀 더 구현 문제에 가까운 것 같다.

Leave a comment