Как разобрать строку и вернуть вложенный массив?

Question

Мне нужна функция Python, которая принимает строку и возвращает массив, где каждый элемент в массиве является либо символом, либо другим массивом такого типа. Вложенные массивы помечаются во входной строке, начиная с '(' и заканчивая ')'.

Таким образом, функция будет действовать так:

1) foo("abc") == ["a", "b", "c"]
2) foo("a(b)c") == ["a", ["b"], "c"]
3) foo("a(b(c))") == ["a", ["b", ["c"]]]
4) foo("a(b(c)") == error: closing bracket is missing
5) foo("a(b))c") == error: opening bracket is missing
6) foo("a)b(c") == error: opening bracket is missing

Примечание: я бы предпочел решение, которое является чисто функциональным.

Answer 1

def foo(s):
    def foo_helper(level=0):
        try:
            token = next(tokens)
        except StopIteration:
            if level != 0:
                raise Exception('missing closing paren')
            else:
                return []
        if token == ')':
            if level == 0:
                raise Exception('missing opening paren')
            else:
                return []
        elif token == '(':
            return [foo_helper(level+1)] + foo_helper(level)
        else:
            return [token] + foo_helper(level)
    tokens = iter(s)
    return foo_helper()

А также,

>>> foo('a((b(c))d)(e)')
['a', [['b', ['c']], 'd'], ['e']]

Answer 2

Итерационный.

def foo(xs):
    stack = [[]]
    for x in xs:
        if x == '(':
            stack[-1].append([])
            stack.append(stack[-1][-1])
        elif x == ')':
            stack.pop()
            if not stack:
                return 'error: opening bracket is missing'
                #raise ValueError('error: opening bracket is missing')
        else:
            stack[-1].append(x)
    if len(stack) > 1:
        return 'error: closing bracket is missing'
        #raise ValueError('error: closing bracket is missing')
    return stack.pop()

assert foo("abc") == ["a", "b", "c"]
assert foo("a(b)c") == ["a", ["b"], "c"]
assert foo("a(b(c))") == ["a", ["b", ["c"]]]
assert foo("a((b(c))d)(e)") == ['a', [['b', ['c']], 'd'], ['e']]
assert foo("a(b(c)") == "error: closing bracket is missing"
assert foo("a(b))c") == "error: opening bracket is missing"
assert foo("a)b(c") == 'error: opening bracket is missing'

Answer 3

С помощью regex а также ast.literal_eval

>>> import re
>>> from ast import literal_eval
>>> def listit(t):
...         return list(map(listit, t)) if isinstance(t, (list, tuple)) else t
... 
def solve(strs):
    s = re.sub(r'[A-Za-z]', "'\g<0>',", strs)
    s = re.sub(r"\)", "\g<0>,", s)
    try: return listit( literal_eval('[' + s  + ']') )
    except : return "Invalid string! "
...     
>>> solve("abc")
['a', 'b', 'c']
>>> solve("a(b)c")
['a', ['b'], 'c']
>>> solve("a(b(c))")
['a', ['b', ['c']]]
>>> solve("a(b(c)")
'Invalid string! '
>>> solve("a)b(c")
'Invalid string! '
>>> solve("a(b))c")
'Invalid string! '
>>> solve('a((b(c))d)(e)')
['a', [['b', ['c']], 'd'], ['e']]

Answer 4

Я бы предложил два пути:

Либо запрограммируйте свой собственный анализатор рекурсивного спуска, как здесь, либо используйте pyparsing, что-то вроде

import pyparsing as pp
expr = pp.Forward()
expr << pp.Word(pp.alphas) + pp.Optional('(' + expr + ')') + pp.Optional(pp.Word(pp.alphas))

здесь вы описываете рекурсивное выражение как последовательность альфа, которая может чередоваться с помощью сбалансированных скобок. Когда вы проверите этот пример для выходных данных, вы увидите, как получить желаемую выходную структуру (хотя это потребует некоторой настройки на вашей стороне и некоторых знаний о pyparsing).

С уважением Маркус

Answer 5

def parse_nested(iterator, level=0):
    result = []
    for c in iterator:
        if c == '(':
            result.append(parse_nested(iterator, level+1))
        elif c == ')':
            if level:
                return result
            else:
                raise ValueError("Opening parenthesis missing")
        else:
            result.append(c)
    if level:
        raise ValueError("Closing parenthesis missing")
    else:
        return result

print parse_nested(iter('a((b(c))d)(e)'))       

Answer 6

Один довольно быстрый и неприятный подход (только для чего-то другого):

import json, re

def foo(x):
    # Split continuous strings
    # Match consecutive characters
    matches = re.findall('[a-z]{2,}', x)
    for m in matches:
        # Join with ","
        x = x.replace(m, '","'.join(y for y in list(m))) 

    # Turn curvy brackets into square brackets
    x = x.replace(')', '"],"')
    x = x.replace('(', '",["')

    # Wrap whole string with square brackets
    x = '["'+x+'"]'

    # Remove empty entries
    x = x.replace('"",', '')
    x = x.replace(',""', '')

    try:
        # Load with JSON
        return json.loads(x)
    except:
        # TODO determine error type
        return "error"

def main():
    print foo("abc")     # ['a', 'b', 'c']
    print foo("a(b)c")   # ['a', ['b'], 'c']
    print foo("a(b(c))") # ['a', ['b', ['c']]]
    print foo("a(b))c")  # error

    print foo('a((b(c))d)(e)') # ['a', [['b', ['c']], 'd'], ['e']]

Answer 7

Рекурсия - это нечто очень мощное, что вы должны попытаться использовать.

Вот мой код:

    # encoding: utf-8
    # Python33

    def check(s):
        cs = [c for c in s if c == '(' or c ==')']
        flag = 0
        for c in cs:
            if flag < 0:
                return 'opening bracket is missing'        
            if c == '(':
                flag += 1
            else:
                flag -= 1
        if flag < 0:
            return 'opening bracket is missing'
        elif flag > 0:
            return 'closing bracket is missing'
        else:
            return ''

    def _foo(cs):
        result = []
        while len(cs):
            c = cs.pop(0)
            if c == '(':
                result.append(_foo(cs))
            elif c == ')':
                return result
            else:
                result.append(c)
        return result

    def foo(s):
        valiad = check(s)
        if valiad:
            return valiad
        cs = list(s)
        return _foo(cs)

    if __name__ == '__main__':
        ss = ["abc","a(b)c","a(b(c))","a(b(c)","a(b))c","a)b(c"]
        for s in ss:
            print(foo(s))