43

一連の教育正規表現記事の一部であり、ネストされた参照の概念を穏やかに紹介しています。

最初のいくつかの三角数は次のとおりです。

 1 = 1
 3 = 1 + 2
 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
15 = 1 + 2 + 3 + 4 + 5

数値が三角形かどうかを確認する方法はたくさんあります。次のように正規表現を使用するこの興味深い手法があります。

  • nが与えられると、最初に同じ文字で満たされた長さnの文字列を作成します
  • 次に、この文字列をパターンと照合します^(\1.|^.)+$
    • このパターンが文字列と一致する場合にのみ、nは三角形になります

これがいくつかの言語で機能することを示すためのスニペットを次に示します。

PHP（ideone.com）

$r = '/^(\1.|^.)+$/';

foreach (range(0,50) as $n) {
  if (preg_match($r, str_repeat('o', $n))) {
     print("$n ");
  }
}

Java（ideone.com上）

for (int n = 0; n <= 50; n++) {
    String s = new String(new char[n]);
    if (s.matches("(\\1.|^.)+")) {
        System.out.print(n + " ");
    }
}

C＃（ideone.com）

Regex r = new Regex(@"^(\1.|^.)+$");

for (int n = 0; n <= 50; n++) {
    if (r.IsMatch("".PadLeft(n))) {
       Console.Write("{0} ", n);
    }
}

したがって、この正規表現は機能しているように見えますが、誰かがその方法を説明できますか？

同様の質問

4

1 に答える 1

36

説明

パターンの概略図は次のとおりです。

from beginning…
|         …to end
|         |
^(\1.|^.)+$
 \______/|___match
  group 1    one-or-more times

(…) 角かっこはキャプチャグループ1を定義し、このグループは。と繰り返し一致し+ます。このサブパターンはとで固定され^、$文字列全体と一致するかどうかを確認します。

グループ1はthis|that 代替案を照合しようとします：

  • \1.、つまり、グループ1が一致したもの（自己参照！）に加えて、「任意の」文字の1つ、
  • または^.、つまり、最初の「任意の」1文字

グループ1には、グループ1が一致したものへの参照があることに注意してください。これはネストされた/自己参照であり、この例で紹介されている主なアイデアです。キャプチャグループが繰り返される場合、通常は最後のキャプチャのみが保持されるため、この場合の自己参照は基本的に次のようになります。

「前回一致したものに加えて、もう1つ一致させてみてください。今回はそれを一致させます。」

再帰と同様に、自己参照を伴う「基本ケース」が必要です。の最初の反復では+、グループ1はまだ何もキャプチャしていませんでした（これは、空の文字列で始まると言っているのと同じではありません）。したがって、グループ1を「初期化」する方法として、2番目の代替が導入されます。これは、文字列の先頭にあるときに1つの文字をキャプチャできるようにすることです。

したがって、で繰り返されるように+、グループ1は最初に1文字、次に2、次に3、次に4などと一致しようとします。これらの数値の合計は三角数です。

さらなる探求

簡略化のために、入力と同じ繰り返し文字で構成される文字列を使用したことに注意してください。このパターンがどのように機能するかがわかったので、このパターンが、など"1121231234"の文字列にも一致することがわかります。"aababc"

また、nが三角数、つまりn = 1 + 2+…+kであることがわかった場合、最後にグループ1によってキャプチャされた文字列の長さはkになります。

これらのポイントは両方とも、次のC＃スニペット（ideone.comにも表示されます）に示されています。

Regex r = new Regex(@"^(\1.|^.)+$");

Console.WriteLine(r.IsMatch("aababc"));     // True
Console.WriteLine(r.IsMatch("1121231234")); // True
Console.WriteLine(r.IsMatch("iLoveRegEx")); // False

for (int n = 0; n <= 50; n++) {
    Match m = r.Match("".PadLeft(n));
    if (m.Success) {
       Console.WriteLine("{0} = sum(1..{1})", n, m.Groups[1].Length);
    }
}
// 1 = sum(1..1)
// 3 = sum(1..2)
// 6 = sum(1..3)
// 10 = sum(1..4)
// 15 = sum(1..5)
// 21 = sum(1..6)
// 28 = sum(1..7)
// 36 = sum(1..8)
// 45 = sum(1..9)

フレーバーノート

すべてのフレーバーがネストされた参照をサポートしているわけではありません。使用しているフレーバーの癖を常によく理解してください（したがって、正規表現関連の質問をするときは常に、この情報を提供するのに役立ちます）。

ほとんどのフレーバーでは、標準の正規表現マッチングメカニズムは、パターンが入力文字列の任意の部分（おそらく、必ずしもそうとは限りませんが、入力全体）に一致するかどうかを確認しようとします。つまり、必要に応じて^、$常にパターンを固定することを忘れないでください。

Javaはその点でわずかに異なり、String.matches入力文字列全体に対してパターンを一致させようとしPattern.matchesます。これが、上記のスニペットでアンカーを省略できる理由です。Matcher.matches

\A他のコンテキストでは、代わりに\Zアンカーを使用する必要がある場合があることに注意してください。たとえば、複数行モードでは、入力の各行の最初と最後を一致^させます。$

最後に、.NET正規表現では、繰り返しキャプチャグループによって作成されたすべての中間キャプチャを実際に取得できます。ほとんどのフレーバーでは、できません。すべての中間キャプチャが失われ、最後のキャプチャのみを保持できます。

関連する質問

ボーナス素材：正規表現を使用して2の力を見つけます!!!

わずかな変更を加えるだけで、ここで紹介したのと同じ手法を使用して、2の累乗を見つけることができます。

利用したい基本的な数学的特性は次のとおりです。

  • 1 = 1
  • 2 =（1）+ 1
  • 4 =（1 + 2）+ 1
  • 8 =（1 + 2 + 4）+ 1
  • 16 =（1 + 2 + 4 + 8）+ 1
  • 32 =（1 + 2 + 4 + 8 + 16）+ 1

解決策を以下に示します（ただし、最初に自分で解決してみてください!!!!）

（ PHP、Java、およびC＃のideone.comを参照してください）：

^(\1\1|^.)*.$

于 2010-09-02T13:43:57.730 に答える