NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem2--正则表达 [rexp]

2: 正则表达 [rexp]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 15  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

为了解决形形色色的字符串匹配问题,正则表达式是一个强有力的工具。正则表达式通过定义一套符号体系,能够表示出需要查找的字符串所具有的性质。如“a|aa”能匹配 a 或 aa,“(a|b)c”能匹配 ac 或 bc。完整的正则表达式过于复杂,在这里我们只考虑由括号、“|”和“a”组成的正则表达式。

运算遵循下列法则:

(1) 有括号时,我们总是先算括号内的部分;

(2) 当两个字符串(或由括号定义的子串)间没有符号时,我们总把它们连起来作为一个整体;

(3) “|”是或连接符,表示两边的字符串任取其一,若同一层里有多个“|”,可以看作在这些“|”所分开的若干字符串里任取其一。

例如,(aaa)aa|aa|(a(aa)a)与(aaaaa)|(aa)|aaaa、aaaaa|aa|aaaa 都是等价的。它们都能匹配长度为 2、4 或 5 的全 a 字符串。给定一个简化正则表达式,试编程计算它最多能匹配多长的全 a 字符串。


Input

一行一个合法的简化正则表达式(保证“|”两端和括号内运算结果均非空字符串)。


Output

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


Sample Input Copy

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

Sample Output Copy

5

HINT

对于 20%的数据:表达式长度为不超过 100 的正整数,且不存在括号;

对于 40%的数据:表达式长度为不超过 100 的正整数;

对于 70%的数据:表达式长度为不超过 2000 的正整数;

对于 100%的数据:表达式长度为不超过 100000 的正整数。

Source/Category