2959. 正则表达式简化版

在程序设计中，正则表达式 (Regular Expressions) 是用来处理复杂的字符串匹配以及模式识别问题的利器。正则表达式的一种常见用法是，给定一个正则表达式和一个字符串，然后询问给定的正则表达式能否匹配整个字符串，你需要处理的就是这种询问。

当然，编写一个优秀的正则表达式引擎是有难度的，在这道题目中，你需要编程处理一种经过高度简化的正则表达式。以下是这种正则表达式简化版的定义。

简化版的正则表达式可能包含以下字符：0~9 的数字，A~Z 以及 a~z 的大小写英文字母，下划线 “_”，方括号 “[” 和 “]”，花括号 “{” 和 “}”，短横线 “-”。其中，方括号和花括号一定以成对的方式出现且不会存在任何嵌套；短横线一定出现在方括号内，且短横线两边的字符或者同为数字，或者同为小写字母，或者同为大写字母，且短横线前面的字符的 ASCII 码不大于后面的字符；花括号内只会出现数字。下面将数字、英文字母和下划线统称为 “ 普通字符 ”。

出现在括号外的普通字符即表示与字符串中同样的单个字符匹配，例如正则表达式 “dd” 可匹配字符串 “dd”，但不能匹配 “Dd”（因为大小写敏感），也不能匹配 “dd_”（正则表达式中不存在与最后的 “_” 匹配的元素）。

成对的方括号以及之间的部分也匹配字符串中的单个字符，但可以匹配的单个字符是一个集合，这个集合包含方括号中间的普通字符。例如正则表达式 “[Dd]d_engi” 既能匹配 “Dd_engi” 又能匹配 “dd_engi”；正则表达式 “[AaB][aAb]” 可匹配 “Ab”“aA”“Ba” 等，但不能匹配 “AB”“bA” 或 “bB”；正则表达式 “13[56789]” 可匹配 “135”“136”“137”“138”“139” 中的任何一个，且不能匹配其它字符串。

成对的方括号间，除了普通字符外，也可能出现短横线 “-”，表示与连续的一段字符匹配。例如，“[A-Z]” 可匹配任何单个大写字符构成的字符串，如 “E”“N”“G”“I” 等；“[0-9]” 可匹配任何单个数字构成的字符串；“[2-4A-Z]” 可匹配 2~4 的数字或者大写字母，但不能匹配 “1”“5” 或者 “a”；正则表达式 “13[5-9]”、“13[85-79]”、“13[956-8]”、“13[5-78-9]”、“13[56789]”“13[98765]”“13[567898765]”“13[5-56-67-78-89-9]” 互相之间都是等价的，都表示可匹配 “135”“136”“137”“138”“139” 中的任何一个，且不能匹配其它字符串。

成对的花括号内含一个整数，表示 “ 前一元素的标准应重复匹配若干次 ”。例如，“D{2}” 表示将字符 D 重复两次，匹配字符串 “DD”；正则表达式 “D{1}” 与 “D” 等价；“D{11}” 与 “DDDDDDDDDDD” 等价；“[Dd]{2}” 可匹配 “dd”“dD”“Dd”“DD” 四种字符串；“dd_[eng]{3}i” 可匹配 “dd_engi”“dd_eeei”“dd_enni”“dd_eeni”“dd_gnei” 等。成对的花括号的前面或者是普通字符或者是成对的方括号，不可能是另一对花括号。正则表达式 “1[35][0-9]{8}” 的意义是 “ 第一位是 1，第二位可以是 3 或 5，后面有 8 个 0~9 的数字 ”，它可以用来匹配中国大陆的手机号码。

【题目包含多组输入输出！】