알고리즘
- 괄호치기
- / 는 앞에서부터 가까운 두 괄호를 묶음.
- 그다음 + - 로 마찬가지로 함.
- 양쪽에 모두 없으면 패스함
- 출력
- 여는괄호, 연산자는 스택에 넣기.
- 닫는 괄호가 나오면 여는괄호가 나올때까지 쭉 빼기.
- 알파벳은 그냥 출력.
코드
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
68
69
70
71
72
73
74
#include <iostream>
#include <string>
#include <stack>
using namespace std;
string first;
char result[101];
int resultl;
stack<char> s;
void bind(char a, char b);
int main() {
cin >> first;
bind('*', '/');
bind('+', '-');
for (int i = 0; i < first.size(); i++) {
if (first[i] == '(' || first[i] == '*' || first[i] == '+' || first[i] == '-' || first[i] == '/')
s.push(first[i]);
else if (first[i] == ')') {
while (s.top() != '(') {
cout << s.top();
s.pop();
}
s.pop();
}
else
cout << first[i];
}
}
void bind(char a, char b) {
for (int i = 0; i < first.size(); i++) {
int lput = -200, rput = -200, length = first.size(), lc = 0, rc = 0;
if (first[i] == a || first[i] == b) {
for (int j = i - 1; j >= 0; j--) {
if (first[j] == ')')
lc++;
else if (first[j] == '(' && lc > 0)
lc--;
if (lc == 0 && (first[j] == '(' || (first[j] >= 'A' && first[j] <= 'Z'))) {
lput = j - 1;
break;
}
}
for (int j = i + 1; j < length; j++) {
if (first[j] == '(')
rc++;
else if (first[j] == ')' && rc > 0)
rc--;
if (rc == 0 && (first[j] == ')' || (first[j] >= 'A' && first[j] <= 'Z'))) {
rput = j + 1;
break;
}
}
if (lput == -200 || rput == -200)
continue;
if (lput < 0)
first = "(" + first;
else
first = first.substr(0, lput + 1) + "(" + first.substr(lput + 1, length);
if (rput == length)
first = first + ")";
else
first = first.substr(0, rput + 1) + ")" + first.substr(rput + 1, first.size());
i++;
}
}
}