Python: ¿Cómo hacer coincidir los paréntesis nesteds con expresiones regulares?

Estoy intentando hacer coincidir una cadena similar a una expresión matemática, que tiene paréntesis nesteds.

import re p = re.compile('\(.+\)') str = '(((1+0)+1)+1)' print p.findall(s) 

[‘(((1 + 0) +1) +1)’]

Quería que coincidiera con todas las expresiones incluidas, como (1 + 0), ((1 + 0) +1) …
Ni siquiera me importa si coincide con los no deseados como (((1 + 0), puedo cuidarlos).

¿Por qué no está haciendo eso ya, y cómo puedo hacerlo?

La expresión regular trata de hacer coincidir la mayor cantidad de texto posible, por lo que consume toda la cadena. No busca coincidencias adicionales de la expresión regular en partes de esa cadena. Es por eso que solo obtienes una respuesta.

La solución es no usar expresiones regulares. Si realmente está intentando analizar expresiones matemáticas, use soluciones de análisis reales. Si realmente solo desea capturar las piezas entre paréntesis, simplemente pase el círculo sobre los conteos de caracteres cuando vea (e) y aumente la disminución de un contador.

Como han mencionado otros, las expresiones regulares no son el camino a seguir para construcciones anidadas. Daré un ejemplo básico usando pyparsing :

 import pyparsing # make sure you have this installed thecontent = pyparsing.Word(pyparsing.alphanums) | '+' | '-' parens = pyparsing.nestedExpr( '(', ')', content=thecontent) 

Aquí hay un ejemplo de uso:

 >>> parens.parseString("((a + b) + c)") 

Salida:

 ( # all of str [ ( # ((a + b) + c) [ ( # (a + b) ['a', '+', 'b'], {} ), # (a + b) [closed] '+', 'c' ], {} ) # ((a + b) + c) [closed] ], {} ) # all of str [closed] 

(Con nueva línea / sangría / comentarios hechos manualmente)

Edición: Modificado para eliminar Forward innecesarios, según las sugerencias de Paul McGuire.

Para obtener la salida en formato de lista anidada:

 res = parens.parseString("((12 + 2) + 3)") res.asList() 

Salida:

 [[['12', '+', '2'], '+', '3']] 

Se está preparando un nuevo módulo de motor regular para reemplazar el existente en Python. Introduce una gran cantidad de nuevas funcionalidades, incluyendo llamadas recursivas.

 import regex s = 'aaa(((1+0)+1)+1)bbb' result = regex.search(r''' (? #capturing group rec \( #open parenthesis (?: #non-capturing group [^()]++ #anyting but parenthesis one or more times without backtracking | #or (?&rec) #recursive substitute of group rec )* \) #close parenthesis ) ''',s,flags=regex.VERBOSE) print(result.captures('rec')) 

Salida:

 ['(1+0)', '((1+0)+1)', '(((1+0)+1)+1)'] 

Error relacionado en la regex : http://code.google.com/p/mrab-regex-hg/issues/detail?id=78

Los lenguajes Regex no son lo suficientemente poderosos para hacer coincidir construcciones anidadas arbitrariamente. Para eso necesitas un autómata push-down (es decir, un analizador). Hay varias herramientas de este tipo disponibles, como PLY .

Python también proporciona una biblioteca de analizadores para su propia syntax, que puede hacer lo que necesite. La salida es extremadamente detallada, sin embargo, y toma un tiempo envolver su cabeza. Si está interesado en este ángulo, la siguiente discusión trata de explicar las cosas de la manera más simple posible.

 >>> import parser, pprint >>> pprint.pprint(parser.st2list(parser.expr('(((1+0)+1)+1)'))) [258, [327, [304, [305, [306, [307, [308, [310, [311, [312, [313, [314, [315, [316, [317, [318, [7, '('], [320, [304, [305, [306, [307, [308, [310, [311, [312, [313, [314, [315, [316, [317, [318, [7, '('], [320, [304, [305, [306, [307, [308, [310, [311, [312, [313, [314, [315, [316, [317, [318, [7, '('], [320, [304, [305, [306, [307, [308, [310, [311, [312, [313, [314, [315, [316, [317, [318, [2, '1']]]]], [14, '+'], [315, [316, [317, [318, [2, '0']]]]]]]]]]]]]]]], [8, ')']]]]], [14, '+'], [315, [316, [317, [318, [2, '1']]]]]]]]]]]]]]]], [8, ')']]]]], [14, '+'], [315, [316, [317, [318, [2, '1']]]]]]]]]]]]]]]], [8, ')']]]]]]]]]]]]]]]], [4, ''], [0, '']] 

Puedes aliviar el dolor con esta corta función:

 def shallow(ast): if not isinstance(ast, list): return ast if len(ast) == 2: return shallow(ast[1]) return [ast[0]] + [shallow(a) for a in ast[1:]] >>> pprint.pprint(shallow(parser.st2list(parser.expr('(((1+0)+1)+1)')))) [258, [318, '(', [314, [318, '(', [314, [318, '(', [314, '1', '+', '0'], ')'], '+', '1'], ')'], '+', '1'], ')'], '', ''] 

Los números provienen del symbol y el token de los módulos de Python, que puede utilizar para crear una tabla de búsqueda de números a nombres:

 map = dict(token.tok_name.items() + symbol.sym_name.items()) 

Incluso podría plegar esta asignación en la función shallow() para que pueda trabajar con cadenas en lugar de números:

 def shallow(ast): if not isinstance(ast, list): return ast if len(ast) == 2: return shallow(ast[1]) return [map[ast[0]]] + [shallow(a) for a in ast[1:]] >>> pprint.pprint(shallow(parser.st2list(parser.expr('(((1+0)+1)+1)')))) ['eval_input', ['atom', '(', ['arith_expr', ['atom', '(', ['arith_expr', ['atom', '(', ['arith_expr', '1', '+', '0'], ')'], '+', '1'], ')'], '+', '1'], ')'], '', ''] 

Stack es la mejor herramienta para el trabajo:

 import re def matches(line, opendelim='(', closedelim=')'): stack = [] for m in re.finditer(r'[{}{}]'.format(opendelim, closedelim), line): pos = m.start() if line[pos-1] == '\\': # skip escape sequence continue c = line[pos] if c == opendelim: stack.append(pos+1) elif c == closedelim: if len(stack) > 0: prevpos = stack.pop() # print("matched", prevpos, pos, line[prevpos:pos]) yield (prevpos, pos, len(stack)) else: # error print("encountered extraneous closing quote at pos {}: '{}'".format(pos, line[pos:] )) pass if len(stack) > 0: for pos in stack: print("expecting closing quote to match open quote starting at: '{}'" .format(line[pos-1:])) 

En el código del cliente, ya que la función se escribe como una función generadora, simplemente use el patrón de bucle for para desenrollar las coincidencias:

 line = '(((1+0)+1)+1)' for openpos, closepos, level in matches(line): print(line[openpos:closepos], level) 

Este código de prueba produce el siguiente en mi pantalla, notó que el segundo parámetro en la impresión indica la profundidad del paréntesis.

 1+0 2 (1+0)+1 1 ((1+0)+1)+1 0 

De una respuesta enlazada:

Desde la utilidad de conversión LilyPond (y escrita / con derechos de autor por mi misma, para que pueda mostrarla aquí):

 def paren_matcher (n): # poor man's matched paren scanning, gives up # after n+1 levels. Matches any string with balanced # parens inside; add the outer parens yourself if needed. # Nongreedy. return r"[^()]*?(?:\("*n+r"[^()]*?"+r"\)[^()]*?)*?"*n 

convert-ly tiende a usar esto como paren_matcher (25) en sus expresiones regulares, lo que probablemente sea excesivo para la mayoría de las aplicaciones. Pero luego lo usa para hacer coincidir expresiones de esquema.

Sí, se rompe después del límite dado, pero la capacidad de simplemente conectarlo en expresiones regulares aún supera las alternativas “correctas” que admiten una profundidad ilimitada en la facilidad de uso.

Los pares equilibrados (por ejemplo, entre paréntesis) es un ejemplo de un lenguaje que no se puede reconocer mediante expresiones regulares.

Lo que sigue es una breve explicación de las matemáticas de por qué es eso.

Las expresiones regulares son una manera de definir autómatas de estados finitos (FSM abreviado). Dicho dispositivo tiene una cantidad finita de estado posible para almacenar información. La forma en que se puede usar ese estado no está particularmente restringida, pero sí significa que hay un número máximo absoluto de posiciones distintas que puede reconocer.

Por ejemplo, el estado se puede utilizar para contar, por ejemplo, paréntesis izquierdos no coincidentes. Pero debido a que la cantidad de estado para ese tipo de conteo debe estar completamente delimitada, entonces un FSM dado puede contar hasta un máximo de n -1, donde n es el número de estados en que puede estar el FSM. Si n es, digamos, 10 , entonces el número máximo de paréntesis izquierdos no coincidentes que el FSM puede igualar es 10, hasta que se rompa. Como es perfectamente posible tener un paréntesis más, no hay un FSM posible que pueda reconocer correctamente el idioma completo de los paréntesis emparejados.

¿Y qué? Supongamos que acaba de elegir una n muy grande? El problema es que, como una forma de describir FSM, las expresiones regulares básicamente describen todas las transiciones de un estado a otro. Como para cualquier N, un FSM necesitaría 2 transiciones de estado (una para hacer coincidir un paréntesis izquierdo y otra para hacer coincidir a la derecha), la expresión regular en sí debe crecer al menos por un factor constante múltiplo de n

En comparación, la siguiente mejor clase de idiomas, (gramáticas sin contexto) puede resolver este problema de una manera totalmente compacta. Aquí hay un ejemplo en BNF

expression ::= ` ( ` expression ` ) ` expression
| nothing

Debe escribir un analizador adecuado para analizar dicha expresión (p. Ej., Usar pyparsing). Las expresiones regulares no son una herramienta adecuada para escribir analizadores decentes.

Puede usar expresiones regulares, pero necesita hacer la recursión usted mismo. Algo como lo siguiente es útil (si solo necesitas encontrar, como dice tu pregunta, todas las expresiones entre paréntesis):

 import re def scan(p, string): found = p.findall(string) for substring in found: stripped = substring[1:-1] found.extend(scan(p, stripped)) return found p = re.compile('\(.+\)') string = '(((1+0)+1)+1)' all_found = scan(p, string) print all_found 

Este código, sin embargo, no coincide con los paréntesis “correctos”. Si necesita hacer eso, estará mejor con un analizador especializado.

Aquí hay una demostración de tu pregunta, aunque es torpe, mientras funciona

 import re s = '(((1+0)+1)+1)' def getContectWithinBraces( x , *args , **kwargs): ptn = r'[%(left)s]([^%(left)s%(right)s]*)[%(right)s]' %kwargs Res = [] res = re.findall(ptn , x) while res != []: Res = Res + res xx = x.replace('(%s)' %Res[-1] , '%s') res = re.findall(ptn, xx) print(res) if res != []: res[0] = res[0] %('(%s)' %Res[-1]) return Res getContectWithinBraces(s , left='\(\[\{' , right = '\)\]\}') 

Mi solución es que: defina una función para extraer contenido dentro de los paréntesis más externos, y luego llame a esa función repetidamente hasta que obtenga el contenido dentro de los paréntesis más internos.

 def get_string_inside_outermost_parentheses(text): content_p = re.compile(r"(?<=\().*(?=\))") r = content_p.search(text) return r.group() def get_string_inside_innermost_parentheses(text): while '(' in text: text = get_string_inside_outermost_parentheses(text) return text 

Creo que esta función puede ser adecuada para su necesidad, lo junté rápido, así que siéntase libre de limpiarlo un poco. Al hacer nidos es fácil pensar en ello al revés y trabajar desde allí =]

 def fn(string,endparens=False): exp = [] idx = -1 for char in string: if char == "(": idx += 1 exp.append("") elif char == ")": idx -= 1 if idx != -1: exp[idx] = "(" + exp[idx+1] + ")" else: exp[idx] += char if endparens: exp = ["("+val+")" for val in exp] return exp 

Muchas publicaciones sugieren que para llaves anidadas, REGEX NO ES LA MANERA DE HACERLO. SIMPLEMENTE CUENTA LAS BRACES: Por ejemplo, vea: Expresión regular para detectar C ++ terminado en punto y coma para los bucles & while

Aquí hay una muestra completa de Python para iterar a través de una cadena y contar las llaves:

 # decided for nested braces to not use regex but brace-counting import re, string texta = r''' nonexistent.\note{Richard Dawkins, \textit{Unweaving the Rainbow: Science, Delusion and the Appetite for Wonder} (Boston: Houghton Mifflin Co., 1998), pp. 302, 304, 306-309.} more text and more. This is a statistical fact, not a guess.\note{Zheng Wu, \textit{Cohabitation: An Alternative Form of Family Living} (Ontario, Canada: Oxford University Press, 2000), p. 149; \hbox{Judith} Treas and Deirdre Giesen, ``Title and another title,'' \textit{Journal of Marriage and the Family}, February 2000, p.\,51} more and more text.capitalize ''' pos = 0 foundpos = 0 openBr = 0 # count open braces while foundpos <> -1: openBr = 0 foundpos = string.find(texta, r'\note',pos) # print 'foundpos',foundpos pos = foundpos + 5 # print texta[pos] result = "" while foundpos > -1 and openBr >= 0: pos = pos + 1 if texta[pos] == "{": openBr = openBr + 1 if texta[pos] == "}": openBr = openBr - 1 result = result + texta[pos] result = result[:-1] # drop the last } found. result = string.replace(result,'\n', ' ') # replace new line with space print result