SORU
11 HAZİRAN 2013, Salı


&; dikey" bir ASCII düzenli ifade eşleştirme "resim""

Not: Bu modern düzenli tatlar olanakları hakkında bir soru. En iyi yolu hakkında bu diğer yöntemleri kullanarak çözmek için değil. an earlier question, ilham, ama o da bir düzenli ifade ile sınırlı değildir.

Sorun

Bir ASCII "resim"/sanat/göster/dizesi gibi:

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

Basit bir dikey çizgi Xs üç: oluşumu bulmak istiyorum

X
X
X

Satır sayısı görüntüde değişken ve genişliğihersatır değişken çok.

Soru(s)

Düzenli ifade (//PHP, Perl, .NET veya benzeri) mümkün:

  1. Eğer böyle bir oluşum varsa
  2. Bu tür oluşumları saymak onları başlangıç noktası Maç (4 örnek yukarıda)

CEVAP
18 HAZİRAN 2013, Salı


Soru 1 için cevap

Demezsim ilk soru için:

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

Bu ifade Perl / Java ile çalışır ve çalışmalıdır .NET.

İfade öz başvuran gruplar ile lookaheads ilerleme her tekrarı için bir karakter eklemek için kullanır (bunun için kullanılır "") say.

\1? \1 (ya da tanımlanır) tüketim eşleşirse anlamına gelir, ve geri (geri verme) verme. Bu durumda (?(1) \1 ) eşdeğer. Eğer \1 tanımlanan \1 maç anlamına gelir.

polygenelubricants his answer for How can we match a^n b^n with Java regex? geribaşvuruların ile lookaheads bu tür çok güzel açıklıyor. (Ayrıca Java düzenli ifade geribaşvuruların ve lookarounds ilgili diğer etkileyici hileler hakkında yazdı.)

Soru 2'ye cevap

Düz eşleşen

Sadece ve eşleşme sayısını cevabı (sayısı) eşleştirme gerektiren kullanırken, soru 2 cevabı olabilir:

Olabilirdeğilsınırlı bir geriye ilerleme var düzenli tatlar doğrudan çözülmesi. Diğer tatlar gibi Java iken .NET m.buettner's .NET solution örneğin gibi).

Böylece düz Perl düzenli ifade maçları ve / (vb PHP) doğrudan bu durumda bu soruya cevap veremez.

(Yarı?)kanıt

Hiçbir değişken uzunlukta geriye ilerleme mevcut olduğunu varsayalım.

Bir hat üzerinde bir şekilde karakter sayısını saymak için X bir önce.
Bunu yapmanın tek yolu onları maç ve değişken uzunluk geriye ilerleme olduğundan bu satırın başına maç (en az) başlamak gerekir.
Eğer bir satır başında maç başlamadan sadece bir en fazla eşleşen satır başına alabilirsiniz.

Her satırda birden çok kez olabilir bu yana, bu hepsini saymak olmaz ve doğru bir cevap verebilir.

Uzunluk/dolaylı çözüm

Eğer bir maç ya da değiştirme sonucu uzunluğu olarak cevap kabul edersek diğer taraftan, 2 soruyanıtlanabilirancak sisteminizde ve Perl (ve diğer tatlar).

Bu çözüm/m.buettner's nice "partial PCRE solution" ilham dayanmaktadır.

Sadece $3 cevap iki (ilgi desenler sayısı) sonuç dizesi uzunluğu olarak soru almak ile aşağıdaki ifadenin eşleşen bir değiştirme olabilir.

^
(?:
    (?:                   # 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 gibi yazılabilir:

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

Online demo

Bu ifade benzer bir çözüm soru 1: yukarıda, bazı değişiklikler vardır X karakterleri eşleşen ilk ilerleme, sarılmış bir nicelik belirteci ve sayma sayısı kibrit nicelik belirteci.

Bu olabildiğince yakın (ekstra kod düzenli ayrıca bilge), soru 2 için kabul edilebilir bir cevap olabilir doğrudan hariç maçlar.

Test çalışmaları

Yukarıdaki çözüm için bazı test çalışmaları ve sonuçları. Dördüncü hakem sonra elde edilen string(ler) parantez içinde sayısal cevap (sonuç dizesi uzunluğu) gösteren ve sonuç.

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)

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • ADDVOiCE

    ADDVOiCE

    28 Mayıs 2009
  • lane182videos

    lane182video

    6 EKİM 2011
  • NightShader1

    NightShader1

    25 Temmuz 2006