[AHOI2017初中组] rexp

题目背景

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

题目描述

完整的正则表达式过于复杂,在这里我们只考虑由 `(`、`)`、`|` 和 `a` 组成的正则表达式。运算遵循下列法则: 1. 有括号时,我们总是先算括号内的部分; 2. 当两个字符串(或由括号定义的子串)间没有符号时,我们总把它们连起来作为一个整体; 3. `|` 是或连接符,表示两边的字符串任取其一,若同一层里有多个或连接符,可以看作在这些或连接符所分开的若干字符串里任取其一。 例如,`(aaa)aa|aa|(a(aa)a)`、`(aaaaa)|(aa)|aaaa` 和 `aaaaa|aaaa|aa` 是等价的,它们都能匹配长度为 $2,4$ 或 $5$ 的全 `a` 字符串。 下面给定一个简化正则表达式,试编程计算它最多能匹配多长的全 `a` 字符串。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

5

输入样例 #2

((a|aaa)|aa)|a

输出样例 #2

3

输入样例 #3

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

输出样例 #3

7

说明

**【数据范围】** 对于 $20\%$ 数据,表达式长度不超过 $100$,且不存在括号。 对于 $40\%$ 数据,表达式长度不超过 $100$。 对于 $70\%$ 数据,表达式长度不超过 $2 \times 10^3$。 对于 $100\%$ 的数据,表达式长度不超过 $10^5$。 保证表达式合法(即 `|` 两端和括号内运算结果均非空字符串)。