問題 1887: [藍(lán)橋杯][2017年第八屆真題]正則問題

題目描述

考慮一種簡(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)度不超過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 正則問題 {

    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;
    }

}