首页 ❯

ASCII“图像”中的“垂直”正则表达式匹配对问题1的答复对问题2的答复

php regex .net perl pcre
2022-08-30 09:40:16

注意：这是一个关于现代正则表达式口味可能性的问题。这不是关于使用其他方法解决这个问题的最佳方法。它的灵感来自前面的一个问题，但这个问题并不局限于正则表达式。

问题

在ASCII“图像”/艺术/地图/字符串中，例如：

....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....

我想找到一个简单的三个s的垂直线形成：X

X
X
X

图像中的行数是可变的，每行的宽度也是可变的。

问题

使用正则表达式（PCRE / PHP，Perl，.NET或类似）可以：

  1. 确定是否存在这样的地层
  2. 计算此类阵型的数量/匹配所有阵型的起点（在上面的示例中为4个）

答案 1

对问题1的答复

要回答第一个问题，可以使用：

(?xm)                    # ignore comments and whitespace, ^ matches beginning of line
^                        # beginning of line
(?:
    .                    # any character except \n
    (?=                  # lookahead
        .*+\n            # go to next line
        ( \1?+ . )       # add a character to the 1st capturing group
        .*+\n            # next line
        ( \2?+ . )       # add a character to the 2nd capturing group
    )
)*?                      # repeat as few times as needed
X .*+\n                  # X on the first line and advance to next line
\1?+                     # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X .*+\n                  # X on the 2nd line and advance to next line
\2?+                     # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line
X                        # X on the 3rd line

Online demo

此表达式适用于 Perl、PCRE、Java，并且应该在 .NET 中工作。

该表达式使用具有自引用捕获组的 lookaheads 为每次重复的 lookahead 添加一个字符（这用于“计数”）。

\1?+意味着如果匹配项（或已定义）消耗它，并且不要将其返回（不要回溯）。在本例中，它等效于 。这意味着定义了匹配 if。\1(?(1) \1 )\1\1

polygenelubricants在他的回答中很好地解释了这种带有反向引用的前瞻 我们如何将a^n b^n与Java正则表达式相匹配？。（他还写了关于Java正则表达式的其他令人印象深刻的技巧，涉及反向引用和查找。

对问题2的答复

普通匹配

当仅使用匹配并要求匹配次数中的答案（计数）时，问题2的答案将是：

它不能在具有有限外观的正则表达式类型中直接解决。而Java和.NET等其他风格可以（例如在m.buettner的.NET解决方案中）。

因此，在这种情况下，Perl和PCRE（PHP等）中的普通正则表达式匹配不能直接回答这个问题。

（半？证明

假定没有可用的可变长度查找后缀。

您必须以某种方式计算一行中在 .
做到这一点的唯一方法是匹配它们，并且由于没有可用的可变长度查找后缀，因此您必须（至少）在行的开头开始匹配。
如果您在一行的开头开始比赛，则每行最多只能获得一场比赛。X

由于每行可以有多个匹配项，因此这不会将它们全部计算在内，也不会给出正确的答案。

长度/间接解决方案

另一方面，如果我们接受答案作为匹配或替换结果的长度，那么第二个问题可以用PCRE和Perl（以及其他风格）来回答。

该解决方案基于/灵感来自m.buettner的“部分PCRE解决方案”。

可以简单地将以下表达式的所有匹配项替换为 ，得到问题二（兴趣模式的数量）的答案作为结果字符串的长度。$3

^
(?:
    (?:                   # match .+? characters
        .
        (?=               # counting the same number on the following two lines
            .*+\n
            ( \1?+ . )
            .*+\n
            ( \2?+ . )
        )
    )+?
    (?<= X )              # till the above consumes an X
    (?=                   # that matches the following conditions
        .*+\n
        \1?+
        (?<= X )
        .*+\n
        \2?+
        (?<= X )
    )
    (?=                   # count the number of matches
        .*+\n
        ( \3?+ . )        # the number of matches = length of $3
    )
)*                        # repeat as long as there are matches on this line
.*\n?                     # remove the rest of the line

在Perl中可以写成：

$in =~ s/regex/$3/gmx;
$count = length $in;

Online demo

此表达式类似于上面问题 1 的解决方案，但进行了一些修改，以包含在第一个前瞻中匹配的字符中，用量词包装并计算量词的匹配次数。X

除了直接匹配之外，这是尽可能接近的（除了正则表达式之外，额外的代码明智），并且可能是问题2的可接受答案。

测试用例

上述解决方案的一些测试用例和结果。结果显示数字答案（结果字符串的长度）和替换后的结果字符串在括号中。

Test #0:
--------------------
X
X
X

result: 1 (X)


Test #1:
--------------------
..X....
..X....
..X....

result: 1 (.)


Test #2:
--------------------
..X.X..
..X.X..
....X..

result: 1 (.)


Test #3:
--------------------
..X....
..X....
...X...

result: 0 ()


Test #4:
--------------------
..X....
...X...
..X....

result: 0 ()


Test #5:
--------------------
....X..
.X..X..
.X.....

result: 0 ()


Test #6:
--------------------
.X..X..
.X.X...
.X.X...

result: 1 (.)


Test #7:
--------------------
.X..X..
.X..X..
.X..X..

result: 2 (.X)


Test #8:
--------------------
XXX
XXX
XXX

result: 3 (XXX)


Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.

result: 5 (XXXXX)


Test #10:
--------------------
1....X.......
2..X..X...X....
3X.X...X..X.....
4X....XXXXXX.....
5X..XXX...........
6.....X..........
7.........X....X
8..X......X....X....
9..X......X....X....X...
A....X.....
B.X..X..
C.....
XXX
XXX
XXX
.

result: 8 (3458.XXX)

答案 2

编辑

以下解决方案存在两个严重问题：

  1. 它们无法匹配从同一条线开始的多个序列，因为进展太大了。XXXpos
  2. 第二种解决方案是不正确的：它与两个彼此上方的连续行匹配。不一定必须连续有三个。X

因此，所有赞成票（和赏金）都应该去m.buettner全面的.NET答案或Qtax本人的引人入胜的PCRE答案。

原始答案

这是一个使用将Perl代码嵌入到正则表达式中的答案。因为 Perl 正则表达式可以使用代码来断言正则表达式内的任意条件或发出部分正则表达式，所以它们不仅限于匹配常规语言或上下文无关语言，而是可以匹配乔姆斯基层次结构中更高级别的语言的某些部分。

要匹配的语言可以用正则表达式术语描述为

^ .{n} X .*\n
  .{n} X .*\n
  .{n} X

其中 是一个数字。这与匹配 an b ncn语言一样复杂，后者是上下文相关语言的规范示例。n

我们可以很容易地匹配第一行，并使用一些Perl代码来发出其他行的正则表达式：

    /^ (.*?) X
       (?: .*\n (??{"." x length($1)}) X){2}
    /mx

这太短了！它有什么作用？

  • ^ (.*?) X在行的开头放置锚点，匹配尽可能少的非换行符，然后匹配 .我们记得作为捕获组的线。XX$1

  • 我们重复一个组两次，该组与行的其余部分匹配，换行符，然后注入与 相同长度的字符串的正则表达式。之后，必须有一个 .$1X

此正则表达式现在将匹配每个相互叠加有三个的字符串。X

如果我们想提取所有这些序列，我们必须保持漂亮。因为序列可能重叠，例如

.X
XX
XX
X.

下一场比赛开始的位置不得经过第一场比赛。我们可以通过观察和观察来做到这一点。Perl仅支持恒定长度的lookbehind，但具有提供类似语义的转义。因此X\K

/^ (.*?) \K X
   (?=( (?: .*\n (??{"."x length($1)}) X ){2} ))
/gmx

将匹配三个垂直 es 的每个序列。测试时间：X

$ perl -E'my$_=join"",<>; say "===\n$1X$2" while /^(.*?)\KX(?=((?:.*\n(??{"."x length($1)})X){2}))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXX
===
X.X...X..X.....
X....XXXXXX.....
X
===
X....XXXXXX.....
X..XXX...........
.....X
===
..............X
..X...........X....
..X...........X

注意：这依赖于至少从Perl 5，v10开始可用的实验性正则表达式功能。该代码使用 v16 perl 进行了测试。

无需嵌入式代码的解决方案

让我们来看看这些线条

...X...\n
...X..\n

我们想要断言每行的前导部分具有相同的长度。我们可以通过使用基本情况递归来做到这一点：...X.*\n

(X.*\n|.(?-1).)X

如果我们将其锚定在一条线的开头，我们可以匹配两个垂直的es。要匹配两行以上的行，我们必须在前瞻中执行递归，然后将匹配位置前进到下一行，然后重复。为此，我们只需匹配。X.*\n

这将生成以下正则表达式，该正则表达式可以将字符串与三个垂直 es 匹配：X

/ ^
  (?:
    (?=( X.*\n | .(?-1). ) X)
    .*\n # go to next line
  ){2}
/mx

但这还不够好，因为我们想要匹配所有这样的序列。为此，我们基本上将整个正则表达式放入一个前瞻。正则表达式引擎确保每次都推进位置以产生新的匹配。

/ ^
  (?=
    (
      (?:
          (?= (X.*\n | .(?-1). ) X)
          .*\n # go to next line
      ){2}
      .* # include next line in $1
    )
  )
/mx

测试时间：

$ perl -E'my$_=join"",<>; say "===\n$1" while /^(?=((?:(?=(X.*\n|.(?-1).)X).*\n){2}.*))/gmx' <<'END'
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
END
===
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
===
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
===
X....XXXXXX.....
X..XXX...........
.....X..........
===
..............X
..X...........X....
..X...........X....X...

因此，这与具有嵌入式代码的解决方案一样有效，也就是说，它将每组行与垂直es匹配，而不是每组es。（实际上，这个解决方案对我来说似乎比嵌入式代码更脆弱）XX


推荐
更多 »
标签
更多 »
php pass-by-reference optional-parameters default-value javascript arrays dom function string object serialization tostring visibility syntax jslint use-strict operators equality equality-operator identity-operator datetime timestamp date-arithmetic redirect angularjs loops foreach iteration scope variables
推荐
更多 »