展開樹形數據結構

我正在嘗試使用Python來改變一些使用re模塊（即re.sub）的文本字符串。不過，我認爲我的問題適用於其他正則表達式實現的語言。展開樹形數據結構

我有一些代表樹狀數據結構的字符串。他們看起來像這樣：

(A,B)-C-D 
A-B-(C,D) 
A-(B,C,D-(E,F,G,H,I))

每個字母代表分支或邊緣。括號中的字母表示進入或離開另一分支的分支。

無處不在，有一個「普通」的元組值（一個只有逗號分隔的單個字母的元組），我想採用該元組的前綴（X-）或後綴（-X）並將其應用於元組中的每個值。

在這種變換中，上述字符串將成爲

(A-C,B-C)-D 
A-(B-C,B-D) 
A-(B,C,(D-E,D-F,D-G,D-H,D-I))

應用該方法反覆將最終得到

(A-C-D,B-C-D) 
(A-B-C,A-B-D) 
(A-B,A-C,A-D-E,A-D-F,A-D-G,A-D-H,A-D-I)

在這些元組中的字符串然後表示通過樹開始於根的路徑並結束於一片葉子。

任何使用正則表達式（或其他方法）完成此任務的幫助將不勝感激。

來源

2011-09-07 cytochrome

你不能用正則表達式來做這件事，因爲你必須處理嵌套結構。相反，您可以使用pyparsing's nestedExpr

來源

2011-09-07 16:18:54 koehlma

謝謝您的建議。我會看看pyparsing。 – cytochrome

這與包含在pyparsing wiki（http://pyparsing.wikispaces.com）的Examples頁面中的正則表達式反轉示例非常相似。 – PaulMcG

您正在描述的問題是枚舉圖中的路徑之一。

您描述了三種圖形

A B 
\/
    C 
    | 
    D 

    A 
    | 
    B 
/\ 
C D 

    A 
/| \ 
B C D 
    // | \\ 
    E F G H I

，併爲每個要枚舉路徑。這涉及在任意嵌套結構中分配值。如果這可以用正則表達式來完成，但我不確定它是否可以完成，我相信在的幾次通過。

雖然我的感覺是你的問題，但最好通過解析你的字符串到一個圖形結構然後枚舉路徑來解決。如果您不想實際構建圖形，則可以在用戶提供的操作中爲解析器生成器生成字符串。

基於正則表達式的解決方案必須知道如何處理這兩個

(A,B)-C

和

(A,B,C,D,E,F,G,H)-I

可以匹配這些字符串與

\([A-Z](,[A-Z])*\)-[A-Z]

但如何將你「分發「的所有submatches沒有一些邏輯？因爲無論如何你都需要這個邏輯，所以你可以在真正的圖形結構上執行它。你也可以在一個字符串本身上做到這一點，但最好在解析器生成器的幫助下完成此任務，該生成器可以處理上下文無關或上下文敏感的結構。

來源

2011-09-07 16:23:35

謝謝您的見解和建議。我曾考慮將字符串解析爲一個更傳統的圖形表示形式，但不清楚這是否會讓我建議的路線更容易些。不過，我會試試看。 – cytochrome

在發表我的評論引用pyparsing的invRegex示例之後，我更仔細地看了一下您的輸入，看起來您可以將其解釋爲中綴表示法，其中'，'和' - '是二元運算符。 Pyparsing有一個名爲operatorPrecedence的幫助器方法，它根據運算符的優先級解析表達式，並將其分組在括號中。（這有更多一點的智慧把它比只使用nestedExpr helper方法，它匹配嵌套組符號中的表達式。）因此，這裏是使用operatorPrecedence解析器的工具入門版本：

data = """\ 
(A,B)-C-D 
A-B-(C,D) 
A-(B,C,D-(E,F,G,H,I))""".splitlines() 


from pyparsing import alphas, oneOf, operatorPrecedence, opAssoc 

node = oneOf(list(alphas)) 
graphExpr = operatorPrecedence(node, 
    [ 
    ('-', 2, opAssoc.LEFT), 
    (',', 2, opAssoc.LEFT), 
    ]) 

for d in data: 
    print graphExpr.parseString(d).asList()

Pyparsing實際收益一個類型爲ParseResults的複雜結構，它支持對解析的記號作爲列表中的元素，字典中的項目或對象中的屬性進行訪問。通過調用asList，我們只需獲取簡單列表形式的元素。

以上表明，我們看起來是在正確的軌道上的輸出：

[[['A', ',', 'B'], '-', 'C', '-', 'D']] 
[['A', '-', 'B', '-', ['C', ',', 'D']]] 
[['A', '-', ['B', ',', 'C', ',', ['D', '-', ['E', ',', 'F', ',', 'G', ',', 'H', ',', 'I']]]]]

Pyparsing也可以讓你的回調或parse actions重視個人表現，在分析時被調用。例如，該解析動作確實分析時轉化爲整數：

def toInt(tokens): 
    return int(tokens[0]) 
integer = Word(nums).setParseAction(toInt)

當該值在ParseResults被返回，它已經被轉換爲整數。

也可以將類指定爲分析操作，並將ParseResults對象傳遞給該類的__init__方法並返回結果對象。我們可以在operatorPrecedence中指定分析動作，方法是在每個運算符的描述符元組中添加分析動作作爲第4個元素。

這裏是二元運算符基類：

class BinOp(object): 
    def __init__(self, tokens): 
     self.tokens = tokens 
    def __str__(self): 
     return self.__class__.__name__ + str(self.tokens[0][::2]) 
    __repr__ = __str__

從這個基類，我們可以推導出2子類，每一個運營商-和,：

class Path(BinOp): 
    pass 

class Branch(BinOp): 
    pass

，並將它們添加到operatorPrecedence中的運算符定義元組：

node = oneOf(list(alphas)) 
graphExpr = operatorPrecedence(node, 
    [ 
    ('-', 2, opAssoc.LEFT, Path), 
    (',', 2, opAssoc.LEFT, Branch), 
    ]) 


for d in data: 
    print graphExpr.parseString(d).asList()

這使我們對象的每個輸入串的嵌套結構：

[Path[Branch['A', 'B'], 'C', 'D']] 
[Path['A', 'B', Branch['C', 'D']]] 
[Path['A', Branch['B', 'C', Path['D', Branch['E', 'F', 'G', 'H', 'I']]]]]

的從這種結構中路徑的生成留給讀者作爲練習爲OP。（pyparsing正則表達式逆變器使用一系列發生器執行此操作 - 希望一些簡單的遞歸就足夠了。）

來源

2011-09-08 11:03:02 PaulMcG

謝謝你的建議，保羅。這可能會使更多拓撲復雜的樹字符串更可行。 – cytochrome

展開樹形數據結構

回答

相關問題