Terapkan glob Matcher

15

Menerapkan fungsi pola dan string yang akan dicocokkan, mengembalikan true jika pola cocok dengan string WHOLE, jika tidak palsu.

Sintaks pola glob kami adalah:

  • ? cocok dengan satu karakter
  • + cocok dengan satu atau lebih karakter
  • * cocok dengan nol atau lebih karakter
  • \ lolos

Aturan:

  • Tidak ada eval, tidak ada konversi menjadi ekspresi reguler, tidak ada panggilan fungsi sistem glob.
  • I / O tidak diperlukan: Anda cukup menulis fungsi
  • Kemenangan terpendek

Contoh:

glob('abc', 'abc') => true
glob('abc', 'abcdef') => false IMPORTANT!
glob('a??', 'aww') => true
glob('a*b', 'ab') => true
glob('a*b', 'agwijgwbgioeb') => true
glob('a*?', 'a') => false
glob('?*', 'def') => true
glob('5+', '5ggggg') => true
glob('+', '') => false
glob('a\*b', 'a*b') => true

Berikut ini tip untuk memulai: http://en.wikipedia.org/wiki/Backtracking

Ming-Tang
sumber
1
Bolehkah saya menyarankan tag tambahan "pencocokan pola"?
dmckee --- ex-moderator kitten
1
Bisakah Anda mengklarifikasi apa yang Anda maksud dengan "tidak ada fungsi standar"? Bahwa Anda tidak dapat memanggil fungsi dari perpustakaan standar? Bagaimana cara kerjanya?
sepp2k
Beberapa contoh untuk melarikan diri? ("\")
Eelvex

Jawaban:

4

Golfscript - 82 karakter

{1,\@n+:|;{:<;{:I)I|="\\+*?"[<]+?[{|=<={I))}*}I~{I\C}{}.{;}]=~}:C%}/{|>'*'-n=},}:g

Asumsikan bahwa tidak ada baris baru di string. Mengembalikan array kosong untuk false, dan array tidak kosong untuk true (konsisten dengan definisi skrip golf true / false).

Ini adalah solusi non-rekursif (kecuali untuk berturut-turut *), yang memelihara daftar posisi dalam string pola isedemikian rupa sehingga pattern[0..i]cocok string[0..cur].

Ini memiliki potensi untuk berjalan untuk waktu yang sangat lama. Anda dapat menambahkan .&setelah :C%untuk mencegah ini.

Nabb
sumber
5

Haskell, 141 karakter

c('\\':a:z)s=a&s>>=c z
c(a:z)s=a%s>>=c z
c[]s=[null s]
p&(a:z)|a==p=[z]
_&_=[]
'?'%(a:z)=[z]
'*'%a=a:'+'%a
'+'%(a:z)='*'%z
l%a=l&a
g=(or.).c

Berfungsi untuk semua input, baik pola dan string yang cocok. Menangani trailing backslash dalam pola sebagai kecocokan literal (perilaku tidak ditentukan.)

Ini dapat dijalankan dengan driver tes berikut:

main = do
    globtest "abc" "abc"    True
    globtest "abc" "abcdef" False
    globtest "a??" "aww"    True
    globtest "a*b" "ab"     True
    globtest "a*b" "agwijgwbgioeb" True
    globtest "a*?" "a"      False
    globtest "?*" "def"     True
    globtest "5+" "5ggggg"  True
    globtest "+" ""         False
    globtest "a\\*b" "a*b"  True
  where
    globtest p s e =
      if g p s == e
        then putStrLn "pass"
        else putStrLn$"fail: g " ++ show p ++ " " ++ show s ++ " /= " ++ show e

Pembaruan: Saya menulis posting blog tentang jawaban khusus ini, karena saya pikir itu menunjukkan dengan baik bagaimana Haskell dengan mudah mengkodekan masalah.


  • Sunting: (181 -> 174) diganti ddan mdengan operator
  • Sunting: (174 -> 151) sebaris rdalamc
  • Sunting: (151 -> 149) menghapus opsi yang dibuat tidak perlu dalam +kasus ini
  • Sunting: (149 -> 141) menghapus klausa yang tidak perlu untuk %, yang ditangani oleh&
MtnViewMark
sumber
2

PHP - 275 243 karakter

<?function g($P,$I){$o='array_shift';if(@$I[0]==="")return 0;for(;$P;$o($P)){$p=$P[0];if($p=='?'|$p=='+'&&@$N===$o($I))return 0;if($p=='+'|$p=='*'&&$I&&g($P,array_slice($I,1)))return 1;if(!strpos(" ?+*\\",$p)&&$p!==$o($I))return 0;}return!$I;}

Tidak Disatukan:

<?php

function g($P,$I) {
        if ($I && $I[0] === "") return false;
        for(;$P;array_shift($P)) {
                $p = $P[0];
                if( $p == '?' || $p == '+') {
                        if (NULL === array_shift($I)) {
                                return false;
                        }
                }
                if( $p=='+' || $p=='*' ) {
                        if ($I && g($P, array_slice($I,1))) {
                                return true;
                        }
                }
                if (!strpos(" ?+*\\",$p) && $p !== array_shift($I)) {
                        return false;
                }
        }
        return !$I;
}

function my_glob($pattern,$subject) {
    return !!g(str_split($pattern),str_split($subject));
}
Arnaud Le Blanc
sumber
2

Overly Verbose Python ( 384 367 Karakter)

t=lambda a:a[1:] 
h=lambda a:a[0] 
n=lambda p,s:s and(h(p)==h(s)and m(t(p),t(s))) 
def m(p,s): 
 if not p: 
  return not s 
 else: 
  return { 
   '?':lambda p,s:s and m(t(p),t(s)), 
   '+':lambda p,s:s and(m(p,t(s))or m(t(p),t(s))), 
   '*':lambda p,s:m(t(p),s)or(s and m(p,t(s))), 
   '\\':lambda p,s:n(t(p),s), 
  }.get(h(p),n)(p,s) 
glob=lambda p,s:not not m(p,s)

Ini bukan yang terpendek, tapi itu bagus dan fungsional. Hal dict pengiriman di tengah mungkin bisa ditulis ulang sebagai disjungsi atas (h(p) == '?') and (? lambda body)hal-hal jenis. Menentukan bahwa operator h membebani saya beberapa karakter tanpa manfaat, tetapi menyenangkan untuk memiliki kata kunci untuk kepala.

Saya ingin memiliki celah di skrip golf nanti jika waktu mengizinkan.

sunting: menghapus cabang ketiga yang tidak perlu dalam kasus '*' setelah membaca jawaban ruby ​​user300

gelandangan
sumber
2

Snappier Python 2.6 (272 karakter), Shorter

golf:

n=lambda p,s:p[0]==s[0]and m(p[1:],s[1:]) 
def m(p,s): 
 q,r,t,u=p[0],p[1:],s[0],s[1:] 
 return any((q=='?'and(t and m(r,u)),q=='+'and(t and(m(p,u)or m(r,u))),q=='*'and(m(r,s)or(t and m(p,u))),q=='\\'and n(r,s),q==t==0))or n(p,s) 
glob=lambda*a:m(*[list(x)+[0]for x in a])

ungolfed:

TERMINATOR = 0 

def unpack(a): 
    return a[0], a[1:] 

def terminated_string(s): 
    return list(s) + [TERMINATOR] 

def match_literal(p, s): 
    p_head, p_tail = unpack(p) 
    s_head, s_tail = unpack(s) 
    return p_head == s_head and match(p_tail, s_tail) 

def match(p, s): 
    p_head, p_tail = unpack(p) 
    s_head, s_tail = unpack(s) 
    return any(( 
        p_head == '?' and (s_head and match(p_tail, s_tail)), 
        p_head == '+' and (s_head and(match(p, s_tail) or match(p_tail, s_tail))), 
        p_head == '*' and (match(p_tail, s) or (s_head and match(p, s_tail))), 
        p_head == '\\' and match_literal(p_tail, s), 
        p_head == s_head == TERMINATOR, 
    )) or match_literal(p, s) 

def glob(p, s): 
    return match(terminated_string(p), terminated_string(s))

menampilkan:

  • kekacauan logis malas-dievaluasi!
  • String gaya C!
  • idiom beberapa perbandingan lucu!
  • banyak yang jelek!

kredit untuk jawaban user300 untuk menggambarkan bagaimana hal-hal disederhanakan jika Anda bisa mendapatkan semacam nilai terminator ketika muncul kepala dari string kosong.

Saya berharap kepala / ekor membongkar dapat dilakukan inline selama deklarasi argumen m. maka m bisa menjadi lambda, sama seperti teman-temannya n dan glob. python2 tidak bisa melakukannya, dan setelah sedikit membaca, sepertinya python3 juga tidak bisa. duka.

pengujian:

test_cases = { 
    ('abc', 'abc') : True, 
    ('abc', 'abcdef') : False, 
    ('a??', 'aww') : True, 
    ('a*b', 'ab') : True, 
    ('a*b', 'aqwghfkjdfgshkfsfddsobbob') : True, 
    ('a*?', 'a') : False, 
    ('?*', 'def') : True, 
    ('5+', '5ggggg') : True, 
    ('+', '') : False, 
}   
for (p, s) in test_cases: 
    computed_result = glob(p, s) 
    desired_result = test_cases[(p, s)] 
    print '%s %s' % (p, s) 
    print '\tPASS' if (computed_result == desired_result) else '\tFAIL' 
gelandangan
sumber
2

Ruby - 199 171

g=->p,s{x=(b=->a{a[1..-1]})[p];y=s[0];w=b[s];v=p[0];_=->p,s{p[0]==y&&g[x,w]}
v==??? g[x,y&&w||s]:v==?+? y&&g[?*+x,w]:v==?*?
y&&g[p,w]||g[x,s]:v==?\\? _[x,s]:v ? _[p,s]:!y}

Tidak Disatukan:

def glob(pattern, subject)
        b=->a{a[1..-1]}
        _=->p,s{ p[0]==s[0] && glob(b[p],b[s]) }
        ({
                ??=>->p,s { glob(b[p], s[0] ? b[s] : s) },
                ?+=>->p,s { s[0] && glob(?*+b[p], b[s]) },
                ?*=>->p,s { s[0] && glob(p,b[s]) || glob(b[p],s) },
                ?\\=>->p,s{ _[b[p],s] },
                nil=>->p,s{ !subject[0] }
        }[pattern[0]] || _)[pattern, subject]
end

Tes:

p glob('abc', 'abc')
p glob('abc', 'abcdef')
p glob('a??', 'aww')
p glob('a*b', 'ab')
p glob('a*b', 'agwijgwbgioeb')
p glob('a*?', 'a')
p glob('?*', 'def')
p glob('5+', '5ggggg')
p glob('+', '')

Terinspirasi oleh jawaban roobs

Arnaud Le Blanc
sumber
saya tidak tahu apa-apa tentang ruby, tetapi dari kode Anda, saya sudah belajar bahwa mengakses di luar batas indeks mengembalikan nol. jadi muncul string kosong menghasilkan nilai nil yang dapat digunakan sebagai simbol terminator string. Gaya-C! bagus! Saya kira itu bisa ditiru dalam python dengan melewati setiap string input melaluilambda s : list(s)+[None]
roobs
Dari tampilannya, Ruby memiliki pola yang cocok. Itu tentu berguna untuk masalah semacam ini.
Jonathan M Davis
Sebenarnya ??karakter literal, =>pemisah kunci / nilai dalam Ruby Hash, dan ->memulai lambda :-) ( { ?? => ->{...} }adalah hash dengan kunci "?"dan lambda sebagai nilai.) Tapi ya cara penggunaannya yang sama terlihat seperti pencocokan pola pada karakter tunggal :-)
Arnaud Le Blanc
2

Fungsi C - 178 karakter yang diperlukan

Dikompilasi dengan GCC, ini tidak menghasilkan peringatan.

#define g glob
int g(p,s)const char*p,*s;{return*p==42?g(p+1,s)||(*s&&g(p,
s+1)):*p==43?*s&&(g(p+1,++s)||g(p,s)):*p==63?*s&&g(p+1,s+1)
:*p==92?*++p&&*s++==*p++&&g(p,s):*s==*p++&&(!*s++||g(p,s));}
#undef g

Baris pertama dan terakhir tidak termasuk dalam jumlah karakter. Mereka disediakan hanya untuk kenyamanan.

Diledakkan:

int glob(p,s)
const char *p, *s; /* K&R-style function declaration */
{
    return
        *p=='*'  ? glob(p+1,s) || (*s && glob(p,s+1)) :
        *p=='+'  ? *s && (glob(p+1,++s) || glob(p,s)) :
        *p=='?'  ? *s && glob(p+1,s+1)                :
        *p=='\\' ? *++p && *s++==*p++ && glob(p,s)    :
        *s==*p++ && (!*s++ || glob(p,s));
}
Joey Adams
sumber
2

JavaScript - 259 karakter

Implementasi saya sangat rekursif, sehingga tumpukan akan meluap jika pola yang sangat panjang digunakan. Mengabaikan tanda plus (yang bisa saya optimalkan tetapi memilih untuk tidak kesederhanaan), satu tingkat rekursi digunakan untuk setiap token.

glob=function f(e,c){var b=e[0],d=e.slice(1),g=c.length;if(b=="+")return f("?*"+d,c);if(b=="?")b=g;else if(b=="*"){for(b=0;b<=g;++b)if(f(d,c.slice(b)))return 1;return 0}else{if(b=="\\"){b=e[1];d=e.slice(2)}b=b==c[0]}return b&&(!d.length&&!g||f(d,c.slice(1)))}

Fungsi ini terkadang mengembalikan nomor alih-alih boolean. Jika itu masalah, Anda dapat menggunakannya sebagai !!glob(pattern, str).


Tidak digabungkan (tidak ditambang, lebih tepatnya) untuk berfungsi sebagai sumber daya yang berguna:

function glob(pattern, str) {
    var head = pattern[0], tail = pattern.slice(1), strLen = str.length, matched;
    if(head == '+') {
        // The plus is really just syntactic sugar.
        return glob('?*' + tail, str);
    }
    if(head == '?') { // Match any single character
        matched = strLen;
    } else if(head == '*') { // Match zero or more characters.
        // N.B. I reuse the variable matched to save space.
        for(matched = 0; matched <= strLen; ++matched) {
            if(glob(tail, str.slice(matched))) {
                return 1;
            }
        }
        return 0;
    } else { // Match a literal character
        if(head == '\\') { // Handle escaping
            head = pattern[1];
            tail = pattern.slice(2);
        }
        matched = head == str[0];
    }
    return matched && ((!tail.length && !strLen) || glob(tail, str.slice(1)));
}

Perhatikan bahwa pengindeksan ke karakter string sebagai untuk elemen array bukan bagian dari standar bahasa yang lebih lama (ECMAScript 3), jadi itu mungkin tidak berfungsi di browser lama.

PleaseStand
sumber
1

Python (454 karakter)

def glob(p,s):
  ps,pns=[0],[]
  for ch in s:
    for i in ps:
      if i<0:
        pns+=[i]
        if i>-len(p) and p[-i]==ch:pns+=[-i]
      elif i<len(p):
        pc=p[i]
        d={'?':[i+1],'+':[i,-i-1],'*':[i+1,-i-1]}
        if pc in d:pns+=d[pc]
        else:
          if pc=='\\':pc=p[i+1]
          if pc==ch:pns+=[i+1]
    ps,pns=pns,[]
  if (s or p in '*') and (len(p) in ps or -len(p)+1 in ps or -len(p) in ps): return True
  return False
Hoa Long Tam
sumber
1

D: 363 Karakter

bool glob(S)(S s,S t){alias front f;alias popFront p;alias empty e;while(!e(s)&&!e(t)){switch(f(s)){case'+':if(e(t))return false;p(t);case'*':p(s);if(e(s))return true;if(f(s)!='+'&&f(s)!='*'){for(;!e(t);p(t)){if(f(s)==f(t)&&glob(s,t))return true;}}break;case'\\':p(s);if(e(s))return false;default:if(f(s)!=f(s))return false;case'?':p(s);p(t);}}return e(s)&&e(t);}

Lebih Jelas:

bool glob(S)(S s, S t)
{
    alias front f;
    alias popFront p;
    alias empty e;

    while(!e(s) && !e(t))
    {
        switch(f(s))
        {
            case '+':
                if(e(t))
                    return false;

                p(t);
            case '*':
                p(s);

                if(e(s))
                    return true;

                if(f(s) != '+' && f(s) != '*')
                {
                    for(; !e(t); p(t))
                    {
                        if(f(s) == f(t) && glob(s, t))
                            return true;
                    }
                }

                break;
            case '\\':
                p(s);

                if(e(s))
                    return false;
            default:
                if(f(s) != f(s))
                    return false;
            case '?':
                p(s);
                p(t);
        }
    }

    return e(s) && e(t);
}
Jonathan M Davis
sumber
1

skrip golf

{{;;}2$+}:x;{x if}:a;{x\if}:o;{1$1$}:b;{(@(@={\m}a}:r;{b(63={\({\m}a}a{b(43={\({\b m{'+'\+m}o}a}a{b(42={b m{\({\'*'\+m}a}o}a{b(92={r}a{b 0=0=\0=0=*{r}o}o}o}o}o}:m;{[0]+\[0]+m}:glob;

itu dibangun dari fungsi yang mengkonsumsi dua argumen dari stack, s dan p, dan menghasilkan nilai balik boolean tunggal. ada sedikit mucking untuk membuat yang kompatibel dengan operator dan malas. Saya sangat meragukan pendekatan ini mendekati optimal, atau bahkan ke arah yang benar.

ada juga beberapa momen bodoh yang menghibur, seperti muncul '*'pola, mengkonsumsi '*'dalam perbandingan, hanya untuk menyadari bahwa cabang berikutnya tidak cocok. untuk turun ke cabang lain, kita membutuhkan pola dengan '*'di bagian depan, tetapi kita telah mengkonsumsi pola asli ketika kita muncul '*', dan kita mengkonsumsi '*', jadi untuk mendapatkan diri kita sendiri pola lagi kita memuat string baru yang mengkilap konstan'*' , dan tambahkan di tempat. itu menjadi lebih buruk karena untuk beberapa alasan pencocokan karakter harus dilakukan dengan nilai ascii, tetapi dengan menambahkan kembali ke string membutuhkan string.

skrip golf kurang golf

{[0]+}:terminate_string;
{{;;}2$+if}:_and;
{{;;}2$+\if}:_or;
{1$1$}:branch;
{(@(@={\match}_and}:match_literal;
{0=0=\0=0=*}:match_terminator;
{(92={match_literal}_and}:match_escape;
{(63={\({\match}_and}_and}:match_wildcard;
{(43={\({\branch match{'+'\+match}_or}_and}_and}:match_wildcard_plus;
{(42={branch match{\({\'*'\+match}_and}_or}_and}:match_wildcard_star;
{branch match_wildcard{branch match_wildcard_plus{branch match_wildcard_star{branch match_escape{branch match_terminator{match_literal}_or}_or}_or}_or}_or}:match;
{terminate_string\terminate_string match}:glob;

tes

{2$2$glob = "test passed: " "test FAILED: " if print \ print ' ; ' print print "\n" print}:test_case;

'abc' 'abc' 1 test_case
'abc' 'abcdef' 0 test_case
'a??' 'aww' 1 test_case
'a*b' 'ab' 1 test_case
'a*b' 'agwijgwbgioeb' 1 test_case
'a*?' 'a' 0 test_case
'?*' 'def' 1 test_case
'5+' '5ggggg' 1 test_case
'+' '' 0 test_case
gelandangan
sumber
1

C # (251 karakter)

static bool g(string p,string i){try{char c;System.Func<string,string>s=t=>t.Remove(0,1);return p==i||((c=p[0])==92?p[1]==i[0]&g(s(s(p)),s(i)):c==42?g(s(p),i)||g(p,s(i)):c==43?g(s(p),s(i))|g(p,s(i)):g(s(p),s(i))&(c==i[0]|c==63));}catch{return false;}}

Sedikit lebih mudah dibaca:

static bool g(string p /* pattern */, string i /* input string */)
{
    // Instead of checking whether we’ve reached the end of the string, just
    // catch the out-of-range exception thrown by the string indexing operator
    try
    {
        char c;

        // .Remove(0,1) is shorter than .Substring(1)...
        System.Func<string, string> s = t => t.Remove(0, 1);

        // Note that every glob matches itself!† This saves us having to write
        // “(p=="" & i=="")” which would be much longer — very convenient!
        return p == i || (

            // backslash escapes
            (c = p[0]) == 92 ? p[1] == i[0] & g(s(s(p)), s(i)) :

            // '*' — need “||” so that s(i) doesn’t throw if the first part is true
            c == 42 ? g(s(p), i) || g(p, s(i)) :

            // '+'
            c == 43 ? g(s(p), s(i)) | g(p, s(i)) :

            // '?' or any other character
            g(s(p), s(i)) & (c == i[0] | c == 63)
        );
    }

    // If we ever access beyond the end of the string, we know the glob doesn’t match
    catch { return false; }
}

Saya tahu, saya tahu ... kecuali untuk gumpalan yang mengandung garis miring terbalik. Sangat disayangkan. Kalau tidak begitu, akan sangat pintar. :(

Timwi
sumber