BOJ 1918 - 후위 표기식
문제
아래와 같은 조건을 만족하는 중위 표기식이 주어질 때 후위 표기식으로 변환하는 문제이다.
- 알파벳 대문자로 이루어진 피연산자는 한 번씩만 등장
-
가 가장 앞에 오거나AB
와 같이*
가 생략되는 수식은 주어지지 않음- 표기식은 알파벳 대문자,
+
,-
,*
,/
,(
,)
로만 이루어지고, 길이는 100이하임
풀이
연산자의 우선순위를 아래와 같이 설정한다.
*
,/
: 1+
,-
: 2(
: 3
중위 표기식을 읽으면서 알파벳은 변환된 후위 표기식 문자열 ans
에 바로 추가한다.
연산자일 경우 아래 조건에 따라 연산자를 저장하는 스택 st
로 처리한다.
st
가 비어있거나 top이(
일 경우 현재 연산자 push- 현재 연산자가
)
일 경우(
가 나올 때까지st
의 top pop - 현재 연산자가
st
의 top보다 우선 순위가 높을 경우(숫자가 낮을 경우) 현재 연산자 push - 현재 연산자가
st
의 top과 우선 순위가 같을 경우st
의 top을ans
에 넣고 pop, 현재 연산자를 pushA*B*C
와 같이 우선 순위가 동일할 경우AB*C*
와 같이 계산 순서가 보장되어야 함
- 현재 연산자가
st
의 top보다 우선 순위가 낮을 경우st
의 top보다 우선 순위가 높아질 때까지 top pop 이후 현재 연산자 pushA+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