Implementar glob Matcher

15

Implemente una función de patrón y cadena para que coincida, devuelva verdadero si el patrón coincide con la cadena ENTERA, de lo contrario es falso.

Nuestra sintaxis de patrón glob es:

  • ? coincide con cualquier personaje
  • + coincide con uno o más personajes
  • * coincide con cero o más caracteres
  • \ escapa

Reglas:

  • Sin evaluación, sin conversión en expresión regular, sin llamar a una función global del sistema.
  • No se requieren E / S: solo puede escribir una función
  • Victorias más cortas

Ejemplos:

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

Aquí hay un consejo para comenzar: http://en.wikipedia.org/wiki/Backtracking

Ming-Tang
fuente
1
¿Puedo sugerir una etiqueta adicional "coincidencia de patrones"?
dmckee --- ex-gatito moderador
1
¿Podría aclarar lo que quiere decir con "sin función estándar"? ¿Que no puedes llamar a funciones desde la biblioteca estándar? ¿Cómo se supone que funciona?
sepp2k
¿Algunos ejemplos para escapar, por favor? ("\")
Eelvex

Respuestas:

4

Golfscript - 82 caracteres

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

Asume que no hay líneas nuevas en las cadenas. Devuelve una matriz vacía para falso y una matriz no vacía para verdadero (consistente con la definición de golfscript de verdadero / falso).

Esta es una solución no recursiva (excepto para *s consecutivas ), que mantiene una lista de las posiciones en la cadena del patrón de imanera que pattern[0..i]coincida string[0..cur].

Esto tiene el potencial de funcionar durante mucho tiempo. Puede agregar .&después :C%para evitar esto.

Nabb
fuente
5

Haskell, 141 personajes

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

Funciona para todas las entradas, tanto patrones como cadenas para comparar. Maneja la barra diagonal inversa posterior en el patrón como una coincidencia literal (el comportamiento no se especificó).

Esto se puede ejecutar con el siguiente controlador de prueba:

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

Actualización: escribí una publicación de blog sobre esta respuesta en particular, ya que creo que muestra bien cómo Haskell codifica tan fácilmente el problema.


  • Editar: (181 -> 174) reemplazado dy mcon operadores
  • Editar: (174 -> 151) ren líneac
  • Editar: (151 -> 149) eliminó una opción generada innecesariamente en el +caso
  • Editar: (149 -> 141) eliminó una cláusula innecesaria para %, que fue manejada por&
MtnViewMark
fuente
2

PHP - 275 243 caracteres

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

Sin 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
fuente
2

Pitón demasiado verbosa ( 384 367 caracteres)

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)

No es el más corto, pero es agradable y funcional. La cosa de despacho en el medio podría presumiblemente ser reescrita como una disyunción sobre las (h(p) == '?') and (? lambda body)cosas tipográficas. Definir que h operador me cuesta algunos caracteres sin ningún beneficio, pero es bueno tener una palabra clave para head.

Me gustaría tener una grieta en el script de golf más tarde si el tiempo lo permite.

editar: eliminó la tercera rama innecesaria en el caso '*' después de leer la respuesta rubí del usuario300

roobs
fuente
2

Más corto Snappier Python 2.6 (272 caracteres)

golfizado:

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

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

con:

  • desastre lógico evaluado perezosamente!
  • C cuerdas de estilo!
  • lindo idioma de comparación múltiple!
  • Mucho feo!

crédito a la respuesta del usuario 300 por ilustrar cómo se simplifican las cosas si puede obtener algún tipo de valor de terminador al extraer el encabezado de una cadena vacía.

Deseo que el desempaque de cabeza / cola se pueda realizar en línea durante la declaración de los argumentos de m. entonces m podría ser una lambda, al igual que sus amigos y glob. python2 no puede hacerlo, y después de leer un poco, parece que python3 tampoco puede hacerlo. aflicción.

pruebas:

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
fuente
2

Rubí - 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}

Sin 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

Pruebas:

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

Inspirado por la respuesta de los roobs

Arnaud Le Blanc
fuente
No sé nada sobre Ruby, pero de su código he aprendido que acceder a índices fuera de límites devuelve nulo. Por lo tanto, al abrir una cadena vacía se obtiene un valor nulo que se puede utilizar como un símbolo de terminador de cadena. Estilo C! ¡hábil! Supongo que podría imitarse en Python pasando cada cadena de entrada a través delambda s : list(s)+[None]
roobs
Por lo que parece, Ruby ha incorporado la coincidencia de patrones. Eso es ciertamente útil para este tipo de problema.
Jonathan M Davis
En realidad, ??son caracteres literales, =>son separadores de clave / valor en Ruby Hashes, y ->comienza un lambda :-) ( { ?? => ->{...} }es un hash con clave "?"y un lambda como valor). Pero sí, la forma en que se usa en conjunto parece una coincidencia de patrones en caracteres únicos :-)
Arnaud Le Blanc
2

Función C - 178 caracteres necesarios

Compilado con GCC, esto no produce advertencias.

#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 primera y la última línea no están incluidas en el recuento de caracteres. Se proporcionan solo por conveniencia.

Volado:

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
fuente
2

JavaScript: 259 caracteres

Mi implementación es muy recursiva, por lo que la pila se desbordará si se usa un patrón extremadamente largo. Ignorando el signo más (que podría haber optimizado pero elegí no hacerlo por simplicidad), se utiliza un nivel de recursión para cada 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)))}

La función a veces devuelve un número en lugar de un booleano. Si eso es un problema, puede usarlo como !!glob(pattern, str).


Ungolfed (sin minificar, más bien) para servir como un recurso útil:

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

Tenga en cuenta que la indexación en caracteres de una cadena como para elementos de matriz no es parte del estándar de lenguaje anterior (ECMAScript 3), por lo que puede no funcionar en navegadores más antiguos.

Por favor levantese
fuente
1

Python (454 caracteres)

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
fuente
1

D: 363 caracteres

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

Más legible:

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

está construido a partir de funciones que consumen dos argumentos de la pila, syp, y producen un único valor de retorno booleano. hay un poco de basura para hacer que sea compatible con los perezosos y perezosos u operadores. Realmente dudo que este enfoque sea casi óptimo, o incluso en la dirección correcta.

También hay algunos momentos estúpidamente entretenidos, como '*'sacar un patrón, consumirlo '*'en una comparación, solo para darse cuenta de que la rama posterior no coincide. para descender a la otra rama, necesitamos el patrón con el '*'frente, pero hemos consumido ese patrón original cuando hicimos estallar '*', y consumimos el '*', así que para obtener el patrón nuevamente cargamos una nueva cadena brillante constante '*'y anteponerlo en su lugar. se vuelve aún más feo porque, por alguna razón, la coincidencia de caracteres debe hacerse con valores ascii, pero preceder a la cadena necesita cadenas.

menos golfscript de 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;

pruebas

{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
fuente
1

C # (251 caracteres)

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

Ligeramente más legible:

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

Lo sé, lo sé ... excepto por los globos que contienen la barra invertida. Lo cual es realmente desafortunado. Hubiera sido realmente inteligente de lo contrario. :(

Timwi
fuente