Каким будет лучший способ в Python проанализировать фрагменты текста, содержащиеся в соответствующих скобках?
"{ { a } { b } { { { c } } } }"
должен первоначально возвращаться:
[ "{ a } { b } { { { c } } }" ]
поместив это как возвращаемый вход:
[ "a", "b", "{ { c } }" ]
который должен вернуться:
[ "{ c }" ]
[ "c" ]
[]
псевдокод:
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.
Или эта версия pyparsing:
>>> from pyparsing import nestedExpr
>>> txt = "{ { a } { b } { { { c } } } }"
>>>
>>> nestedExpr('{','}').parseString(txt).asList()
[[['a'], ['b'], [[['c']]]]]
>>>
Я как бы новичок в Python, так что легко на меня, но вот реализация, которая работает:
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
Вывод:
['{ a } { b } { { { c } } }']
['a', 'b', '{ { c } }']
['{ c }']
['c']
Разбор с использованием lepl (устанавливается через $ 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]
Вывод:
Node
+- '{'
+- Node
| +- '{'
| +- 'a'
| `- '}'
+- Node
| +- '{'
| +- 'b'
| `- '}'
+- Node
| +- '{'
| +- Node
| | +- '{'
| | +- Node
| | | +- '{'
| | | +- 'c'
| | | `- '}'
| | `- '}'
| `- '}'
`- '}'
Вы также можете разобрать их все сразу, хотя я считаю, что {a} означает "a", а не ["a"] немного странно. Если я правильно понял формат:
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:]))
Если вы хотите использовать парсер (lepl в этом случае), но все же хотите получить промежуточные результаты, а не окончательный разобранный список, тогда я думаю, что это именно то, что вы искали:
>>> 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']
Это может выглядеть непрозрачно сначала, но это довольно просто: o)
Вложенное является рекурсивным определением сопряжения для вложенных скобок ( "+" и [...] в определении сохраняют все как одну строку после того, как она была сопоставлена). Затем split говорит совпадение как можно больше ( "[:]" ) того, что окружает "{"... "}" (которое мы отбрасываем с "Drop" ) и содержит либо вложенное выражение, либо любую букву.
Наконец, вот лепл-версия синтаксического анализа "все в одном", который дает результат в том же формате, что и предыдущий пример pyparsing, но который (я считаю) более гибкий в отношении того, как пробелы появляются во входном файле:
>>> with Separator(~Space()[:]):
... nested = Delayed()
... nested += Drop("{") & (nested[1:] | Any()) & Drop("}") > list
...
>>> nested.parse("{{ a }{ b}{{{c}}}}")
[[['a'], ['b'], [[['c']]]]]
Более чистое решение. Это вернет строку, заключенную в самую внешнюю скобку. Если None возвращается, совпадения не было.
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]
Использование Grako (компилятор грамматики):
#!/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))
[
"a",
"b",
[
[
"c"
]
]
]
Вот решение, которое я придумал для аналогичного варианта использования. Это было свободно основано на принятом ответе на код psuedo. Я не хотел добавлять зависимости для внешних библиотек:
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