我的字符串格式为“ AB(AB(DDC)C)A(BAAC)DAB(ABC)”.

>每个字符代表一个元素(A,B,C或D).
>在右括号之间,每个元素都有一个子元素(可能不存在).

例如,具有“ AB(AB(DDC)C)A(BAAC)DA”,顶层将是AB(AB(DDC)C)A(BAAC)DA. [A,B,A,D,A],相应的子代将为[无,AB(DDC)C,BAAC,无,无].儿童也将被递归解析.

我在这里实现了一个解决方案：

def parse_string(string):

    i = 0                                                                       
    parsed = []                                                                 

    while i < len(string):                                                      
        if string[i] in ('A', 'B', 'C', 'D'):                                        
            parsed.append([string[i], None])                                    
            i += 1                                                              
        elif string[i] == '(':                                                  
            open_brakets = 1                                                    
            i += 1                                                              
            j = i                                                               
            while open_brakets:                                                 
                if string[j] == '(':                                            
                    open_brakets += 1                                           
                elif string[j] == ')':                   
                    open_brakets -= 1                    
                j += 1
            # Parse the children as well
            parsed[-1][-1] = parse_string(string[i:j - 1])       
            i = j                                                               
        else:                                                                   
            i += 1                                                              

    return parsed

print parse_string('AB(AB(DDC)C)A(BAAC)DAB(ABC)') 

尽管我认为这有点丑陋,但我确信它不是很有效.

我想知道是否有一种方法可以使Python更清洁/更快/更优雅？允许使用外部库(特别是如果它们是用C！:-P编写的).

更新资料

其他应该起作用的字符串示例：

> ABC(DAB(ACB)BBB(AAA)ABC)DCB

通常,字符串的长度不受限制,子代的数目,长度,嵌套级别的数目均不受限制.

解决方法:

如果您还需要递归地解析内部括号：

def parse_tree(tree, string, start=0):
    index = start
    while index < len(string):
        current = string[index]
        if current == "(":
            child = tree[-1][1]
            child_parsed = parse_tree(child, string, index+1)
            index += child_parsed + 2 # adds 2 for the parentheses
        elif current == ")":
            break
        else:
            tree.append((current, []))
            index += 1
    return index - start
tree = []
print(parse_tree(tree, 'abc(abc(defg)d)de(f)gh'))

可以将其视为状态机.状态机接受节点定义,直到看到一个开放的括号,然后在其中将新的上下文(即递归函数调用)推送到解析堆栈以解析括号的内容.解析内部上下文时,右括号会弹出上下文.

如果您具有更复杂的语法,则可以更好地扩展的另一种选择是使用诸如PyParsing之类的解析库：

from pyparsing import OneOrMore, Optional, oneOf, alphas, Word, Group, Forward, Suppress, Dict

# define the grammar
nodes = Forward()
nodeName = oneOf(list(alphas))
nodeChildren = Suppress('(') + Group(nodes) + Suppress( ')')
node = Group(nodeName + Optional(nodeChildren))
nodes <<= OneOrMore(node)

print(nodes.parseString('abc(abc(defg)d)de(f)gh'))

像PyParsing这样的解析库允许您定义一个易于阅读的说明性语法.

原始非递归解析的答案：一种方法是使用itertools(累积仅来自Python 3.2及更高版本,itertools文档的旧版本为pure python implementation of accumulate).这样可以避免使用索引：

from itertools import takewhile, accumulate
PARENS_MAP = {'(': 1, ')': -1}
def parse_tree(tree, string):
    string = iter(string)
    while string:
        current = next(string)
        if current == "(":
            child = iter(string)
            child = ((c, PARENS_MAP.get(c, 0)) for c in child)
            child = accumulate(child, lambda a,b: (b[0], a[1]+b[1]))
            child = takewhile(lambda c: c[1] >= 0, child)
            child = (c[0] for c in child)
            tree[-1][1] = "".join(child)
        else:
            tree.append([current, None])
print(parse_tree('abc(abc(defg)d)de(f)gh'))

我不确定它是更快还是更优雅,但是我认为使用显式索引更容易编写,理解和修改.