php - "vertical"正则表达式匹配 ASCII "image"

Question

注意:这是一个关于现代正则表达式的可能性的问题。这不是使用其他方法解决此问题的最佳方法。它的灵感来自 an earlier question ，但不限于正则表达式。

问题

在 ASCII“图像”/art/map/string 中，例如:

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

我想找一个由三个X组成的简单垂直线:

X
X
X

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

问题

使用正则表达式(PCRE/PHP、Perl、.NET 或类似)是否可​​以:

1. 确定是否存在这样的编队
2. 计算这种编队的数量/匹配所有编队的起点(上例中为 4 个)

Answer 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。

该表达式使用带有自引用捕获组的前瞻来为前瞻的每次重复添加一个字符(这用于“计数”)。

\1?+ 表示如果 \1 匹配(或已定义)使用它，并且不将其归还(不要回溯)。在这种情况下，它等效于 (?(1)\1)。这意味着如果 \1 已定义，则匹配 \1。

polygenelubricants在 his answer for How can we match a^n b^n with Java regex? 中很好地解释了这种带有反向引用的前瞻。 . (他还写过关于 Java 正则表达式的其他令人印象深刻的技巧，涉及反向引用和环视。)

回答问题 2

普通匹配

当仅使用匹配并要求匹配数中的答案(计数)时，问题 2 的答案将是:

它可以不直接在具有有限后视的正则表达式风格中解决。而像 Java 和 .NET 这样的其他风格可以(例如在 m.buettner's .NET solution 中)。

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

(半？)证明

假设没有可用的可变长度后视。

您必须以某种方式计算 X 之前一行中的字符数。
做到这一点的唯一方法是匹配它们，并且由于没有可用的可变长度后视，您必须(至少)在行首开始匹配。
如果从一行的开头开始匹配，则每行最多只能匹配一个。

由于每行可能出现多次，因此不会全部计算在内，也不会给出正确答案。

长度/间接解

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

此解决方案基于m.buettner's nice "partial PCRE solution" 或受其启发.

可以简单地将以下表达式的所有匹配项替换为 $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)