例如题目中由“x”“()”“|”组成的正则表达式,括号“()”的优先级最高,或操作“|”次之。括号里面是一个整体,操作的两边保留更长的那个。
题目描述中的((xx|xxx)x|(x|xx))xx是怎么执行的?为什么它能接受的最长字符串长度是6?
先执行括号,再执行或操作,步骤如下。
(1)先看第一个括号,发现里面还嵌套了括号,找到最内部的括号,括号内是一个或操作。((xx|xxx)x|(x|xx))xx,得:(xxxx|(x|xx))xx。
(2)执行最内部的括号。(xxxx|(x|xx))xx,得:(xxxx|xx)xx。
(3)执行最后的括号。(xxxx|xx)xx,得:xxxxxx。结束,得到长度为6的字符串。
本题是练习DFS(递归)和栈的好题目。
题目的主体是括号匹配,这是经典的递归、栈的应用。
(1)一个左括号必然与一个右括号匹配。可以尝试生成各种各样的嵌套括号,方法是:从第1对括号“()”开始;把第2对括号的左括号和右括号分别随机插入第1对括号中的任意位置,例如“(())”;再把第3对括号随机插入,例如“(()())”,等等。只要括号是成对插入的,得到的括号串就都是合法的。
(2)用栈检查括号的合法性。每遇到一个左括号“(”,就入栈,每遇到一个右括号“)”,就完成一次匹配,出栈。读者可以用一个嵌套括号来练习一下。
(3)编程。可以直接用栈编程,也可以用DFS(递归)编程,后者更简单。
代码如下:
include[HTML_REMOVED]
using namespace std;
string s;
int pos = 0;
int dfs(){
int tmp = 0,ans = 0;
int len = s.size();
while(pos[HTML_REMOVED]> s;
cout << dfs();
return 0;
}