提问者:小点点

"ASCII"图像中的垂直"正则表达式匹配"


注:这是一个关于现代正则表达式口味可能性的问题。这不是用其他方法解决这个问题的最佳方法。它受到了前面一个问题的启发,但这个问题并不局限于正则表达式。

在ASCII“image”/art/map/string格式中:

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

我想找到三个Xs组成的简单垂直线:

X
X
X

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

使用正则表达式(PCRE/PHP, Perl,.NET或类似)是否有可能:

  1. 确定是否存在此类地层

共3个答案

匿名用户

为了回答第一个问题,我们可以使用:

(?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

在线演示

此表达式适用于Perl、PCREJava,应该适用于。NET.

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

\1表示如果\1匹配(或定义)使用它,并且不返回(不回溯)。在这种情况下,它相当于(?(1)\1)。如果定义了\1,则表示匹配\1

Polygene在回答如何将a^n b^n与Java正则表达式相匹配时,用反向引用很好地解释了这种外观?。(他还为Java正则表达式编写了其他令人印象深刻的技巧,包括反向引用和lookaround)

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

它不能直接解决在正则表达式风味,有一个有限的后视镜。而其他口味像Java和。NET可以(例如在m.buettner。NET解决方案)。

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

假设没有可变长度的lookbehind可用。

您必须以某种方式计算X前一行的字符数
唯一的方法是匹配它们,因为没有可变长度的lookbehind可用,所以您必须(至少)在行首开始匹配
如果从一行的开头开始匹配,则每行最多只能获得一个匹配。

由于每行可能出现多个事件,因此无法将其全部计算在内,也无法给出正确答案。

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

该解决方案基于/受m.buettner漂亮的“部分PCRE解决方案”的启发。

我们可以简单地用3美元替换下面表达式的所有匹配项,得到问题2的答案(兴趣模式的数量)作为结果字符串的长度。

^
(?:
    (?:                   # 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;

在线演示

该表达式类似于上面问题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)

匿名用户

以下解决方案有两个严重问题:

  1. 它们无法匹配从同一行开始的多个XXX序列,因为pos前进太多

因此,所有的赞成票(和赏金)都应该m.buettner的综合票。NET的答案或迷人的PCRE的答案从库塔自己。

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

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

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

其中n是一个数字。这与匹配anbncn语言一样复杂,后者是上下文敏感语言的典型示例。

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

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

那很短!它是做什么的?

>

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

这个正则表达式现在将匹配每个有三个X的字符串。

如果我们想提取所有这样的序列,我们必须很漂亮。因为序列可能重叠,例如。

.X
XX
XX
X.

下一个匹配开始的位置不能经过第一个X。我们可以通过向后看和向前看来做到这一点。Perl只支持常量长度的lookback,但是有\K转义,它提供了类似的语义学。因此

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

将匹配三个垂直Xes的每个序列。测试时间:

$ 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

如果我们将其锚定在一行的开头,我们可以匹配两个垂直的Xes。要匹配两行以上的代码,我们必须先进行一次前瞻性递归,然后将匹配位置提前到下一行,然后重复。为此,我们只需匹配*\n

这将产生以下正则表达式,它可以匹配具有三个垂直Xe的字符串:

/ ^
  (?:
    (?=( 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...

所以这和嵌入代码的解决方案一样有效,也就是说,它用垂直的Xes匹配每组行,而不是每组Xes。(实际上,这个解决方案在我看来比嵌入式代码更脆弱)

匿名用户

首先,这是一个很好的问题。我认为尝试将正则表达式引擎发挥到极限是非常有益的。

你们在评论中说这很容易。NET,但是因为还没有答案,我想我应该写一个。

你可以同时解决问题1和2。NET的可变长度查找和平衡组。大部分工作由平衡组完成,但是可变长度的查找对于能够检测同一行上开始的多个匹配至关重要。

无论如何,以下是模式:

(?<=                  # lookbehind counts position of X into stack
  ^(?:(?<a>).)*       # push an empty capture on the 'a' stack for each character
                      # in front of X
)                     # end of lookbehind

X                     # match X

(?=.*\n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
  (?(a)(?!))          # make sure that stack 'a' is empty
  X.*\n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack 'b', and consume
                      # a character
  (?(b)(?!))          # make sure that stack 'b' is empty
  X                   # match a final X
)                     # end of lookahead

此模式必须与RegexOptions一起使用。多行,用于^匹配行的开头(显然是使用RegexOptions.IgnorePatternWhitespace,以便自由空间模式工作)。

以下是一些补充意见:

通过将除了初始X之外的所有内容放入lookaround中,我们没有重叠匹配的问题,甚至匹配从同一行开始。然而,后视必须是可变长度的,这当然限制了这种解决方案。NET.

其余的则依赖于对平衡群体的把握。我不会在这里详细讨论这个问题,因为它本身就有很长的答案。(有关更多信息,请参阅MSDN和本博文)

查找后面的只是匹配^。*,所以直到行开始的所有内容,但对于每个。我们将空捕获推送到堆栈a上,从而将我们的X的位置计数为堆栈的大小。

然后,在使用了lookahead中的剩余行之后,我们再次匹配*,但在消费每个之前,我们从堆栈a中弹出一个元素(一旦a为空,就会导致失败),并将空捕获推到b(这样我们就不会忘记第三行必须有多少个字符)。

为了确保真正清空整个堆栈,我们使用(?(a)(?!)。这是一个条件模式,尝试匹配(?!)如果堆栈a不是空的(否则跳过)。和(?!)是一个空的负前瞻,它总是失败。因此,这只是编码“aanotempty?fail。否则,继续”。

现在我们已经知道新行中的字符数量是正确的,我们尝试将aX与该行的其余部分匹配起来。然后我们对stackb再次重复相同的过程。现在不需要推上任何新的堆栈,因为如果这样做有效,我们就完成了。我们在此之后检查b是否为空,并匹配第三个X

最后,优化方面注意:如果所有重复都被原子组包裹,这种模式仍然有效(从而模拟不支持的所有格量词。NET)!这将节省很多回溯。此外,如果我们至少把堆栈弹出量词放在原子组中,我们可以去掉两个(?(...)(?!))检查(因为这些只是需要的情况下,其中前面的重复必须回溯)。

(只有最勇敢的冒险家才会跟着我进入我即将进入的真正黑暗的洞穴…)

正如评论中所讨论的,这种解决方案有一个缺点:它计算重叠匹配。例如。

..X..
..X..
..X..
..X..

给出两个匹配,一个在第一行,一个在第二行。我们希望避免这种情况,并且只报告一个匹配(如果有6到8个Xs,则报告两个,如果有9到11个Xs,则报告三个)。此外,我们想在1号、4号、7号报告比赛,...X

我们可以通过要求第一个X前面有3个其他Xs的整数倍来调整上述模式以允许此解决方案。检查这个的基本想法使用了和以前相同的堆栈操作(除了我们在3个堆栈之间移动东西,这样在找到三个X后,我们就会在开始的地方结束)。要做到这一点,我们必须摆弄一点后视镜。

不过有一个陷阱。NET的可变长度查找使用另一个。NET特有的功能,RightToLeftMode,其中模式从右向左读取(并匹配)。通常这不需要打扰我们,但当我们将其与平衡小组结合起来时,我们可能会遇到一些不愉快的惊喜。特别是,在考虑捕获堆栈如何演化时,我们还需要从右到左(或从下到上)构造(并读取)表达式。

因此,当您阅读以下表达式(以及我的注释)时,请从最外层的lookback(您必须滚动一点)的末尾开始,即仅在顶层X之前;然后一直读到顶部。然后在后面继续。

(?<=                  
  # note that the lookbehind below does NOT affect the state of stack 'a'!
  # in fact, negative lookarounds can never change any capturing state.
  # this is because they have to fail for the engine to continue matching.
  # and if they fail, the engine needs to backtrack out of them, in which
  # case the previous capturing state will be restored.
  (?<!                # if we get here, there is another X on top of the last
                      # one in the loop, and the pattern fails
    ^                 # make sure we reached the beginning of the line
    (?(a)(?!))        # make sure that stack 'a' is empty
    (?:(?<-a>).)*     # while we can pop an element from stack 'a', and consume
                      # a character
    X.*\n             # consume the next line and a potential X
  )
  # at this point we know that there are less than 3 Xs in the same column
  # above this position. but there might still be one or two more. these
  # are the cases we now have to eliminate, and we use a nested negative
  # lookbehind for this. the lookbehind simply checks the next row and
  # asserts that there is no further X in the same column.
  # this, together with the loop, below means that the X we are going to match
  # is either the topmost in its column or preceded by an integer multiple of 3
  # Xs - exactly what we are looking for.
  (?:

    # at this point we've advanced the lookbehind's "cursor" by exactly 3 Xs
    # in the same column, AND we've restored the same amount of captures on
    # stack 'a', so we're left in exactly the same state as before and can
    # potentially match another 3 Xs upwards this way.
    # the fact that stack 'a' is unaffected by a full iteration of this loop is
    # also crucial for the later (lookahead) part to work regardless of the
    # amount of Xs we've looked at here.

    ^                 # make sure we reached the beginning of the line
    (?(c)(?!))        # make sure that stack 'a' is empty
    (?:(?<-c>)(?<a>).)* # while we can pop an element from stack 'c', push an
                      # element onto 'a' and consume a character
    X.*\n             # consume the next line and a potential X
    (?(b)(?!))        # make sure that stack 'b' is empty
    (?:(?<-b>)(?<c>).)* # while we can pop an element from stack 'b', push an
                      # element onto 'c' and consume a character
    X.*\n             # consume the next line and a potential X
    (?(a)(?!))        # make sure that stack 'a' is empty
    (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
    X.*\n             # consume the next line and a potential X
  )*                  # this non-capturing group will match exactly 3 leading
                      # Xs in the same column. we repeat this group 0 or more
                      # times to match an integer-multiple of 3 occurrences.
  ^                   # make sure we reached the beginning of the line
  (?:(?<a>).)*        # push an empty capture on the 'a' stack for each
                      # character in front of X
)                     # end of lookbehind (or rather beginning)

# the rest is the same as before    

X                     # match X
(?=.*\n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
  (?(a)(?!))          # make sure that stack 'a' is empty
  X.*\n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack 'b', and consume
                      # a character
  (?(b)(?!))          # make sure that stack 'b' is empty
  X                   # match a final X
)                     # end of lookahead

RegexHero的工作演示。网

这次我把所有的解释都穿插在模式中。所以如果你按照我上面推荐的方式阅读模式,你会在需要的时候得到正确的解释...

现在这是一个地狱般的野兽。但它现在满足了整个规范,并展示了它的强大功能。NET的regex风格真的很好。而且,尽管这看起来很可怕,但我认为(一旦你意识到从右到左的事情),这比使用PCRE的类似解决方案(使用递归或其他方式)更容易理解。

正如Kobi在下面的评论中所提到的,如果您接受在单个匹配的多个捕获中发现您的结果(例如,如果您有7个Xs的列,则您只能获得一个匹配,但在某个组中有两个捕获),则可以将此缩短一段时间。您可以通过重复主(向前看)部分1次或多次,并捕获初始的X(但将所有内容都放在向前看中)来实现这一点。然后,lookback不需要计算Xs的三倍,只需检查是否没有前导X。这可能会将图案的大小减半。

(如果只有最勇敢的冒险家跟随我完成最后一个解决方案,我可能在下一次旅程中只剩下疯子了……)

为了证明我刚才所说的上述解决方案与PCRE的比较,让我们看看如何远程解决PCRE中的全部问题。我们必须更加努力地工作,没有可变长度的后视和平衡组。

Qtax(OP)为他的第一个问题(检查字符串是否包含任何X-列)提供了一个出色的解决方案,使用自引用组进行计数。这是一个非常优雅和紧凑的解决方案。但是,由于每一个匹配都是从行的开头到列的开头的X,并且匹配不能重叠,因此我们不能在每一行中获得多个匹配。我们可以尝试将所有内容放在一个向前看的位置(这样实际上就没有匹配的内容),但是两个零宽度的匹配也永远不会在同一位置开始-所以我们仍然只能在每个候选行中获得一个匹配。

但是,确实可以使用PCRE至少解决问题2的第一部分:计算每行中开始的列数(从而计算X列的总数)。因为我们不能以单个匹配的形式获取此计数(请参见上一段),也不能以单个组或捕获的形式获取此计数(因为PCRE只提供固定数量的捕获,而不是.NET)。我们可以做的是编码匹配中的列数。

方法如下:对于每一行,我们检查是否有一列开始。如果是这样的话,我们在某个捕获组中包含一个角色。然后,在报告成功匹配之前,我们尝试查找尽可能多的其他列—每个列都会向特定组添加一个字符。通过这样做,我们对特定捕获长度中从每行开始的列数进行编码。

实际上在正则表达式中实现这个概念比它最初听起来要复杂得多(而且听起来已经相当复杂了)。不管怎样,就是这样:

^                        
(?:(?|
  (?(5)(?![\s\S]*+\5))      
  (?!(?!)()()) 
  (?=
    (?:
      .                  
      (?=                
        .*+\n            
        ( \3? . )   
        .*+\n        
        ( \4? . )    
      )
    )*?              
    X .*+\n          
    \3               
    X .*+\n          
    \4               
  )
  ()
|
  (?(5)(?=[\s\S]*+\5)|(?!))
  (?:
    .
    (?=
      .*+\n
      ( \1? .)
      .*+\n
      ( \2? .)
    )
  )+?
  (?=
    (?<=X).*+\n
    (\1)         
    (?<=X).*+\n
    (\2)         
    (?<=X)     
  )
  (?=
    ([\s\S])   
    [\s\S]*
    ([\s\S] (?(6)\6))
  )
){2})+

(事实上,这要简单一点——如何简化这种方法,请参见Qtax的答案。出于学术原因,我将把这种方法留在这里,因为可以从中学习到一些非常先进和有趣的技术——请参见最后的总结。)

是的,没有注释。我想,实际上没有人会读它们,所以我会尝试将这个表达式分成几个部分(我会采用自顶向下的方法)。

让我们看看地狱洋葱的外层:

^                        
(?:(?|
  checkForNextColumn
|
  countAndAdvance
){2})+

所以我们的比赛再次锚定在线的开头。然后我们有一个(?:...{2}),这意味着偶数次的重复。这是两个子模式的交替。这些子模式代表了我上面提到的步骤。第一个检查当前行中是否有另一个列开始,第二个注册一个计数,并为第一个子模式的另一个应用程序准备引擎状态。因此,对第二种模式进行了控制——第一种模式只是使用前瞻检查另一列,因此是零宽度模式。这就是为什么我不能简单地用包装所有东西,而是必须做{2})的事情——否则零宽度组件只会尝试一次;这是几乎所有引擎都应用的必要优化,以避免无限具有(a*)等模式的循环。

还有一个(非常重要的细节):我使用了(?|…)用于替换。在这种分组中,每个备选方案都以相同的组号开始。因此,在/(?|(a)|(b))/中,可以将ab捕获到组1。这是允许子模式之间“通信”的关键技巧,因为它们可以修改相同的组。

无论如何我们有这两个子模式。我们希望确保它们之间的控制确实是交替的。因此,如果最后一组匹配,每个组都会失败。我们通过将模式包装在一些分组中并引用magic来实现这一点:

^(?:(?|
  (?(5)(?![\s\S]*+\5))       # if group 5 has matched before make sure that
                             # it didn't match empty
  checkForNextColumn         # contains 4 capturing groups
  ()                         # this is group 5, match empty
|
  (?(5)(?=[\s\S]*+\5)|(?!))  # make sure that group 5 is defined and that it
                             # matched empty
  advanceEngineState         # contains 4 capturing groups
  (?=
    ([\s\S])                 # this is group 5, match non-empty
    [\s\S]*                  # advance to the end very end of the string
    ([\s\S] (?(6)\6))             # add a character from the end of the string to
                             # group 6
  )
){2})+

因此,在每个备选方案的末尾,我们将使该备选方案的条件无效,甚至可以开始匹配。在第二个备选方案的末尾,我们还将使用Qtax概述的技术将一个字符包含到组6。这是计数步骤。即,组6包含的字符数与当前行中开始的列数相同。

现在,checkForNextColumn将真正成为Qtax在前瞻中的解决方案。不过它还需要一次修改,为了证明这一点,我们将首先研究advanceEngineState

让我们考虑一下如何修改状态,以便QTC的解决方案匹配一行中的第二列。说我们有输入

..X..X..
..X..X..
..X..X..

我们想找到第二列。这可以通过从第一个X之后的位置开始匹配,并将组\1\2分别初始化为第2行和第3行的前三个字符(.X),而不是空的。

现在,让我们尝试这样做:将所有内容匹配到下一个开始列的X,然后用相应的行前缀填充两个组,以便在checkForNextColumn模式中使用。这也是Qtax的模式,除了我们将X计算在内(而不是在它之前停止),并且我们需要将捕获添加到一个单独的组中。下面是advanceEngineState

(?:
  .
  (?=
    .*+\n
    ( \1? .)
    .*+\n
    ( \2? .)
  )
)+?
(?=
  (?<=X) .*+\n
  (\1)        
  (?<=X) .*+\n
  (\2)        
  (?<=X)
)

请注意,我是如何将X转换为lookbehinds的,以更进一步,以及我如何有效地将\1的最终内容复制到\3中,并将\2的最终内容复制到\4<中。/code>。

因此,如果我们现在在前瞻中使用QTax的解决方案作为check ForNextColiv,使用组\3\4而不是\1\2,我们应该完成了。

但是,我们如何使这些组\3\4而不是\1\2?我们可以使用()()启动模式,该模式将始终匹配,不会影响引擎的光标,但将组计数增加2。但是,这是有问题的:这会将组12重置为空字符串,如果我们找到第二列,advanceEngineState将处于不一致的状态(因为引擎的全局位置已提前,但计数组再次为零)。所以我们想让这两组人进入这个模式,但不影响他们当前捕获的内容。我们可以利用我已经提到的一些东西来实现这一点。NET解决方案:负环视中的组不会影响捕获的内容(因为引擎需要回溯出环视才能继续)。因此,我们可以使用(?!(?!)())(一种永远不会导致模式失败的负前瞻)在模式中包含两组从未使用过的括号。这允许我们在第一个子模式中使用组34,同时在下一次迭代的第二个子模式中保持组12不变。总之,这是检查下一列

(?!(?!)()()) 
(?=
  (?:
    .                  
    (?=                
      .*+\n            
      ( \3? . )   
      .*+\n        
      ( \4? . )    
    )
  )*?              
  X .*+\n          
  \3               
  X .*+\n          
  \4               
)

这在很大程度上看起来很熟悉。

就是这样。对一些输入运行此操作将为我们提供一个组6,其中包含一个捕获,用于每行有一个列开始的位置,并且捕获的长度将告诉我们有多少列从那里开始。

是的,它确实有效(现场演示)。

请注意,这(与基本的.NET解决方案一样)将对长度超过3Xs的列进行过度计数。我认为可以使用lookaheads(类似于完整的.NET解决方案的lookback)来更正此计数,但这将留给读者作为练习。

有点不幸的是,这个解决方案的基本问题已经非常复杂,并且使解决方案变得臃肿(75%的行大多只是QTaxs解决方案的副本)。因为周围的框架有一些非常有趣的技术和经验教训:

  • 我们可以有多个子模式来完成特定的匹配/计数任务,并通过将它们放在一个(?|...)交替和循环。
  • 在将所有内容放入之前,我们可以通过将它们包装在像{2}这样的有限量词中,来强制执行零宽度替换。
  • 可以跳过一个子模式中的组编号(不影响捕获的内容),方法是将它们放入一个永不失败的负前瞻,如(?!(?!)()).
  • 控制可以通过捕获在进入交替时检查的特定组中的某样东西或任何东西在子模式之间来回传递。

这允许进行一些非常强大的计算(我曾看到有人声称PCRE实际上是图灵完全的)——尽管这对于生产性使用来说肯定是错误的方法。但是,在解决问题的过程中,仍然试图理解(并想出)这样的解决方案可能是一个非常具有挑战性的、在某种程度上是有益的练习。