括号画家

Candela 是一名漫画家，她有一个奇特的爱好，就是在纸上画括号。

这一天，刚刚起床的 Candela 画了一排括号序列，其中包含小括号 ()、中括号 [] 和大括号 {}，总长度为 N。

这排随意绘制的括号序列显得杂乱无章，于是 Candela 定义了什么样的括号序列是美观的。

1
2
3
1.空的括号序列是美观的；
2.若括号序列 A 是美观的，则括号序列 (A)、[A]、{A} 也是美观的；
3.若括号序列 A、B 都是美观的，则括号序列 AB 也是美观的；

例如 [(){}]() 是美观的括号序列，而 )({)[}]( 则不是。

现在 Candela 想在她绘制的括号序列中找出其中连续的一段，满足这段子序列是美观的并且长度尽量大。你能帮帮她吗？

输入：

1 个长度为 N 的括号序列。(5 ≤ N ≤ 10000)

输出：

一个整数，表示最长的美观的连续子序列的长度。

样例：

1
[[[[]]{}]]
1
10

代码

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
#include<iostream>
#include<stack>
#include<string>
using namespace std;

stack<char> stack1;
stack<int> 	stack2;
string str;
int ans;

void ansUpdate(int i) {
	stack1.pop();
	stack2.pop();
	ans = max(ans, i - stack2.top());
}

void stack12Clear(int i) {
	while (!stack1.empty()) {
		stack1.pop();
		stack2.pop();
	}
	stack1.push('#');
	stack2.push(i);
}

int main() {
	cin >> str;
	stack1.push('#');
	stack2.push(-1);
	for (int i = 0; i < str.length(); ++i) {
		switch (str[i]) {
		case '(':
		case '[':
		case '{':
			stack1.push(str[i]);
			stack2.push(i);
			break;
		case ')':
			if (stack1.top() == '(') ansUpdate(i);
			else stack12Clear(i);
			break;
		case '}':
			if (stack1.top() == '{') ansUpdate(i);
			else stack12Clear(i);
			break;
		case ']':
			if (stack1.top() == '[') ansUpdate(i);
			else stack12Clear(i);
			break;
		}
	}
	cout << ans << endl;
	return 0;
}