10

对于给定的输入字符串和给定的模式 K，我想从字符串中提取每次出现的 K（或其中的一部分（使用组））并检查整个字符串是否匹配K*（因为它由 0 个或多个 K 组成没有其他字符）。

但我想使用正则表达式一次性完成。更具体地说，我目前正在使用 寻找模式Matcher.find，但这不是严格要求的。

我该怎么做？

我已经找到了一个解决方案（并发布了一个答案），但想知道是否有特定的正则表达式或Matcher功能可以解决/可以解决这个问题，或者只是有更好/不同的方法来解决这个问题。但是，即使不是，我仍然认为这是一个有趣的问题。

例子：

图案：（<[0-9]>中的单个数字<>）

有效输入：<1><2><3>

无效输入：

<1><2>a<3>
<1><2>3
Oh look, a flying monkey!
<1><2><3

在 2 遍中执行此操作的代码matches：

boolean products(String products)
{
    String regex = "(<[0-9]>)";
    Pattern pAll = Pattern.compile(regex + "*");

    if (!pAll.matcher(products).matches())
        return false;

    Pattern p = Pattern.compile(regex);
    Matcher matcher = p.matcher(products);

    while (matcher.find())
        System.out.println(matcher.group());

    return true;
}
4

4 回答 4

7

1. 定义问​​题

由于不清楚当整个字符串与 pattern 不匹配时输出什么K*，我将重新定义问题以明确在这种情况下输出什么。

给定任何模式 K：

  • 检查字符串是否具有模式K*。
  • 如果字符串具有模式K*，则将字符串拆分为匹配的非重叠标记K。
  • 如果字符串只有与 pattern 匹配K*的前缀，则选择K*+1选择的前缀，并将前缀拆分为与 K 匹配的标记。

1不知道有没有办法得到最长的匹配K的前缀。当然，你总是可以一个一个的去掉最后一个字符，测试K*直到匹配，但显然效率低下。

除非另有说明，否则我在下面写的任何内容都将遵循我上面的问题描述。请注意，问题的第三个要点是解决要采用哪个前缀字符串的歧义。

2. .NET中的重复捕获组

如果我们有解决问题的方法，就可以解决上述问题：

给定一个模式(K)*，它是一个重复的捕获组，获取所有重复的捕获文本，而不仅仅是最后一个重复。

  • 在字符串有pattern的情况下K*，通过匹配^(K)*$，我们可以得到所有匹配pattern的token K。
  • 在字符串只有前缀匹配的情况下K*，通过匹配^(K)*，我们可以得到所有匹配模式的标记K。

在 .NET 正则表达式中就是这种情况，因为它为重复的捕获组保留所有捕获的文本。

但是，由于我们使用的是 Java，因此我们无法访问此类功能。

3. Java中的解决方案

检查字符串是否具有模式K*始终可以使用Matcher.matches()/来完成String.matches()，因为引擎将对输入字符串进行全面回溯，以某种方式K*与输入字符串“统一”。困难的事情是将输入字符串拆分为与 pattern 匹配的标记K。

如果K*相当于K*+

如果模式 K 具有以下性质：

对于所有字符串2，K*等价于K*+，即如何将输入字符串拆分为匹配模式K相同的标记。

2您可以仅为您正在操作的输入字符串定义此条件，但确保此前提条件并不容易。当你为所有字符串定义它时，你只需要分析你的正则表达式来检查条件是否成立。

然后可以构造解决问题的一次性解决方案。Matcher.find()您可以在 pattern 上重复使用\GK，并检查找到的最后一个匹配项是否位于字符串的末尾。这类似于您当前的解决方案，除了您使用代码进行边界检查。

in中的量词+后使量词具有所有格。占有量词将阻止引擎回溯，这意味着每次重复始终是模式 K 的第一个可能匹配项。我们需要此属性以便解决方案具有等效含义，因为它还将返回模式 K 的第一个可能匹配项。*K*+\GK

如果K*不等于K*+

如果没有上面的属性，我们需要 2 次通过来解决问题。首先通过调用Matcher.matches()/String.matches()上的模式K*。第二遍：

  • 如果字符串与 pattern 不匹配K*，我们将Matcher.find()在 pattern 上重复使用，\GK直到找不到更多匹配项。这可以通过我们如何定义当输入字符串与模式不匹配时采用哪个前缀字符串来完成K*。

  • 如果字符串与 pattern 匹配，则在 pattern 上K*重复使用是一种解决方案。但是，这将导致与输入字符串的其余部分匹配的冗余工作。Matcher.find()\GK(?=K*$)

请注意，此解决方案普遍适用于任何 K。换句话说，它也适用于K*等价于的情况K*+（但我们将使用更好的一次性解决方案来代替该情况）。

于 2013-05-16T17:08:14.163 回答
6

这是对已经接受的答案的附加答案。下面是一个示例代码片段，它只通过模式一次m.find()，这类似于您的一次性解决方案，但不会解析不匹配的行。

import java.util.regex.*;

class test{
    public static void main(String args[]){
        String t = "<1><2><3>";
        Pattern pat = Pattern.compile("(<\\d>)(?=(<\\d>)*$)(?<=^(<\\d>)*)");
        Matcher m = pat.matcher(t);
        while (m.find()) {
            System.out.println("Matches!");
            System.out.println(m.group());
        }       

    }
}

正则表达式解释：

<\\d>--这是你上面定义的 k 模式
?=-- 正向前瞻（检查 K 前面的内容）
<\\d>*-- 匹配 k 0 次或更多次
$-- 行尾
?<=-- 正向后视（检查 K 后面
^的内容） -- 开头line
<\\d>*-- 后跟 0 个或多个 Ks

正则表达式是美丽的东西。

编辑：正如@nhahtdh 向我指出的那样，这只是答案的一个实施版本。事实上，上面的实现可以通过答案中的知识来改进。
(<\\d>)(?=(<\\d>)*$)(?<=^(<\\d>)*)可以改成\\G<\\d>(?=(<\\d>)*$)。

于 2013-05-16T18:26:17.683 回答
3

Matcher.start以下是使用和的一次性解决方案Matcher.end。

boolean products(String products)
{
    String regex = "<[0-9]>";

    Pattern p = Pattern.compile(regex);

    Matcher matcher = p.matcher(products);
    int lastEnd = 0;
    while (matcher.find())
    {
        if (lastEnd != matcher.start())
           return false;
        System.out.println(matcher.group());
        lastEnd = matcher.end();
    }
    if (lastEnd != products.length())
        return false;
    return true;
}

唯一的缺点是它会在找到无效数据之前打印出（或处理）所有值。

例如，products("<1><2>a<3>");将打印出：

<1>
<2>

在抛出异常之前（因为直到那里字符串才有效）。

要么发生这种情况，要么必须暂时存储所有这些似乎是不可避免的。

于 2013-05-16T11:51:44.560 回答
1 
    String t = "<1><2><3>";
    Pattern pat = Pattern.compile("(<\\d>)*");
    Matcher m = pat.matcher(t);
    if (m.matches()) {
        //String[] tt = t.split("(?<=>)"); // Look behind on '>'
        String[] tt = t.split("(?<=(<\\d>))"); // Look behind on K
    }
于 2013-05-16T15:58:44.677 回答