2.3.蓝桥杯-正则问题
题目描述
考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是 6。
输入描述
一个由 x()| 组成的正则表达式。输入长度不超过 100，保证合法。
输出描述
这个正则表达式能接受的最长字符串的长度。
输入输出样例
示例
输入
((xx|xxx)x|(x|xx))xx输出
6运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
参考代码：
package Practice2; import java.util.Scanner; public class Main { /*定义全局变量记录正则表达式，之所以要定义成全局变量，是为了递归调用， * 如果是局部变量，那么处理正则表达式的函数的形参就需要是正则表达式， * 每一次递归都需要重新把整个正则表达式进行处理，不符合需求*/ static String str = null; /*定义索引记录处理到正则表达式哪一个字符*/ static int index = -1; //初值为-1，表示一开始没有字符 public static void main(String[] args) { /*题目中正则表达式由字符x、(、)、|构成*/ /*1.输入正则表达式*/ Scanner sc = new Scanner(System.in); str = sc.next(); /*2.调用method方法得出正则表达式能接受的最长字符串的长度*/ int result = method(); /*3.输出结果*/ System.out.println(result); } //用来统计正则表达式能接受的最长字符串的长度的方法 private static int method() { /*1.记录目前x的最大个数*/ int current = 0; /*2.记录最终x的最大个数*/ int max = 0; /*3.循环处理正则表达式*/ while (index < str.length() - 1) { //这里之所以用index < str.length()-1，是防止越界。因为如果是index < str.length()，当index等于str.length()-1时，index++就越界了 index++; //注：要处理的是字符 if (str.charAt(index) == 'x') { /*3.1.处理x时只需要个数自增*/ current++; } else if (str.charAt(index) == '(') { /*3.2.遇到(时需要递归调用，因为(中有一个新的子表达式，这个子表达式需要独立计算， 计算完成后，结果要返回给外层表达式*/ current = current + method(); } else if (str.charAt(index) == ')') { /*3.3.遇到)时意味着括号处理完毕，结束本轮循环*/ break; } else if (str.charAt(index) == '|') { /*3.2.遇到|时就需要判断|左、右两侧谁的正则长度大*/ max = Math.max(current, max); //关键：此时current就需要清0，current的之前值被max记录，新的值重新计算 current = 0; } } /*4.返回正则表达式最大长度*/ return Math.max(current, max); } }