-
Notifications
You must be signed in to change notification settings - Fork 1
/
괄호 변환.cpp
100 lines (85 loc) · 1.85 KB
/
괄호 변환.cpp
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 괄호 변환 (분할정복)
// https://programmers.co.kr/learn/courses/30/lessons/60058
// 시행착오
// string cut = u.substr(1, u.size() - 2); 에서 u.size를 str.size로 잘못 작성함
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <bitset>
#include <functional>
#include <sstream>
using namespace std;
const char Open = '(';
const char Close = ')';
void Divide(string str, bool open, string& u, string& v)
{
stack<char> st;
char check_top = open ? Open : Close;
int i = 0;
st.push(str[i++]);
while (!st.empty())
{
char top = st.top();
if (top == check_top)
{
if (str[i] == check_top)
{
st.push(top);
}
else
{
st.pop();
}
}
i++;
}
u = str.substr(0, i);
v = str.substr(i, str.size() - i);
//cout << "u : " << u << " v : " << v << endl << endl;
}
string solution(string str)
{
string u, v;
if (str == "")
return "";
if (str[0] == Open)
{
Divide(str, true, u, v);
return u + solution(v);
}
else
{
Divide(str, false, u, v);
string temp = Open + solution(v) + Close;
string cut = u.substr(1, u.size() - 2);
for (int j = 0; j < cut.size(); ++j)
{
if (cut[j] == Open)
{
cut[j] = Close;
}
else
{
cut[j] = Open;
}
}
return temp + cut;
}
}
int main()
{
//string p = ")(";
//string p = "(()())()";
string p = "()))((()";
string answer = solution(p);
cout << answer;
return 0;
}