Te doy la bienvenida a proyecto on line, en este lugar vas a hallar la solucíon a lo que andabas buscando.
Solución:
Haskell, 203 bytes
Nadie había hecho esto mediante la implementación de un pequeño motor de expresiones regulares todavía, y sentí que tenía que hacerse. Obviamente, esto no ganará. pero espero que inspire a alguien a escribir un motor de expresiones regulares aún más golfista.
He reescrito mi solución para evitar analizar directamente la expresión regular en su AST. En cambio, el proceso de análisis construye una función que se utiliza para hacer coincidir un string contra la expresión regular de entrada.
La función principal es (&) :: String -> String -> Bool que toma un string representación de una expresión regular y una string para probar, devolviendo un valor booleano. Esto llama a la siguiente función que maneja la mayor parte del trabajo al analizar la expresión regular y hacer coincidir la string.
Función p :: String -> ([String] -> [String], String) toma una string representación de una expresión regular y devuelve como el primer elemento de una tupla una función que devuelve una lista de todos los posibles sufijos de cadenas no coincidentes en la lista de entrada después de satisfacer la expresión regular analizada de la entrada string. La expresión regular coincide completamente con la string si el vacio string está contenido en la lista de posibles sufijos no coincidentes.
r&s=elem""$fst(p r)[s]
p(c:t)|c>'`'=t% s->[t|h:t<-s,c==h]|c>'^'=t%id|(l,o:t)<-p t,(r,_:u)<-p t=u%last(r.l:[s->r s++l s|o>'+'])
m#s=s++filter(`notElem`s)(m s)
('*':t)%m=t%until(s->s==m#s)(m#)
s%m=(m,s)
¡Pruébelo en línea!
Para deshacerme de un byte, reemplacé import Data.List; m#s=nub$s++m s con m#s=s++filter(`notElem`s)(m s). Estas funciones no son equivalentes si hay elementos duplicados en cualquiera s de m s. Sin embargo, la nueva función elimina todos los elementos de m s que ya existen en s, asi que until todavía termina una vez que no se descubren nuevos sufijos mediante la aplicación de m.
Código sin golf
import Data.List
match :: String -> String -> Bool
match r s =elem ""$(fst $ parseRegex r)[s]
parseRegex :: String -> ([String] -> [String], String)
parseRegex ('_':t) = parseKleene id t
parseRegex (c:t) | c >= 'a' = parseKleene (>>=p) t
where p (c':t')| c==c' = [t']
p _ = []
parseRegex ('(':t) =
let (l, (o:t')) = parseRegex t in
let (r, (_:t'')) = parseRegex t' in
parseKleene (if o=='+' then (r.l) else (ss-> (r ss)++(l ss))) t''
parseKleene :: ([String] -> [String]) -> String -> ([String] -> [String], String)
parseKleene p ('*':t) = parseKleene p' t
where
p' ss
| ss' <- nub$ p ss,
ss /= ss' = ss ++ (p' ss')
| otherwise = ss
parseKleene p s = (p,s)
GolfScript, 198 bytes
Pude superar mi solución Haskell implementando el primer algoritmo que probé en GolfScript en lugar de Haskell. No creo que sea lo suficientemente interesante como para una respuesta separada, así que lo dejaré aquí. Es probable que haya algunas oportunidades para jugar al golf, ya que aprendí GolfScript solo por esto.
Esta solución tiene la forma de un bloque que espera la prueba. string en la parte superior de la pila seguida de la expresión regular string.
[.;]1+(.96>0[]2%0r(r:s;[@]s(;iif:i~(.3%;2[]until[.;]+:r~;.(..4%2%)@m);m);[email protected]@m 1$:o~ii;(:c;;,,(;c=,(;%i;i:m~""?
¡Pruébelo en línea!
APL (Dyalog Unicode), 39 bytesSBCS
Editar: ahora funciona con corridas de * incluso después _
Programa completo. Solicita stdin para string y luego para regex. Devuelve una lista que consta de una lista vacía (por defecto, se imprime como dos espacios) para coincidencias y una lista vacía (línea vacía) para no coincidencias.
(1⌽'$^','*+' '_'⎕R'*' '()'⊢⍞~'+')⎕S⍬⊢⍞
¡Pruébelo en línea! (la salida se hace más fácil de leer al convertir toda la salida a JSON)
⍞stdin rápido (para string)
⊢sobre eso, aplique lo siguiente:
(...)⎕S⍬PCRE SBusque lo siguiente, devolviendo una lista vacía para cada coincidencia
~'+'elimine todas las ventajas de lo siguiente:
⍞prompt stdin (para expresiones regulares)
⊢sobre eso, aplique lo siguiente:
'*+' '_'⎕R'*' '()'PCRE Replace corridas de * con * y _ con ()
'$^',anteponer el signo de dólar y el símbolo de intercalación (indicando el final y el comienzo)
1⌽rotar el primer carácter ($) hasta el final
APL (Dyalog Unicode), 295 277 octetos
a←819⌶⎕A
E←+')∧0=+-⌿'()'∘.=⍵1↓¯1↓⊢
M←c←⊃⌽⍵⋄c∊'0',a:0⋄c∊'_*':1⋄r s o←E⍵⋄o='
D←',⍺∇s⋄1⌽∊')('(⍺∇r)'+'s
M⊃D/(⌽⍵),⊂⍺
¡Pruébelo en línea!
-18 bytes gracias a @ngn.
Esta es una prueba de concepto de que podemos hacer una "coincidencia de expresiones regulares simple" sin ningún retroceso, evitando así posibles bucles infinitos debido a _* o r**. Este también es un ejemplo de que APL es un lenguaje de programación de uso general.
La función anónima en la última línea hace la coincidencia de expresiones regulares; usarlo como (regex) f (input string). El valor de retorno es 1 si la coincidencia es exitosa, 0 en caso contrario.
Concepto
Dada una expresión regular simple R y el primer personaje c de entrada string, podemos construir (o derivar) otra expresión regular simple R' que coincide exactamente con las cuerdas s donde el original R partidos c+s.
$$ forall R in text expresión regular simple, c in text [a-z], s in text [a-z]*, \ existe R ' in text expresión regular simple, R' = sim s iff R = sim c + s $$
Combine esto con un probador que compruebe si r coincide con un vacío string (epsilon), y obtenemos un comparador de expresiones regulares simple completamente funcional: dada una expresión regular $ R_0 $ y string $ s = c_1 c_2 cdots c_n $, derivar secuencialmente $ R_0, c_1 rightarrow R_1, c_2 rightarrow R_2 cdots rightarrow R_n $ y luego prueba si $ R_n $ coincide con epsilon.
Mi código usa el siguiente algoritmo para probar epsilon match (MatchEps) y computación R' de R y c (Derive).
T = True, F = False
0 = null regex (never matches)
_ = "empty string" regex
a = single-char regex
r, s = any (sub-)regex
MatchEps :: regex -> bool
MatchEps 0 = F # Null regex can't match empty string
MatchEps _ = T # Empty-string regex trivially matches empty string
MatchEps a = F # Single-char can't match
MatchEps r* = T # Kleene matches as zero iteration
MatchEps (r|s) = MatchEps r or MatchEps s
MatchEps (r+s) = MatchEps r and MatchEps s
Derive :: char -> regex -> regex
# No matching string at all
Derive c 0 = 0
# _ can't match any string that starts with c
Derive c _ = 0
# Single-char regex only matches itself followed by empty string
Derive c a = if c == 'a' then _ else 0
# r* matches either _ or (r+r*);
# _ can't start with c, so it must be first `r` of (r+r*) that starts with c
Derive c r* = ([Derive c r]+r*)
# r or s; simply derive from r or derive from s
Derive c (r|s) = ([Derive c r]|[Derive c s])
# r followed by s; it matters if r can match _
Derive c (r+s) =
# if r matches _, either [r starts with c] or [r matches _ and s starts with c]
if MatchEps r then (([Derive c r]+s)|[Derive c s])
# otherwise, r always starts with c
else ([Derive c r]+s)
Sin golf, con comentarios
⍝ Unwrap single layer of (...) and extract (r, s, op) from (r|s) or (r+s)
ExtractRS←+')∧0=+-⌿'()'∘.=⍵1↓¯1↓⊢
⍝ 1↓¯1↓⊢ Drop the outermost ()
⍝ ... Pass the result to the function as ⍵...
⍝ +-⌿'()'∘.=⍵ Compute the layers of nested ()s
⍝ (⍵∊'|+')∧0= Locate the operator (`|` or `+`) as bool vector
⍝ ⍵... Pass to inner function again ⍵ as ⍺, above as ⍵
⍝ ⍺[⍸⍵] Extract the operator
⍝ (⍺⊆⍨~⍵), Prepend the left and right regexes
⍝ Tests if the given regex matches an empty string (epsilon, eps)
MatchEps←s) or (r+s); extract it
op='
⍝ Derives regex `R'` from original regex `R` and first char `c`
Derive←s): one char from either branch
MatchEps r: '((',(⍺∇r),'+',s,')
⍝ Main function: Fold the string by Derive with initial regex,
⍝ and then test if the result matches eps
f←MatchEps⊃Derive/(⌽⍵),⊂⍺
Nota final
Esta no es una idea original mía; es parte de una serie de ejercicios sobre un libro de texto que prueba teoremas. Puedo afirmar que se ha demostrado que el algoritmo funciona (porque completé las pruebas de corrección), aunque no puedo abrir la prueba completa al público.
Si conservas algún reparo y forma de reformar nuestro sección puedes realizar una interpretación y con gusto lo ojearemos.