[AHOI2017初中组] rexp

题目背景

为了解决形形色色的字符串匹配问题，正则表达式是一个强有力的工具。正则表达式通过定义一套符号体系，能够表示出需要查找的字符串所具有的性质。如 a|aa 能匹配 a 或 aa，(a|b)c 能匹配 ac 或 bc。

题目描述

完整的正则表达式过于复杂，在这里我们只考虑由 (、)、| 和 a 组成的正则表达式。运算遵循下列法则：

有括号时，我们总是先算括号内的部分；
当两个字符串（或由括号定义的子串）间没有符号时，我们总把它们连起来作为一个整体；
| 是或连接符，表示两边的字符串任取其一，若同一层里有多个或连接符，可以看作在这些或连接符所分开的若干字符串里任取其一。

下面给定一个简化正则表达式，试编程计算它最多能匹配多长的全 a 字符串。

输入格式

输入一行一个合法的简化正则表达式。

输出格式

一行一个整数，表示能匹配的最长全 a 字符串长度。

样例 #1

样例输入 #1

(aaa)aa|aa|(a(aa)a)

样例输出 #1

样例 #2

样例输入 #2

((a|aaa)|aa)|a

样例输出 #2

样例 #3

样例输入 #3

(a(aa|aaa)a|(a|aa))aa

样例输出 #3

提示

【数据范围】

对于 $20%$ 数据，表达式长度不超过 $100$，且不存在括号。

对于 $40%$ 数据，表达式长度不超过 $100$。

对于 $70%$ 数据，表达式长度不超过 $2 \times 10^3$。

对于 $100%$ 的数据，表达式长度不超过 $10^5$。

保证表达式合法（即 | 两端和括号内运算结果均非空字符串）。

这道题明明因该评个红题，但给了个绿题，真的很奇怪。

递归找答案就行了。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int read()
{
	int res = 0; // 答案
	char ch;
	while (cin >> ch)
	{
		if (ch == 'a') ++ res; // 如果是 a 那么 ++ res
		if (ch == '(') res += read(); // 如果有前括号，那么开始新的递归
		if (ch == ')') return res; // 如果有后括号，那么递归结束
		if (ch == '|') return max(res, read()); // 求 max
	}
	return res; // 最终答案
}

int main()
{
	cout << read();
	return 0;
}

~~实在不会画个图也行~~