En "aa67bc54c9", ¿hay alguna forma de imprimir "aa" 67 veces, "bc" 54 veces y así sucesivamente, utilizando expresiones regulares?

Question

Me hicieron esta pregunta en una entrevista para una pasantía, y la primera solución que sugerí fue intentar usar una expresión regular (por lo general estoy un poco perplejo en las entrevistas). Algo como esto

(?P<str>[a-zA-Z]+)(?P<n>[0-9]+) 

pensé que iba a coincidir con las cuerdas y almacenarlos en el "str" ​​variable y los números en la variable "n". De qué, no estaba seguro.

Por lo tanto, coincide con las cadenas del tipo "a1b2c3", pero el problema aquí es que también coincide con las cadenas del tipo "a1b". ¿Alguien podría sugerir una solución para lidiar con este problema?

Además, ¿hay alguna otra expresión regular que pueda resolver este problema?

Answer 1

¿qué tal:

while ($line =~ s/^([a-z]+)(\d+)//i) 
{ 
    print $1 x $2; 
} 

Answer 2

respondiendo a la pregunta directa:

• No, las expresiones regulares de texto partido y no imprima nada, así que no hay manera de hacerlo únicamente el uso de expresiones regulares .

La expresión regular que usted dio coincidirá con un par de cadena/número; puede imprimir eso repetidamente utilizando un mecanismo apropiado. La solución Perl de @tster es lo más compacta posible. (No utiliza los nombres que aplicó en su expresión regular, estoy bastante seguro de que eso no importa.)

Los detalles restantes dependen del lenguaje de implementación.

Answer 3

¿Sabe por qué las "expresiones regulares" se llaman "regulares"? :-)

Eso sería demasiado largo para explicarlo, solo voy a delinear el camino. Para hacer coincidir un patrón (es decir, decidir si una cadena dada es "válida" o "inválida"), un informático teórico usaría un finite state automaton. Esa es una máquina abstracta que tiene un número finito de estados; cada tick lee un carácter de la entrada y salta a otro estado. El patrón de dónde saltar desde un estado particular cuando se lee un personaje en particular es fijo. Algunos estados están marcados como "OK", algunos como "FAIL", por lo que al examinar el estado de una máquina puede verificar si su texto es "válido" (es decir, un correo electrónico válido).

Por ejemplo, esta máquina sólo acepta "agradable" como su palabra "válida" (una imagen de Wikipedia):

Un conjunto de palabras "válidos" una máquina de este tipo, teóricamente, puede distinguir de inválido se llama "regular language". No todos los conjuntos son un lenguaje regular: por ejemplo, los autómatas de estados finitos son incapaces de verificar si los paréntesis en la cadena están equilibrados.

Pero la construcción de máquinas de estado era una tarea compleja, en comparación con la complejidad de definir qué es "válido". Entonces los matemáticos (principalmente S. Kleene) notaron que cada regular language podría describirse con un "regular expression". Tenían * sy | y eran los prototipos de lo que ahora conocemos como expresiones regulares.

---

¿Qué tiene que ver con el problema?El problema en el tema es esencialmente no regular. No se puede expresar con nada que funcione como un autómata finito.

La esencia es que debe contener una celda de memoria que sea capaz de contener un número arbitrario (recuento de repeticiones en su caso). Los autómatas finitos y las expresiones regulares clásicas no pueden hacer esto.

Sin embargo, las expresiones regulares modernas son más expresivas y are said to be able to check balanced parentheses! Pero esto puede servir como un buen ejemplo de que no debe usar expresiones regulares para tareas que no convengan. Y mucho menos que contenga fragmentos de código; esto hace que la expresión esté lejos de ser "regular".

Respondiendo a la pregunta inicial, no puede resolver su problema con el uso de cualquier cosa "normal" solo. Sin embargo, las expresiones regulares podrían ser ayudarle en la solución de este problema, como en tster's answer

---

Tal vez, debería mirar más de cerca a tster's answer (hacer un "1" no, por favor!) Y mostrar por qué no es el "regular expresión "solución". Uno puede pensar que sí lo es, solo contiene una declaración de impresión (no es esencial) y un concepto de bucle y bucle es compatible con la potencia expresiva del autómata de estado finito. Pero hay una cosa más difícil de alcanzar:

while ($line =~ s/^([a-z]+)(\d+)//i) 
{ 
    print $1 
      x # <--- this one 
       $2; 
} 

La tarea de leer una cadena y un número y la impresión en varias ocasiones que cadena dada varias veces, donde el número es un entero arbitrario, se puede deshacer en un estado finito máquina sin memoria adicional. Utiliza una celda de memoria para mantener ese número y disminuirlo, y verifica que sea mayor que cero. Pero este número puede ser arbitrariamente grande, y contradice con una memoria finita disponible para la máquina de estado finita.

Sin embargo, no hay nada de malo en el patrón clásico /([abc]*){5}/ que coincide con algo "regular" repetido fijo número de veces. En esencia, tenemos estados que corresponden a "patrón combinado una vez", "patrón combinado dos veces" ... "patrón combinado 5 veces". Hay un número finito de ellos, y esa es la esencia de la diferencia.

Answer 4

No, esta es su 'pregunta trucada' básica: no importa cómo la responda, esa respuesta es incorrecta a menos que tenga exactamente la respuesta que el entrevistador fue entrenado para loro. Ver el estudio diagnóstico de la cuestión determinada por Pavel Shved - en cuenta que todas las invocaciones tienen 'no' como una condición común, la herramienta sólo mantiene deslizamiento: Incluso cuando se cambia de estado no hay contador en ese estado

tengo un libro bastante avanzado de Kenneth C. Louden, que es un profesor universitario en el tema, en el que se afirma que el tema en cuestión está codificado como "Regex no puede contar". La respuesta obvia a la pregunta me parece en este momento usar la función de anticipación de Regex ...

Probablemente depende de qué versión de la marca de expresiones regulares esté usando el entrevistador, lo que probablemente dependa de la dinámica de vuelo de Pelotas de golf.

Answer 5

Buenas respuestas hasta ahora. Por lo general, se considera que las expresiones regulares son una forma de hacer coincidir patrones, no generar resultados de la manera que usted mencionó.

Habiendo dicho eso, hay una forma de usar expresiones regulares como parte de la solución.@Jonathan Leffler hizo un buen comentario en su comentario al tster's reply: "... tal vez necesites una mejor biblioteca de expresiones regulares en tu idioma".

Según su idioma de elección y la biblioteca disponible, es posible realizar esto. Usando C# y .NET, por ejemplo, esto podría lograrse a través del Regex.Replace method. Sin embargo, la solución no es 100% de expresiones regulares, ya que todavía se basa en otras clases y métodos (StringBuilder, string.join, y Enumerable.Repeat) como se muestra a continuación:

string input = "aa67bc54c9"; 
string pattern = @"([a-z]+)(\d+)"; 
string result = Regex.Replace(input, pattern, m => 
     // can be achieved using StringBuilder or String.Join/Enumerable.Repeat 
     // don't use both 
     //new StringBuilder().Insert(0, m.Groups[1].Value, Int32.Parse(m.Groups[2].Value)).ToString() 
     String.Join("", Enumerable.Repeat(m.Groups[1].Value, Int32.Parse(m.Groups[2].Value)).ToArray()) 
     + Environment.NewLine // comment out to prevent line breaks 
     ); 
Console.WriteLine(result); 

Una solución más clara sería identificar las coincidencias , repórtelos e insértelos usando StringBuilder en lugar de confiar en Regex.Replace. Otros idiomas pueden tener modismos compactos para manejar la multiplicación de cadenas que no depende de otras clases de biblioteca.

Para responder a la pregunta de la entrevista, respondí, "es posible, sin embargo, la solución no sería un enfoque 100% regex independiente y dependería de otras características de lenguaje y/o bibliotecas para manejar el aspecto de generación de la pregunta ya que la expresión regular solo es útil para unir patrones, no generarlos ".

Y en base a las otras respuestas aquí podría reforzar esa respuesta aún más si es necesario.