Su tarea es crear un programa que determine si una cadena dada es una expresión regular válida o no utiliza fragmentos de código provenientes de sitios en la red StackExchange.
A los efectos de este desafío, el dialecto expresión regular será un conjunto simplificada y en su mayoría mínima de meta-caracteres: ()*?|\
. Como tal, no podrá utilizar analizadores de expresiones regulares incorporados.
\
se usa para escapar de los metacaracteres. Debe ser seguido por un meta-personaje.- Los paréntesis sin escapes deben estar equilibrados
*
y?
debe estar precedido por un no-meta-caracter, un grupo entre paréntesis o un meta-caracter escapado.- Todos los demás caracteres ASCII imprimibles más nueva línea, tabulación y espacio deben admitirse como caracteres no meta. Lo que sucede con una cadena que contiene otros caracteres no está definido.
- El significado real de la expresión regular no es importante para este desafío.
Ejemplos
Truthy:
abc
a?
(a|)*
()
a|b*
\*
\\
\\*
a*b?(cd|e)
+
[
}
(123\))*
\|
(a(b(c|d)*e)*f)*
(|\)*)
(abc)+*
(abc)+
+abc
^ last test case is an actual newline
Falsy:
?abc
*
**
\
(
a*?
a?*
?
a)
(\)
(|\)*
\()
|*
(?:abc)
\\**
\n
Puntuación
Su puntaje general es la cantidad de fragmentos tomados de las preguntas y respuestas de StackExchange.
- Los fragmentos repetidos cuentan tantas veces como se usan.
- El espacio en blanco se puede agregar y eliminar libremente (debido a Python, Haskell y otros lenguajes sensibles al espacio en blanco) y no cuenta para el recuento de fragmentos.
- Los fragmentos están permitidos en cualquier sitio de StackExchange siempre que provengan de preguntas, respuestas y comentarios que sean más antiguos (incluido el tiempo de edición; use revisiones más antiguas si es necesario) que este desafío. (24 de septiembre de 2019 a las 3:30 p.m. UTC)
- Los fragmentos pueden provenir de cualquier parte de una pregunta, respuesta o cuerpo de comentario, ya sea en un bloque de código preformateado o no.
- Empalmar un fragmento en el medio de otro hace que el fragmento externo cuente como dos fragmentos
¡La puntuación más baja gana!
decision-problem
parsing
regular-expression
duct-tape-coding
Carne de res
fuente
fuente
Respuestas:
Perl 6 , 20 fragmentos
Pruébalo en línea!
Los fragmentos se toman de:
{$_ eq
,m/[
,<-[
,()*?
,|\\
,]>
,|\\
,<[
,()*?
,|\\
,]>
,|
,'(' <~~>* ')'
,<[
,*?
,]>
,?|
,\|
,]+/
,}
.Este es principalmente el enfoque codicioso (hecho evidente por todos los fragmentos de uno o dos caracteres). Utilicé SymbolHound para buscar los caracteres individuales, y la única optimización real fue el
'(' <~~>* ')'
fragmento, que se toma de mi propia respuesta en expresiones regulares recursivas de Perl 6.Explicación:
Básicamente, esto verifica si la entrada es igual a una coincidencia codiciosa de una expresión regular válida. La razón por la que no podemos usar la expresión regular en sí y agregarla
^$
para marcar los extremos es porque estamos usando una expresión regular recursiva, que no funcionaría si hubiera^$
marcadores. La expresión regular en sí es:fuente
~~
, gracias!~~
que no aparece porque aún no está completamente implementado (por ejemplo<~~0>
), aunque hay otras gemas ocultas allí.