AT_ttpc2015_p.Dancing stars on regular expression!

在这里，我们称以下结构的字符串为“正则表达式”：

$ e $ ::= $ a...a $ | ($ e_1 $+$ e_2 $) | ($ e_1 $;$ e_2 ) | \*( e_1 $) | !($ e_1 $)

其中，$ a...a $ 表示由字符 $ a $ 连续重复一次或多次构成的字符串。

正则表达式 $ e $ 所代表的字符串集合 $ L(e) $ 可以通过下面的规则递归定义：

1. $ L(a...a)\ =\ {a...a} $，如 $ L(aa)\ =\ {aa} $, $ L(aaa)\ =\ {aaa} $。
2. $ L((e_1+e_2))\ =\ L(e_1)\ ∪\ L(e_2) $ 是 $ L(e_1) $ 和 $ L(e_2) $ 中任一集合中元素的合集。
3. $ L((e_1;e_2))\ =\ L(e_1)L(e_2) $，即 $ L(e_1) $ 中的字符串与 $ L(e_2) $ 中的字符串组合而成的所有字符串形成的集合。
4. $ L(*(e_1)) $ 表示 $ L(e_1) $ 中字符串的任意次数（包括零次）连接。
5. $ L(!(e_1))\ =\ Σ^*\ -\ L(e_1) $，即从所有可能字符串中除去 $ L(e_1) $ 的集合。

这里，$ Σ^* $ 是所有可能字符串的集合，形如 $ {ε,a,aa,aaa,\ldots} $，由 $ a $ 字符有限次重复组成。

另外，无 ! 正则表达式表示不包含 ! 操作符的表达式，而无 * 正则表达式表示不包含 * 操作符的表达式。

现在给你一个无 ! 的正则表达式 $ S $，请判断是否存在一个无 * 的正则表达式 $ T $，使得 $ L(S) = L(T) $。

输入为以下格式：

• 第一行是一个整数 $ N $ ($ 1 \leq N \leq 4000 $)，表示第二行输入的字符串 $ S $ 的长度。
• 第二行是一个无 ! 正则表达式的字符串 $ S $。

如果存在一个无 * 的正则表达式 $ T $ 满足 $ L(S) = L(T) $，输出 YES；否则，输出 NO。

数据范围与提示

• 示例 1：可以选择 $ T = (a+aa) $ 作为答案。
• 示例 2：可以选择 $ T = (!(a)+a) $ 作为答案。
• 示例 3：不存在符合 $ L(S) = L(T) $ 的无 * 正则表达式 $ T $。

本翻译由 AI 自动生成