php - 옵션 - ASCII "이미지"에서 "수직"정규식 매칭




regex modifier (4)

질문 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

온라인 데모

이 표현식은 Perl, PCRE, Java에서 작동하며 .NET에서 작동해야합니다.

이 표현식은 미리보기의 반복마다 문자를 추가하기 위해 자기 참조하는 캡처 그룹과 함께 미리보기를 사용합니다 (이것은 "계산"에 사용됩니다).

\1?+\1 일치하거나 (또는 ​​정의 된) \1 이 그것을 소비하고 그것을 되돌려주지 않는다는 것을 의미합니다 (되돌아 가지 않습니다). 이 경우 (?(1) \1 ) . \1 이 정의되면 \1 의미합니다.

polygenelubricants 는 우리가 ^ nb ^ n을 Java 정규식과 어떻게 일치시킬 수 polygenelubricants 에 대한 그의 답변 에서 이러한 종류의 역 참조를 매우 잘 설명합니다 . . (그는 역 참조와 둘러보기가 포함 된 Java 정규 표현식에 대한 다른 놀라운 트릭에 대해서도 작성했습니다.)

질문 2에 응답하십시오.

일반 일치

매칭을 사용하고 매치 횟수에서 대답 (카운트)을 요구할 때, 질문 2의 답은 다음과 같습니다 :

그것은 lookbehind가 제한된 regex flavors에서 직접 해결할 수 없습니다 . Java 및 .NET과 같은 다른 기능도 있습니다 (예 : m.buettner의 .NET 솔루션 ).

따라서 펄의 정규식 정규식과 PCRE (PHP 등)는이 경우이 질문에 직접 대답 할 수 없습니다.

(준?) 증명

가변 길이 lookbehind를 사용할 수 없다고 가정합니다.

어떤 식으로 X 앞에 한 줄에있는 문자의 수를 계산해야합니다.
그렇게하는 유일한 방법은 일치시키는 것입니다. 가변 길이 lookbehind를 사용할 수 없으므로 적어도 줄의 시작 부분에서 일치를 시작해야합니다.
한 줄의 시작 부분에서 일치 항목을 시작하면 한 줄에 하나의 일치 항목 만 얻을 수 있습니다.

한 줄에 여러 번 나타날 수 있기 때문에 모두 계산되지 않을 것이고 정답을주지 못할 것입니다.

길이 / 간접 해법

반면에 일치 또는 대체 결과의 길이로 대답을 수락하면 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;

온라인 데모

이 표현식은 첫 번째 미리보기에서 일치하는 문자에 X 를 포함하고 한정 기호로 싸고 한정 기호와 일치하는 개수를 계산하도록 일부 수정하여 위의 질문 1에 대한 해결책과 비슷합니다.

직접적인 일치는 제외하고 이것은 정규식 외에도 추가 코드가 현명한만큼 가까우며 질문 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)

참고 : 이것은 현대 정규식의 가능성에 대한 질문입니다. 다른 방법을 사용하여이 문제를 해결하는 것이 가장 좋은 방법은 아닙니다. 이전 질문 에서 영감을 얻었지만 정규 표현식에만 국한되지는 않습니다.

문제

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)

편집하다

다음 솔루션에는 두 가지 중대한 문제가 있습니다.

  1. pos 너무 많이 진행됨에 따라 동일한 행에서 시작하는 여러 개의 XXX 시퀀스와 일치 할 수 없습니다.
  2. 두 번째 해결 방법은 올바르지 않습니다. 두 개의 X 가 서로 위에있는 연속적인 줄과 일치합니다. 꼭 3 번 연속 될 필요는 없습니다.

따라서 모든 upvotes (및 현상금)는 m.buettner 의 포괄적 인 .NET 응답 또는 자신의 매혹적인 PCRE 응답 중 하나에 가야합니다.

원문 답변

이것은 Perl 코드를 regexes에 임베드하는 방법입니다. Perl 정규 표현식은 코드를 사용하여 정규 표현식 내에서 임의의 조건을 지정하거나 부분 정규 표현식을 내보낼 수 있지만 일반 언어 또는 컨텍스트 프리 언어와 일치하는 것은 아니지만 Chomsky 계층 구조에서 상위 부분의 언어와 일치 할 수 있습니다.

일치시키려는 언어는 다음과 같이 정규식 용어로 설명 할 수 있습니다.

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

여기서 n 은 숫자입니다. 이는 상황에 민감한 언어의 표준적인 예인 a n b n c n 언어와 일치하는 것만큼이나 복잡합니다.

우리는 첫 번째 줄을 쉽게 매치 할 수 있고, 다른 줄에 대한 정규식을 내기 위해 몇 가지 Perl 코드를 사용할 수 있습니다.

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

그것은 짧았다! 그것은 무엇을합니까?

  • ^ (.*?) X 는 행의 시작 부분에 앵커하고 가능한 한 개행 문자가 아닌 문자를 일치시킨 다음 ^ (.*?) X 찾습니다. 캡쳐 그룹 $1X 까지의 라인을 기억합니다.

  • 우리는 나머지 두 줄인 개행과 일치하는 그룹을 두 번 반복 한 다음 $1 과 같은 길이의 문자열과 일치하는 정규식을 삽입합니다. 그 후에 X 가 있어야합니다.

이 정규식은 이제 서로 위에 세 개의 X 가있는 모든 문자열과 일치합니다.

우리가 그러한 모든 시퀀스를 추출하고자한다면, 우리는 멋지게 될 것입니다. 시퀀스가 겹칠 수 있으므로

.X
XX
XX
X.

다음 경기가 시작되는 위치가 첫 번째 X 지나서는 안됩니다. 우리는 lookinhind와 lookahead를 통해 이것을 할 수 있습니다. Perl은 고정 길이 lookbehind 만 지원하지만 비슷한 의미를 제공하는 \K 이스케이프가 있습니다. 그러므로

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

세 개의 수직 X es의 모든 시퀀스와 일치합니다. 테스트 시간 :

$ 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 :

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

라인의 시작 부분에 앵커를 고정하면 두 개의 수직 X 일치시킬 수 있습니다. 두 개 이상의 행을 매치시키기 위해서는 미리보기에서 재귀를 수행 한 다음 매치 위치를 다음 행으로 넘어 가서 반복해야합니다. 이를 위해 간단히 일치 .*\n .

결과적으로 세 개의 수직 X 와 문자열을 일치시킬 수있는 다음 정규식이됩니다.

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

그러나 이러한 모든 시퀀스를 일치시키려는 경우에는 충분하지 않습니다. 이렇게하기 위해, 우리는 본질적으로 전체 정규식을 미리보기 (lookahead)에 넣었습니다. 정규식 엔진은 항상 매치를 생성하여 새로운 매치를 생성합니다.

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

그래서 이것은 코드가 삽입 된 솔루션과 마찬가지로 작동합니다. 즉, X es의 각 그룹이 아닌 수직 X es와 각 라인 그룹을 일치시킵니다. (사실,이 솔루션은 임베디드 코드보다 내게 취약하다.)


If you want to find a single "vertical" pattern, here's a solution. If you want to also match a "horizontal" pattern, try doing it with a separate match, perhaps checking for overlapping match positions. Remember that the computer has not idea what a line is. It's an arbitrary thing made up by humans. The string is just a one-dimensional sequence where we denote some character(s) to be a line ending.

#!/usr/local/perls/perl-5.18.0/bin/perl
use v5.10;

my $pattern = qr/XXX/p;

my $string =<<'HERE';
....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....
HERE


$transposed = transpose_string( $string );

open my $tfh, '<', \ $transposed;
while( <$tfh> ) {
    while( /$pattern/g ) {
        my $pos = pos() - length( ${^MATCH} );
        push @found, { row => $pos, col => $. - 1 };
        pos = $pos + 1; # for overlapping matches
        }
    }

# row and col are 0 based
print Dumper( \@found ); use Data::Dumper;

sub transpose_string {
    my( $string ) = @_;

    open my $sfh, '<', \ $string;

    my @transposed;
    while( <$sfh> ) {
        state $row = 0;
        chomp;
        my @chars = split //;

        while( my( $col, $char ) = each @chars ) {
            $transposed[$col][$row] = $char;
            }

        $row++;
        }

    my @line_end_positions = ( 0 );
    foreach my $col ( 0 .. $#transposed ) {
        $transposed .= join '', @{ $transposed[$col] };
        $transposed .= "\n";
        }
    close $sfh;

    return $transposed;
    }

My approach to match vertical patterns using PHP.

First of all, let's rotate our input by 90°:

// assuming $input contains your string
$input = explode("\n", $input);
$rotated = array();
foreach ($input as $line)
{
    $l = strlen($line);
    for ($i = 0; $i < $l; $i++)
    {
        if (isset($rotated[$i]))
            $rotated[$i] .= $line[$i];
        else
            $rotated[$i] = $line[$i];
    }
}
$rotated = implode("\n", $rotated);

This results in

..XXX.....
..........
.XX....XX.
....X.....
X...X....X
.X.XXX....
..XX......
...X......
...X......
.XXX......
...X.....
.........
........
........
....XXX
.....
...
..
..
X
.
.
.

Now this might look strange, but actually brings us closer since we can now simply preg_match_all() over it:

if (preg_match_all('/\bXXX\b/', $rotated, $m))
var_dump($m[0]);

et voila:

array(4) {
  [0] =>
  string(3) "XXX"
  [1] =>
  string(3) "XXX"
  [2] =>
  string(3) "XXX"
  [3] =>
  string(3) "XXX"
}

If you also want to match the same horizontal pattern, simply use the same expression on the non-rotated input.







pcre