문제
풀이
Stack을 활용하여 풀 수 있는 문제이다.
알고리즘
- 피연산자 A~Z는 무조건 출력해준다.
- 연산자일 경우 아래의 3가지 경우가 있다.
- ( 의 경우 스택에 바로 넣어준다.
- +, -, * , / 일 경우 stack의 top에 현재 연산자보다 우선순위가 낮지 않을 경우 stack의 top을 출력하고 pop해준다. (+, - 보다 *, /의 우선순위가 높다. )
- ) 가 나오면 스택에서 ( 가 나올 때 까지 출력하며 pop해준다.
- 반복문을 다 돌고난 후 스택이 비어있지 않을 경우가 있으므로, 스택이 빌 때까지 pop하며 출력해준다.
핵심 : 스택은 우선 순위가 낮은 연산자 (+, -) 부터 큰 연산자 (*, /) 순으로 쌓여야 한다.
Example
A + (B * C) - (D / E)의 경우를 보자.
- 2번에서 )가 나왔으므로 스택에서 (가 나올때까지 출력하며 pop해준다.
- 3번에서 - 연산자가 + 연산자보다 우선순위가 높지 않으므로 +를 출력하고 pop 해주고, -를 스택에 넣어준다.
- 5번 역시 (가 나올때까지 출력하며 pop한다.
- 6번에서 반복문이 다 돌고난 뒤에도 스택에 요소가 남아있으므로 스택이 빌 때 까지 모두 출력해준다.
소스 코드
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
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
stack<char> op;
cin >> s;
for (int i = 0; i < s.length(); i++)
{
if (s[i] >= 'A' && s[i] <= 'Z')
{
cout << s[i];
}
else
{
if (s[i] == '(')
op.push(s[i]);
else if (s[i] == '*' || s[i] == '/')
{
while (!op.empty() && (op.top() == '*' || op.top() == '/'))
{
cout << op.top();
op.pop();
}
op.push(s[i]);
}
else if (s[i] == '+' || s[i] == '-')
{
while (!op.empty() && op.top() != '(')
{
cout << op.top();
op.pop();
}
op.push(s[i]);
}
else if (s[i] == ')')
{
while (!op.empty() && op.top() != '(')
{
cout << op.top();
op.pop();
}
op.pop();
}
}
}
while (!op.empty())
{
cout << op.top();
op.pop();
}
return 0;
}
