Java实现第八届蓝桥杯正则问题

正则问题

考虑一种简单的正则表达式：

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入

一个由x()|组成的正则表达式。输入长度不超过100，保证合法。

输出

这个正则表达式能接受的最长字符串的长度。

例如，

输入：

((xx|xxx)x|(x|xx))xx

程序应该输出：

6

资源约定：

峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

不要使用package语句。不要使用jdk1.7及以上版本的特性。

主类的名字必须是：Main，否则按无效代码处理。

PS：

本题栈的基础应用思路很简单 ‘（’ ‘x’ ‘|’ 入栈碰见‘）’然后出栈

出栈的时候把他们连一起然后用‘|’进行切割模拟或运算

留下最长的那个字符串入栈最后所有的东西都出栈

在进行上面的操作不过本题比较坑括号有不是成对的吐槽一下什么破语法

`第二个有点问题，错误的我建议也看看，省的下次犯`

import java.util.Scanner;

public class 正则问题 {

	static int count;

	static char[] a = new char[200];

	static int p;

	static int max =-1;;

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		a = in.next().toCharArray();

		dfs();

		System.out.println(max);

	}

	static int dfs() {

		int xnum = 0;

		int maxx = 0;

		while (p < a.length) {

			max=Math.max(xnum, max);

			max=Math.max(maxx, max);

			if (a[p] == 'x') {

				p++;

				xnum++;

			} else if (a[p] == '(') {

				p++;

				xnum += dfs();

			} else if (a[p] == ')') {

				p++;

				break;

			} else if (a[p] == '|') {

				p++;

				maxx=Math.max(xnum, maxx);

//				max=Math.max(maxx, max);

				//maxx = Math.max(xnum, maxx);

				xnum = 0;

			}

			max=Math.max(xnum, max);

//			max=Math.max(maxx, max);

		}

		return Math.max(xnum, maxx);

	}

}

import java.io.File;

import java.io.FileNotFoundException;

import java.text.ParseException;

import java.util.Scanner;

/**

 * 采用DFS，从前到后遍历遇到(就开始新的搜索，遇到)则停止搜索并通过比较，找出这个括号里的最大值；

 * 如果遇到|，则需要记录之前的长度，用于在之后)的比较。遇到x，长度加一，且继续往下找

 *

  每一个（）都是一次dfs，可返回期间最大x数量

 */

public class 编程7正则问题 {

	// static Scanner in = new Scanner(System.in);

	static int count;

	static char[] a = new char[200];

	static int p;

	public static void main(String[] args) throws ParseException, FileNotFoundException {

		Scanner in = new Scanner(new File("src/JavaA/s8/7.txt"));

		a = in.next().toCharArray();

		System.out.println(dfs());

	}

	static int dfs() {

		int xnum = 0;

		int maxx = 0;

		while (p < a.length) {

			if (a[p] == 'x') {

				p++;

				xnum++;

			} else if (a[p] == '(') {

				p++;

				xnum += dfs();

			} else if (a[p] == ')') {

				p++;

				break;

			} else if (a[p] == '|') {

				p++;

				maxx=xnum;

				//maxx = Math.max(xnum, maxx);

				xnum = 0;

			}

		}

		return Math.max(xnum, maxx);

	}

}

巴特西

Java实现第八届蓝桥杯正则问题

输入

输出

`第二个有点问题，错误的我建议也看看，省的下次犯`

最新文章

热门文章