백준 1918 후위 표기식

작성일 | In |

Problem : 후위 표기식

유형 : 스택

문제 해석

  • 주어진 중위 표기식을 후위 표기식으로 변경하여라.

문제 재해석

  • ( , ) 와 같은 괄호 처리를 고려한다.

해결 전략

  • 스택을 이용하여, 순서를 고려하여 구현한다.
  • 스택에 들어가는것이, 현재 스택에서 최상위 우선순위가 될때까지 pop을 진행한다.
  • 즉 스택에 있는 연산자의 우선순위가 같거나 크다면 pop 한다.

설계, 구현

  • 스택 자료구조를 이용한다.
  • 숫자 인경우, 그냥 출력한다.

숫자가 아닌 경우

  • 괄호 인지를 확인한다.
    • ( 의 경우, 항상 연산자 순위를 최하위로 결정한다.
    • 항상 스택에 push한다.
    • ) 의 경우, ( 를 만날때까지 pop 한다.
  • 연산자인 경우, 우선순위에 맞춰 push pop 을 진행한다.
    • + , - 인 경우, ( 를 제외한다면 최하위 우선순위이다.
    • % , * 인 경우, 본인들과 동일한것들을 pop 한다.

주의할 점

  • 항상 스택의 empty 상태를 확인하기.

코드

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 <bits/stdc++.h>
using namespace std;

string st, answer;
stack<char> s;

void Oper_Func(const char &oper) {
    if (oper == '*' or oper == '/') {
        while (!s.empty() and (s.top() == '*' or s.top() == '/')) {
            answer += s.top();
            s.pop();
        }
        s.push(oper);
    }

    else if (oper == '+' or oper == '-') {
        while (!s.empty() and s.top() != '(') {
            answer += s.top();
            s.pop();
        }
        s.push(oper);
    }
}

void Bracket_Func(const char& bracket) {
    if (bracket == '(') s.push('(');
    else {
        while (!s.empty()) {
            char cur = s.top(); s.pop();
            if (cur == '(') break;
            answer += cur;
        }
    }
}

void Solve() {
    for (const char &ch : st) {
        if (isalpha(ch)) answer += ch;
        else {
            if (ch == '(' or ch == ')') Bracket_Func(ch);
            else Oper_Func(ch);
        }
    }

    while (!s.empty()) {
        answer += s.top();
        s.pop();
    }

    cout << answer << "\n";
}

void Input() {
    cin >> st;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • 구현 속도를 좀더 올려야 할 것 같다.