真题解析│蓝桥杯省赛真题之正则问题
-
-
梁老师 北京小升初老师～
0 人点赞了该文章 · 51 浏览
2017年蓝桥杯软件类省赛C++语言大学A组第7题“正则问题”。
题目描述
题目链接：正则问题
http://oj.ecustacm.cn/problem.php?id=1321
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是：xxxxxx，长度是6
解释
题解
倪文迪的话：“这道题用递归的思路来做，代码还是相当简洁的。遇到左括号’(‘就去递归求解，遇到右括号’)‘则当前递归结束并返回结果；遇到’|‘则记录并重置当前的值，再向右计算更新；如果是x的话直接统计即可。”
罗勇军老师的话：本题是练习DFS（递归）和栈的好题目。
题目的主体是括号匹配，这是经典的递归、栈的应用。
（1）一个左括号必然有一个右括号匹配。读者可以尝试生成各种各样的嵌套括号，方法是：从第1对括号“()”开始；把第2对括号的左括号和右括号分别随机插入到第1对括号的任意位置，例如“(())”；把第3对括号随机插入，例如“(()())”，等等。只要括号是成对插入的，得到的括号串都是合法的。
（2）用栈检查括号的合法性。每遇到一个左括号’(’，就进栈，每遇到一个右括号’)’，就完成了一次匹配，出栈。读者可以用一个嵌套括号来练习练习。
（3）编码。可以直接用栈编码，也可以用DFS（递归）编码，更简单一点。（参考这篇博文，它介绍了栈、队列、堆等，并给出了各种代码实现：简单数据结构）
本题的字符串除了括号，还有’|‘和’x’。’|'和’x’的处理和括号的递归处理有关，这使得代码的逻辑有点复杂。请尝试自己编码，然后对照下面的代码。
下面给出了C++、Java、Python代码。Python确实很慢。
C++代码
#include<bits/stdc++.h>
using namespace std;
string s;
int pos = 0; //当前的位置
int dfs(){
int tmp = 0, ans = 0;
int len = s.size();
while(pos < len){
if(s[pos] == '('){ //左括号，继续递归。相当于进栈
pos++;
tmp += dfs();
}else if(s[pos] == ')'){ //右括号，递归返回。相等于出栈
pos++;
break;
}else if(s[pos] == '|'){ //检查或
pos++;
ans = max(ans, tmp);
tmp = 0;
}else{ //检查X，并统计X的个数
pos++;
tmp++;
}
}
ans = max(ans, tmp);
return ans;
}
int main(){
cin >> s;
cout << dfs() << endl;
return 0;
}Java代码
//User: 1240276522
import java.util.Scanner;
public class Main {
static String s;
static int pos;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
s = sc.nextLine();
System.out.println(dfs());
}
public static int dfs() {
int ans = 0;
int temp = 0;
int len = s.length();
while (pos < len) {
if(s.charAt(pos) == '(') {
pos++;
temp += dfs();
} else if(s.charAt(pos) == 'x') {
temp++;
pos++;
}else if(s.charAt(pos) == '|') {
ans = Math.max(ans,temp);
temp = 0;
pos++;
} else if(s.charAt(pos) == ')') {
pos++;
return Math.max(temp,ans);
}
}
return Math.max(ans,temp);
}
}Python代码
s = input()
count, pos, length = 0, 0, len(s)
def dfs():
global length, pos
temp, ans = 0, 0
while pos < length:
if s[pos] == '(':
pos += 1
temp += dfs()
elif s[pos] == 'x':
pos += 1
temp += 1
elif s[pos] == '|':
pos += 1
ans = max(ans, temp)
temp = 0
elif s[pos] == ')':
pos += 1
ans = max(ans, temp)
return ans
ans = max(ans, temp)
return ans
ans = dfs()
print(ans)
添加 家长论坛微信
全部 0条评论