Implémenter glob Matcher

15

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

Ming-Tang
la source
1
Puis-je suggérer un tag supplémentaire "pattern-matching"?
dmckee --- chaton ex-modérateur
1
Pourriez-vous préciser ce que vous entendez par «aucune fonction standard»? Que vous ne pouvez pas appeler des fonctions de la bibliothèque standard? Comment c'est censé fonctionner?
sepp2k
Quelques exemples d'évasion s'il vous plaît? ("\")
Eelvex

Réponses:

4

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.

Nabb
la source
5

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&
MtnViewMark
la source
2

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));
}
Arnaud Le Blanc
la source
2

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

roobs
la source
2

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' 
roobs
la source
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}

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

Arnaud Le Blanc
la source
Je ne connais rien à Ruby, mais grâce à votre code, j'ai appris que l'accès aux indices hors limites renvoie zéro. le fait d'éclater une chaîne vide donne une valeur nulle qui peut être utilisée comme symbole de terminaison de chaîne. Style C! chouette! je suppose que cela pourrait être imité en python en passant chaque chaîne d'entréelambda s : list(s)+[None]
roobs
De son apparence, Ruby a construit une correspondance de motifs. C'est certainement pratique pour ce genre de problème.
Jonathan M Davis
En fait, ce ??sont des caractères littéraux, =>des séparateurs clé / valeur dans Ruby Hashes, et ->démarre un lambda :-) ( { ?? => ->{...} }est un hachage avec clé "?"et un lambda comme valeur.) :-)
Arnaud Le Blanc
2

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));
}
Joey Adams
la source
2

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.

Veuillez vous lever
la source
1

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
Hoa Long Tam
la source
1

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);
}
Jonathan M Davis
la source
1

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
roobs
la source
1

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. :(

Timwi
la source