問(wèn)題 1887: [藍(lán)橋杯][2017年第八屆真題]正則問(wèn)題
題目描述
考慮一種簡(jiǎn)單的正則表達(dá)式：
只由 x ( ) | 組成的正則表達(dá)式驮瞧。
小明想求出這個(gè)正則表達(dá)式能接受的最長(zhǎng)字符串的長(zhǎng)度澜薄。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最長(zhǎng)字符串是： xxxxxx砚婆，長(zhǎng)度是6贫悄。
輸入
一個(gè)由x()|組成的正則表達(dá)式次询。輸入長(zhǎng)度不超過(guò)100彰檬，保證合法奏司。
輸出
這個(gè)正則表達(dá)式能接受的最長(zhǎng)字符串的長(zhǎng)度乔询。
樣例輸入
((xx|xxx)x|(x|xx))xx
樣例輸出
6
( (xx|xxx) x | (x|xx) ) xx 能接受的最長(zhǎng)字符串是： xxxxxx，長(zhǎng)度是6韵洋。
((2|3)1|(1|2))2
2|3
( 進(jìn)
遇到x ++
遇到|判斷
遇到）后面的x +
遇到| 再判斷
dfs方法：
package 字符串;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* User: 76147
* Date: 2020-01-29
* Time: 19:32
* Description:
*/
public class 正則問(wèn)題 {
private static int p;
private static char a[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.next();
a = str.toCharArray();
int res = dfs();
System.out.println(res);
}
}
private static int dfs() {
int ans = 0;
int result = 0;
int len = a.length;
while (p < len) {
if (a[p] == 'x') {
p++;
ans++;
} else if (a[p] == '(') {
p++;
ans = ans + dfs();
} else if (a[p] == ')') {
p++;
break;
} else {
p++;
result = Math.max(result, ans);
ans = 0;
}
}
result = Math.max(result, ans);
return result;
}
}
