Implémentez une fonction de modèle et de chaîne à mettre en correspondance, retournez true si le modèle correspond à la chaîne WHOLE, sinon false.

Notre syntaxe de modèle de glob est:

• ? correspond à n'importe quel caractère
• + correspond à un ou plusieurs caractères
• * correspond à zéro ou plusieurs caractères
• \ s'échappe

Règles:

• Aucun eval, aucune conversion en expression régulière, aucun appel à une fonction glob système.
• Les E / S ne sont pas nécessaires: vous pouvez simplement écrire une fonction
• Victoires les plus courtes

Exemples:

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

Voici une astuce pour commencer: http://en.wikipedia.org/wiki/Backtracking

Golfscript - 82 caractères

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

Suppose qu'il n'y a pas de nouvelle ligne dans les chaînes. Renvoie un tableau vide pour faux et un tableau non vide pour vrai (conforme à la définition golfscript de vrai / faux).

Il s'agit d'une solution non récursive (à l'exception des *s consécutifs ), qui conserve une liste des positions dans la chaîne de modèle itelles qu'elles pattern[0..i]correspondent string[0..cur].

Cela a le potentiel de fonctionner très longtemps. Vous pouvez ajouter .&après :C%pour éviter cela.

Haskell, 141 caractères

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

Fonctionne pour toutes les entrées, les modèles et les chaînes à comparer. Gère la barre oblique inverse de fin dans le modèle comme une correspondance littérale (le comportement n'était pas spécifié.)

Cela peut être exécuté avec le pilote de test suivant:

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

Mise à jour: J'ai écrit un blog sur cette réponse particulière, car je pense que cela montre bien comment Haskell code si facilement le problème.

• Edit: (181 -> 174) remplacé det mavec des opérateurs
• Modifier: (174 -> 151) ren ligne dansc
• Modifier: (151 -> 149) a supprimé une option générée inutilement dans le +cas
• Edit: (149 -> 141) a supprimé une clause inutile pour %, qui a été gérée par&

PHP - 275 243 caractères

<?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;}

Non golfé:

<?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));
}

Python trop verbeux ( 384 367 caractères)

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)

Ce n'est pas le plus court, mais c'est agréable et fonctionnel. La chose du dict d'expédition au milieu pourrait vraisemblablement être réécrite comme une disjonction sur (h(p) == '?') and (? lambda body)les choses de type. Définir que l'opérateur h me coûte quelques caractères sans aucun avantage, mais c'est bien d'avoir un mot-clé pour head.

J'aimerais avoir une fissure au golf en l'écrivant plus tard si le temps le permet.

edit: suppression de la troisième branche inutile dans le cas '*' après avoir lu la réponse ruby ​​de user300

Shorter Snappier Python 2.6 (272 caractères)

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])

non golfé:

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))

avec:

• désordre logique paresseusement évalué!
• Cordes de style C!
• idiome de comparaison multiple mignon!
• beaucoup de laid!

crédit à la réponse de user300 pour avoir illustré comment les choses sont simplifiées si vous pouvez obtenir une sorte de valeur de terminateur lorsque vous sautez la tête d'une chaîne vide.

je souhaite que le déballage tête / queue puisse être effectué en ligne lors de la déclaration des arguments de m. alors m pourrait être un lambda, tout comme ses amis n et glob. python2 ne peut pas le faire, et après un peu de lecture, il semble que python3 ne puisse pas non plus. malheur.

essai:

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' 

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}

Non golfé:

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

Tests:

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('+', '')

Inspiré par la réponse des roobs

Fonction C - 178 caractères nécessaires

Compilé avec GCC, cela ne produit aucun avertissement.

#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

La première et la dernière ligne ne sont pas incluses dans le nombre de caractères. Ils sont fournis à titre indicatif uniquement.

Explosé:

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));
}

JavaScript - 259 caractères

Mon implémentation est très récursive, donc la pile débordera si un modèle extrêmement long est utilisé. Ignorant le signe plus (que j'aurais pu optimiser mais choisi de ne pas utiliser pour des raisons de simplicité), un niveau de récursivité est utilisé pour chaque jeton.

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)))}

La fonction renvoie parfois un nombre au lieu d'un booléen. Si c'est un problème, vous pouvez l'utiliser comme !!glob(pattern, str).

Non golfé (non minimisé, plutôt) pour servir de ressource utile:

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)));
}

Notez que l'indexation en caractères d'une chaîne comme pour les éléments de tableau ne fait pas partie de la norme de langage plus ancienne (ECMAScript 3), donc elle peut ne pas fonctionner dans les navigateurs plus anciens.

Python (454 caractères)

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

D: 363 caractères

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);}

Plus lisiblement:

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);
}

golfscript

{{;;}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;

il est construit à partir de fonctions qui consomment deux arguments de la pile, s et p, et produisent une seule valeur de retour booléenne. il y a un peu de nettoyage pour le rendre compatible avec les opérateurs paresseux et et paresseux ou. je doute vraiment que cette approche soit presque optimale, voire dans la bonne direction.

il y a aussi quelques moments amusants et stupides, comme sauter un '*'modèle, consommer le '*'dans une comparaison, seulement pour réaliser que la branche suivante ne correspond pas. afin de descendre l'autre branche, nous avons besoin du motif avec le '*'devant, mais nous avons consommé ce motif original lorsque nous avons sauté le '*', et nous avons consommé le '*', donc pour obtenir à nouveau le motif, nous chargeons une nouvelle chaîne brillante constante '*', et ajoutez-la en place. cela devient encore plus laid parce que pour une raison quelconque, la correspondance des caractères doit être effectuée avec des valeurs ascii, mais le retour au début dans la chaîne nécessite des chaînes.

golfscript moins 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;

tests

{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

C # (251 caractères)

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;}}

Un peu plus lisible:

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; }
}

_{^† Je sais, je sais ... sauf pour les globes contenant la barre oblique inverse. Ce qui est vraiment regrettable. Cela aurait été vraiment intelligent autrement. :(}