我正在開發這個正在開發的算法，需要幫助。我有以下格式的一種樹的輸入：如何解析python中的括號樹？
（根（AB（ABC）（CBA））（CD（CDE）（FGH）））
這看起來這下面的樹。
Root
|
____________
AB CD
| |
__________ ___________
ABC CBA CDE FGH
什麼算法是假設讀在括號格式，並提供以下的輸出：
Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH
它列出了根及其子女和有孩子的所有其他家長。 我無法理解如何啓動這個，有人可以幫我給我提示或給一些參考或鏈接？
遞歸下降解析器解析器是一個簡單的形式，可以解析很多語法。雖然整個解析理論對於堆棧溢出答案來說太大，但最常見的解析方法涉及兩個步驟：首先，標記化（tokenisation），它提取字符串的子字詞（這裏可能是'Root'和'ABC'或'（'和'）'括號），然後使用遞歸函數進行解析。
該代碼解析輸入（如您的示例），生成所謂的解析樹，並且還具有一個函數'show_children'，該函數接受解析樹，並根據問題生成表達式的子視圖。
import re
class ParseError(Exception):
pass
# Tokenize a string.
# Tokens yielded are of the form (type, string)
# Possible values for 'type' are '(', ')' and 'WORD'
def tokenize(s):
toks = re.compile(' +|[A-Za-z]+|[()]')
for match in toks.finditer(s):
s = match.group(0)
if s[0] == ' ':
continue
if s[0] in '()':
yield (s, s)
else:
yield ('WORD', s)
# Parse once we're inside an opening bracket.
def parse_inner(toks):
ty, name = next(toks)
if ty != 'WORD': raise ParseError
children = []
while True:
ty, s = next(toks)
if ty == '(':
children.append(parse_inner(toks))
elif ty == ')':
return (name, children)
# Parse this grammar:
# ROOT ::= '(' INNER
# INNER ::= WORD ROOT* ')'
# WORD ::= [A-Za-z]+
def parse_root(toks):
ty, _ = next(toks)
if ty != '(': raise ParseError
return parse_inner(toks)
def show_children(tree):
name, children = tree
if not children: return
print '%s -> %s' % (name, ' '.join(child[0] for child in children))
for child in children:
show_children(child)
example = '(Root (AB (ABC) (CBA)) (CD (CDE) (FGH)))'
show_children(parse_root(tokenize(example)))
Python的缺陷之一（至少CPython）是一個相對較淺的最大堆棧深度。這是很好的，乾淨的代碼，但它依賴於Python堆棧，所以它會限制它可以解析的樹的深度。其他解決方案，例如我發佈的解決方案，可以處理非常深的樹木。如果這解決了問題，我會保持原樣，因爲我喜歡簡單性，但是可以重寫爲使用「list」作爲堆棧來保持狀態，然後它可以將非常深的樹解析爲好。 – steveha
我認爲在Python中解析最流行的解決方案是PyParsing。 PyParsing附帶了解析S表達式的語法，您應該可以使用它。討論這個StackOverflow的答案：
試試這個：
def toTree(expression):
tree = dict()
msg =""
stack = list()
for char in expression:
if(char == '('):
stack.append(msg)
msg = ""
elif char == ')':
parent = stack.pop()
if parent not in tree:
tree[parent] = list()
tree[parent].append(msg)
msg = parent
else:
msg += char
return tree
expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))"
print toTree(expression)
它返回一個字典，其中根可以用鑰匙'來訪問。然後你可以做一個簡單的BFS來打印輸出。
OUTPUT：
{
'' : ['Root'],
'AB' : ['ABC', 'CBA'],
'Root': ['AB', 'CD'],
'CD' : ['CDE', 'FGH']
}
您必須消除表達所有的空格，您開始之前，或通過添加以下作爲的第一行用於忽略表達inrrelevant charaters -loop：
if char == <IRRELEVANT CHARACTER>:
continue
上述代碼將在O（n）時間運行，其中n是表達式的長度。
EDIT
這裏是打印功能：
def printTree(tree, node):
if node not in tree:
return
print '%s -> %s' % (node, ' '.join(child for child in tree[node]))
for child in tree[node]:
printTree(tree, child)
期望的輸出可通過以下來實現：
expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))"
tree = toTree(expression)
printTree(tree, tree[''][0])
輸出
Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH
編輯
假設節點名稱不是唯一的，我們只需要給新名稱的節點。
def parseExpression(expression):
nodeMap = dict()
counter = 1
node = ""
retExp =""
for char in expression:
if char == '(' or char == ')' :
if (len(node) > 0):
nodeMap[str(counter)] = node;
retExp += str(counter)
counter +=1
retExp += char
node =""
elif char == ' ': continue
else :
node += char
return retExp,nodeMap
打印功能現在將變爲：
expression = " (Root(SQ (VBZ) (NP (DT) (NN)) (VP (VB) (NP (NN)))))"
expression, nodeMap = parseExpression(expression)
tree = toTree(expression)
printTree(tree, tree[''][0], nodeMap)
輸出：
Root -> SQ
SQ -> VBZ NP VP
NP -> DT NN
VP -> VB NP
NP -> NN
def printTree(tree, node, nodeMap):
if node not in tree:
return
print '%s -> %s' % (nodeMap[node], ' '.join(nodeMap[child] for child in tree[node]))
for child in tree[node]:
printTree(tree, child, nodeMap)
輸出可以通過使用獲得這是可以做到用
您使用的表示是基於Lisp的S表達式s，這可以幫助你的谷歌搜索，如果沒有別的.. –
提示：您將要使用的主要數據結構是一個堆棧，最上面的項目是您要添加的孩子的節點。 –