10

特定の入力文字列と特定のパターン K について、文字列からすべての K (またはその一部 (グループを使用)) を抽出し、文字列全体が一致することをK*確認します(0 個以上の K で構成されているように)他のキャラクターなし）。

しかし、正規表現を使用して単一のパスでこれを行いたいと思います。より具体的には、現在 を使用してパターンを見つけていますMatcher.findが、これは厳密には必須ではありません。

どうすればいいですか？

私はすでに解決策を見つけました（そして回答を投稿しました）が、Matcherこの問題に対処する/対処できる特定の正規表現または機能があるかどうか、または単にそれを行うためのより良い/異なる方法があるかどうかを知りたい. しかし、たとえそうでなくても、それは興味深い質問だと思います。

例：

パターン: <[0-9]>( 内の 1 桁の数字<>)

有効な入力:<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*。
  • 文字列に pattern がある場合はK*、一致する重複しないトークンに文字列を分割しますK。
  • 文字列に pattern に一致するプレフィックスしかない場合は、 1K*によって選択されたプレフィックスを選択し、プレフィックスを K に一致するトークンに分割します。K*+

1とにかく K に一致する最長のプレフィックスを取得する方法があるかどうかはわかりません。もちろん、最後の文字を 1 つずつ削除して、K*一致するまでテストすることはいつでもできますが、明らかに非効率的です。

特に明記しない限り、以下に記載するものはすべて、上記の問題の説明に従います。問題の 3 番目の箇条書きは、どのプレフィックス文字列を使用するかについてのあいまいさを解決することです。

2. .NET で繰り返しキャプチャ グループ

上記の問題は、問題の解決策があれば解決できます。

(K)*繰り返されるキャプチャ グループであるpatternを指定すると、最後の繰り返しだけでなく、すべての繰り返しについてキャプチャされたテキストを取得します。

  • 文字列に pattern がある場合、K*と照合することで^(K)*$、 pattern に一致するすべてのトークンを取得できますK。
  • 文字列が に一致するプレフィックスのみを含む場合、 とK*照合することで^(K)*、 pattern に一致するすべてのトークンを取得できますK。

これは .NET 正規表現の場合に当てはまります。これは、繰り返されるキャプチャ グループのすべてのキャプチャされたテキストを保持するためです。

ただし、Java を使用しているため、そのような機能にはアクセスできません。

3. Java での解決策

文字列がパターンK*を持っていることの確認は、常にMatcher.matches()/String.matches()で行うことができます。これは、エンジンが入力文字列に対して本格的なバックトラックを実行して、何らかの方法で入力文字列と「統合」するためK*です。難しいのは、入力文字列を pattern に一致するトークンに分割することですK。

K*と同等の場合K*+

パターン K に次のプロパティがある場合:

すべての文字列に対して2はK*と同等ですK*+。つまり、入力文字列が pattern に一致するトークンに分割される方法はK同じです。

2この条件は、操作している入力文字列に対してのみ定義できますが、この前提条件を確保するのは簡単ではありません。すべての文字列に対して定義すると、正規表現を分析して条件が成立するかどうかを確認するだけで済みます。

その後、問題を解決するワンパス ソリューションを構築できます。Matcher.find()patternで繰り返し使用でき\GK、見つかった最後の一致が文字列の末尾にあることを確認します。これは、コードで境界チェックを行うことを除いて、現在のソリューションに似ています。

inの量指定子の+後は、量指定子を所有格にします。所有量指定子は、エンジンがバックトラックするのを防ぎます。これは、各繰り返しが常にパターン K の最初の可能な一致であることを意味します。パターン K の最初の可能な一致も返すため、ソリューションが同等の意味を持つようにするために、このプロパティが必要です。*K*+\GK

K*同等でない場合K*+

上記のプロパティがなければ、問題を解決するには 2 つのパスが必要です。pattern でMatcher.matches()/を呼び出すための最初のパス。2 回目のパス:String.matches()K*

  • 文字列が pattern に一致しない場合は、一致するものが見つからなくなるまでパターンでK*繰り返し使用します。これは、入力文字列が pattern に一致しない場合にどのプレフィックス文字列を使用するかを定義する方法により実行できます。Matcher.find()\GKK*

  • 文字列が pattern に一致する場合、 patternK*で繰り返し使用Matcher.find()すること\GK(?=K*$)が 1 つの解決策です。ただし、これにより、残りの入力文字列と一致する冗長な作業が発生します。

この解は任意の K に普遍的に適用可能であることに注意してください。つまり、 がK*と等しい場合にも適用されますK*+(ただし、代わりに、より優れたワンパス ソリューションを使用します)。

于 2013-05-16T17:08:14.163 に答える
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 に答える