balanceados - Python analizando bloques entre corchetes

title in python plot

Question

¿Cuál sería la mejor manera en Python para analizar los fragmentos de texto contenidos en los paréntesis correspondientes?

"{ { a } { b } { { { c } } } }"

debería regresar inicialmente:

[ "{ a } { b } { { { c } } }" ]

poniéndolo como una entrada debería regresar:

[ "a", "b", "{ { c } }" ]

que debería regresar:

[ "{ c }" ]

[ "c" ]

[]

Answer 1

Aquí hay una solución que se me ocurrió para un caso de uso similar. Esto estaba basado libremente en la respuesta del código de psuedo aceptado. No quería agregar ninguna dependencia para bibliotecas externas:

def parse_segments(source, recurse=False):
    """
    extract any substring enclosed in parenthesis
    source should be a string
    """
    unmatched_count = 0
    start_pos = 0
    opened = False
    open_pos = 0
    cur_pos = 0

    finished = []
    segments = []

    for character in source:
        #scan for mismatched parenthesis:
        if character == ''('':
            unmatched_count += 1
            if not opened:
                open_pos = cur_pos
            opened = True

        if character == '')'':
            unmatched_count -= 1

        if opened and unmatched_count == 0:
            segment = source[open_pos:cur_pos+1]
            segments.append(segment)
            clean = source[start_pos:open_pos]
            if clean:
                finished.append(clean)
            opened = False
            start_pos = cur_pos+1

        cur_pos += 1

    assert unmatched_count == 0

    if start_pos != cur_pos:
        #get anything that was left over here
        finished.append(source[start_pos:cur_pos])

    #now check on recursion:
    for item in segments:
        #get rid of bounding parentheses:
        pruned = item[1:-1]
        if recurse:
            results = parse_tags(pruned, recurse)
            finished.expand(results)
        else:
            finished.append(pruned)

    return finished

Answer 2

O esta versión de pyparsing:

>>> from pyparsing import nestedExpr
>>> txt = "{ { a } { b } { { { c } } } }"
>>>
>>> nestedExpr(''{'',''}'').parseString(txt).asList()
[[[''a''], [''b''], [[[''c'']]]]]
>>>

Answer 3

Parse usando lepl (instalable vía $ easy_install lepl ):

from lepl import Any, Delayed, Node, Space

expr = Delayed()
expr += ''{'' / (Any() | expr[1:,Space()[:]]) / ''}'' > Node

print expr.parse("{{a}{b}{{{c}}}}")[0]

Salida:

Node +- ''{'' +- Node | +- ''{'' | +- ''a'' | `- ''}'' +- Node | +- ''{'' | +- ''b'' | `- ''}'' +- Node | +- ''{'' | +- Node | | +- ''{'' | | +- Node | | | +- ''{'' | | | +- ''c'' | | | `- ''}'' | | `- ''}'' | `- ''}'' `- ''}''

Answer 4

Pseudocódigo:

For each string in the array:
    Find the first ''{''. If there is none, leave that string alone.
    Init a counter to 0. 
    For each character in the string:  
        If you see a ''{'', increment the counter.
        If you see a ''}'', decrement the counter.
        If the counter reaches 0, break.
    Here, if your counter is not 0, you have invalid input (unbalanced brackets)
    If it is, then take the string from the first ''{'' up to the ''}'' that put the
     counter at 0, and that is a new element in your array.

Answer 5

Si desea utilizar un analizador (lepl en este caso), pero aún desea los resultados intermedios en lugar de una lista analizada final, entonces creo que este es el tipo de cosa que estaba buscando:

>>> nested = Delayed()
>>> nested += "{" + (nested[1:,...]|Any()) + "}"
>>> split = (Drop("{") & (nested[:,...]|Any()) & Drop("}"))[:].parse
>>> split("{{a}{b}{{{c}}}}")
[''{a}{b}{{{c}}}'']
>>> split("{a}{b}{{{c}}}")
[''a'', ''b'', ''{{c}}'']
>>> split("{{c}}")
[''{c}'']
>>> split("{c}")
[''c'']

Eso puede parecer opaco al principio, pero en realidad es bastante simple: o)

anidado es una definición recursiva de un parche para paréntesis anidados (el "+" y [...] en la definición guardan todo como una sola cadena después de que se haya emparejado). A continuación, split dice que coinciden todos los posibles ("[:]") de algo que está rodeado por "{" ... "}" (que descartamos con "Drop") y contiene una expresión anidada o cualquier letra.

Finalmente, aquí hay una versión lepl del analizador "todo en uno" que da un resultado en el mismo formato que el ejemplo de pyparsing anterior, pero que (creo) es más flexible sobre cómo aparecen los espacios en la entrada:

>>> with Separator(~Space()[:]):
...     nested = Delayed()
...     nested += Drop("{") & (nested[1:] | Any()) & Drop("}") > list
...
>>> nested.parse("{{ a }{ b}{{{c}}}}")
[[[''a''], [''b''], [[[''c'']]]]]

Answer 6

Solución más limpia. Esto encontrará devolver la cadena encerrada en el soporte más externo. Si se devuelve None, no hubo coincidencia.

def findBrackets( aString ):
   if ''{'' in aString:
      match = aString.split(''{'',1)[1]
      open = 1
      for index in xrange(len(match)):
         if match[index] in ''{}'':
            open = (open + 1) if match[index] == ''{'' else (open - 1)
         if not open:
            return match[:index]

Answer 7

Soy un poco nuevo en Python, así que no me moleste, pero aquí hay una implementación que funciona:

def balanced_braces(args):
    parts = []
    for arg in args:
        if ''{'' not in arg:
            continue
        chars = []
        n = 0
        for c in arg:
            if c == ''{'':
                if n > 0:
                    chars.append(c)
                n += 1
            elif c == ''}'':
                n -= 1
                if n > 0:
                    chars.append(c)
                elif n == 0:
                    parts.append(''''.join(chars).lstrip().rstrip())
                    chars = []
            elif n > 0:
                chars.append(c)
    return parts

t1 = balanced_braces(["{{ a } { b } { { { c } } } }"]);
print t1
t2 = balanced_braces(t1)
print t2
t3 = balanced_braces(t2)
print t3
t4 = balanced_braces(t3)
print t4

Salida:

[''{ a } { b } { { { c } } }'']
[''a'', ''b'', ''{ { c } }'']
[''{ c }'']
[''c'']

Answer 8

También podría analizarlos todos a la vez, aunque me parece que {a} significa "a" lugar de ["a"] poco extraño. Si entendí el formato correctamente:

import re
import sys


_mbrack_rb = re.compile("([^{}]*)}") # re.match doesn''t have a pos parameter
def mbrack(s):
  """Parse matching brackets.

  >>> mbrack("{a}")
  ''a''
  >>> mbrack("{{a}{b}}")
  [''a'', ''b'']
  >>> mbrack("{{a}{b}{{{c}}}}")
  [''a'', ''b'', [[''c'']]]

  >>> mbrack("a")
  Traceback (most recent call last):
  ValueError: expected left bracket
  >>> mbrack("{a}{b}")
  Traceback (most recent call last):
  ValueError: more than one root
  >>> mbrack("{a")
  Traceback (most recent call last):
  ValueError: expected value then right bracket
  >>> mbrack("{a{}}")
  Traceback (most recent call last):
  ValueError: expected value then right bracket
  >>> mbrack("{a}}")
  Traceback (most recent call last):
  ValueError: unbalanced brackets (found right bracket)
  >>> mbrack("{{a}")
  Traceback (most recent call last):
  ValueError: unbalanced brackets (not enough right brackets)
  """
  stack = [[]]
  i, end = 0, len(s)
  while i < end:
    if s[i] != "{":
      raise ValueError("expected left bracket")
    elif i != 0 and len(stack) == 1:
      raise ValueError("more than one root")
    while i < end and s[i] == "{":
      L = []
      stack[-1].append(L)
      stack.append(L)
      i += 1
    stack.pop()
    stack[-1].pop()
    m = _mbrack_rb.match(s, i)
    if m is None:
      raise ValueError("expected value then right bracket")
    stack[-1].append(m.group(1))
    i = m.end(0)
    while i < end and s[i] == "}":
      if len(stack) == 1:
        raise ValueError("unbalanced brackets (found right bracket)")
      stack.pop()
      i += 1
  if len(stack) != 1:
    raise ValueError("unbalanced brackets (not enough right brackets)")
  return stack[0][0]


def main(args):
  if args:
    print >>sys.stderr, "unexpected arguments: %r" % args
  import doctest
  r = doctest.testmod()
  print r
  return r[0]

if __name__ == "__main__":
  sys.exit(main(sys.argv[1:]))

Answer 9

Usando Grako (compilador de gramática) :

#!/usr/bin/env python
import json
import grako # $ pip install grako

grammar_ebnf = """
    bracketed = ''{'' @:( { bracketed }+ | any ) ''}'' ;
    any = /[^{}]+?/ ;
"""
model = grako.genmodel("Bracketed", grammar_ebnf)
ast = model.parse("{ { a } { b } { { { c } } } }", "bracketed")
print(json.dumps(ast, indent=4))

Salida

[
    "a", 
    "b", 
    [
        [
            "c"
        ]
    ]
]