¿Cómo puedo usar Regex para encontrar una cadena de caracteres en orden alfabético usando Python?

Así que tengo un desafío en el que estoy trabajando: encuentre la cadena más larga de caracteres alfabéticos en una cadena. Por ejemplo, “abcghiijkyxz” debería dar como resultado “ghiijk” (Sí, la i está duplicada).

He estado haciendo bastante con los bucles para resolver el problema, iterando sobre toda la cadena, luego para cada personaje, iniciando un segundo bucle con más bajo y ord. No se necesita ayuda para escribir ese bucle.

Sin embargo, se me sugirió que Regex sería ideal para este tipo de cosas. Mi expresión regular es débil (sé cómo agarrar un conjunto estático, mi conocimiento avanzado se extiende a saber que existen). ¿Cómo escribiría un Regex para mirar hacia adelante y verificar que los personajes futuros sean los siguientes en orden alfabético? ¿O la sugerencia de usar Regex no es práctica para este tipo de cosas?

Edit: El consenso general parece ser que Regex es realmente terrible para este tipo de cosas.

Solo para demostrar por qué la expresión regular no es práctica para este tipo de cosas, aquí hay una expresión regular que coincidirá con ghiijk en su ejemplo dado de abcghiijkyxz . Tenga en cuenta que también coincidirá con abc , y , x , z , ya que técnicamente deberían considerarse para la cadena más larga de caracteres alfabéticos en orden. Desafortunadamente, no puede determinar cuál es el más largo solo con expresiones regulares, pero esto le brinda todas las posibilidades. ¡Tenga en cuenta que esta expresión regular funciona para PCRE y no funcionará con el módulo de re de python! Además, tenga en cuenta que la biblioteca de regex de python no es compatible actualmente (*ACCEPT) . Aunque no lo he probado, el paquete pyre2 (envoltorio de python para re2 pyre2 de Google que usa Cython) afirma que admite el verbo de control (*ACCEPT) , por lo que actualmente es posible usar python.

Ver regex en uso aquí

 ((?:a+(?(?!b)(*ACCEPT))|b+(?(?!c)(*ACCEPT))|c+(?(?!d)(*ACCEPT))|d+(?(?!e)(*ACCEPT))|e+(?(?!f)(*ACCEPT))|f+(?(?!g)(*ACCEPT))|g+(?(?!h)(*ACCEPT))|h+(?(?!i)(*ACCEPT))|i+(?(?!j)(*ACCEPT))|j+(?(?!k)(*ACCEPT))|k+(?(?!l)(*ACCEPT))|l+(?(?!m)(*ACCEPT))|m+(?(?!n)(*ACCEPT))|n+(?(?!o)(*ACCEPT))|o+(?(?!p)(*ACCEPT))|p+(?(?!q)(*ACCEPT))|q+(?(?!r)(*ACCEPT))|r+(?(?!s)(*ACCEPT))|s+(?(?!t)(*ACCEPT))|t+(?(?!u)(*ACCEPT))|u+(?(?!v)(*ACCEPT))|v+(?(?!w)(*ACCEPT))|w+(?(?!x)(*ACCEPT))|x+(?(?!y)(*ACCEPT))|y+(?(?!z)(*ACCEPT))|z+(?(?!$)(*ACCEPT)))+) 

Resultados en:

 abc ghiijk y x z 

Explicación de una sola opción, es decir, a+(?(?!b)(*ACCEPT)) :

  • a+ Coincide con (literalmente) una o más veces. Esto detecta instancias donde varios de los mismos caracteres están en secuencia, como aa .
  • (?(?!b)(*ACCEPT)) Si la cláusula evalúa la condición.
    • (?!b) Condición para la cláusula if. El lookahead negativo que asegura lo que sigue no es b . Esto se debe a que si no es b , queremos que el siguiente verbo de control tenga efecto.
    • (*ACCEPT) Si se cumple la condición (arriba), aceptamos la solución actual. Este verbo de control hace que la expresión regular finalice correctamente, omitiendo el rest del patrón. Dado que este token está dentro de un grupo de captura, solo ese grupo de captura finaliza correctamente en esa ubicación en particular, mientras que el patrón principal continúa ejecutándose.

Entonces, ¿qué pasa si la condición no se cumple? Bueno, eso significa que (?!b) evaluado como falso. Esto significa que el siguiente carácter es, de hecho, b por lo que permitimos que continúe la coincidencia (en lugar de capturar en esta instancia). Tenga en cuenta que todo el patrón está envuelto en (?:)+ que nos permite hacer coincidir opciones consecutivas hasta que se cumpla el verbo de control (*ACCEPT) o el final de la línea.

La única excepción a toda esta expresión regular es la de z . Siendo que es el último carácter del alfabeto inglés (que supongo que es el objective de esta pregunta), no nos importa lo que venga después, así que simplemente podemos poner z+(?(?!$)(*ACCEPT)) , lo que asegurará que nada coincida después de z . Si, en cambio, desea hacer coincidir za (orden alfabético circular coincidente – idk si esta es la terminología adecuada, pero me parece correcta) puede usar z+(?(?!a)(*ACCEPT)))+ como se ve aqui

Como se mencionó, regex no es la mejor herramienta para esto. Ya que está interesado en una secuencia continua, puede hacer esto con un solo bucle for:

 def LNDS(s): start = 0 cur_len = 1 max_len = 1 for i in range(1,len(s)): if ord(s[i]) in (ord(s[i-1]), ord(s[i-1])+1): cur_len += 1 else: if cur_len > max_len: max_len = cur_len start = i - cur_len cur_len = 1 if cur_len > max_len: max_len = cur_len start = len(s) - cur_len return s[start:start+max_len] >>> LNDS('abcghiijkyxz') 'ghiijk' 

Mantenemos un total acumulado de cuántos caracteres no decrecientes hemos visto, y cuando la secuencia no decreciente termina, la comparamos con la secuencia no decreciente más larga que vimos anteriormente, actualizando nuestro “mejor visto hasta ahora” si es más largo .

Genere todas las subcadenas de expresiones regulares como ^ a + b + c + $ (de más larga a más corta). Luego haz coincidir cada una de esas expresiones regulares con todas las subcadenas (de mayor a menor) de “abcghiijkyxz” y detente en la primera coincidencia.

 def all_substrings(s): n = len(s) for i in xrange(n, 0, -1): for j in xrange(n - i + 1): yield s[j:j + i] def longest_alphabetical_substring(s): for t in all_substrings("abcdefghijklmnopqrstuvwxyz"): r = re.compile("^" + "".join(map(lambda x: x + "+", t)) + "$") for u in all_substrings(s): if r.match(u): return u print longest_alphabetical_substring("abcghiijkyxz") 

Eso imprime “ghiijk”.

Regex : char+ significa a+b+c+...

Detalles:

  • + Partidas entre uno y tiempos ilimitados

Código Python :

 import re def LNDS(text): array = [] for y in range(97, 122): # a - z st = r"%s+" % chr(y) for x in range(y+1, 123): # b - z st += r"%s+" % chr(x) match = re.findall(st, text) if match: array.append(max(match, key=len)) else: break if array: array = [max(array, key=len)] return array 

Salida :

 print(LNDS('abababababab abc')) >>> ['abc'] print(LNDS('abcghiijkyxz')) >>> ['ghiijk'] 

Para el patrón de abcghiijkyxz regulares abcghiijkyxz :

 a+b+ i+j+k+l+ a+b+c+ j+k+ a+b+c+d+ j+k+l+ b+c+ k+l+ b+c+d+ l+m+ c+d+ m+n+ d+e+ n+o+ e+f+ o+p+ f+g+ p+q+ g+h+ q+r+ g+h+i+ r+s+ g+h+i+j+ s+t+ g+h+i+j+k+ t+u+ g+h+i+j+k+l+ u+v+ h+i+ v+w+ h+i+j+ w+x+ h+i+j+k+ x+y+ h+i+j+k+l+ y+z+ i+j+ i+j+k+ 

Demo de código

Para realmente “resolver” el problema, puedes usar

 string = 'abcxyzghiijkl' def sort_longest(string): stack = []; result = []; for idx, char in enumerate(string): c = ord(char) if idx == 0: # initialize our stack stack.append((char, c)) elif idx == len(string) - 1: result.append(stack) elif c == stack[-1][1] or c == stack[-1][1] + 1: # compare it to the item before (a tuple) stack.append((char, c)) else: # append the stack to the overall result # and reinitialize the stack result.append(stack) stack = [] stack.append((char, c)) return ["".join(item[0] for item in sublst) for sublst in sorted(result, key=len, reverse=True)] print(sort_longest(string)) 

Cuyos rendimientos

 ['ghiijk', 'abc', 'xyz'] 

en este ejemplo.


La idea es recorrer la cadena y hacer un seguimiento de una variable de stack que se llena con sus requisitos utilizando ord() .

¡Es realmente fácil con expresiones regulares!

(Usando contextos finales aquí)

 rexp=re.compile( "".join(['(?:(?=.' + chr(ord(x)+1) + ')'+ x +')?' for x in "abcdefghijklmnopqrstuvwxyz"]) +'[az]') a = 'bcabhhjabjjbckjkjabckkjdefghiklmn90' re.findall(rexp, a) #Answer: ['bc', 'ab', 'h', 'h', 'j', 'ab', 'j', 'j', 'bc', 'k', 'jk', 'j', 'abc', 'k', 'k', 'j', 'defghi', 'klmn']