樹形結構作爲字符串 - 如何匹配嵌套大括號？

我有一個樹結構設置，並希望將其保存到/讀取一個字符串，用最少量的文本（所以XML序列化出）。我爲此設置了一個簡單的（或者我認爲）的結構，但是不知道如何讀取它，所以我的結構很可能不得不改變。讓我用一個例子來演示。樹形結構作爲字符串 - 如何匹配嵌套大括號？

我的樹由X的，Y在下面的示例中的座標，如：

[a,b] 
    |-----| 
[c,d] [e,f] 
     |-----|-----| 
     [g,h] [i,j] [k,l]

當我運行我的算法把此樹爲一個字符串，我得到下面的輸出：

a,b(c,d()e,f(g,h()i,j()k,l()))

而且這裏我使用的代碼：

public string SerializeMe() 
{ 
    StringBuilder ret = new StringBuilder(this.Value.ToString()) 
    ret.Append("("); 
    foreach (SimpleTreeNode<T> child in _Children) 
    { 
     ret.Append(child.SerializeMe()); 
    } 
    ret.Append(")"); 
    return ret.ToString(); 
}

那偉大工程，但現在我不能解析的S重新回到我的樹結構。我可以得到子字符串到第一個大括號並將其轉換爲節點的值，但我不確定如何將字符串的其餘部分拆分爲子節點。有沒有什麼方法可以輕鬆找到開口大括號，然後找到大括號？我研究過一些複雜的正則表達式，我無法正常工作，很快就完全失去了。

有沒有人有任何想法？

編輯：
這裏是我到目前爲止的代碼：

public static SimpleTreeNode<SPoint> ParsePointTree(string input) 
{ 
    //if the input string is empty, there is no node here. Return null. 
    if (string.IsNullOrEmpty(input)) return null; 
    else 
    { 
     //get the value from the first part of the string 
     string valString = input.Substring(0, input.IndexOf('(')); 
     SPoint value = (SPoint)valString; 
     SimpleTreeNode<SPoint> node = new SimpleTreeNode<SPoint>(value); 

     //now we have the child nodes enclosed in brackets 
     string innerstring = input.Substring(input.IndexOf('(')); 

     List<string> children = new List<string>(); 
     // how do we split innerstring into siblings?? // 

     foreach (string child in children) 
     { 
      node.Children.Add(SimpleTreeNode<SPoint>.ParsePointTree(child)); 
     } 

     return node; 
    } 
}

我遇到的問題是，我會得到一個必須分成兄弟姐妹的字符串。在上面的示例中，c,d和e,f是兄弟姐妹，以(c,d()e,f(g,h()i,j()k,l()))的形式表示。我需要將此字符串拆分爲c,d()和e,f(g,h()i,j()k,l())，這是我卡住的地方。

來源

2011-07-07 death_au

試過遞歸解析？ –

此外，請向我們顯示您的解析代碼，而不是您的序列號代碼... –

馬克艾略特是正確的。請注意，您構建您的輸出遞歸。可能最簡單，如果你遞歸地解析它，並且每個解析級別都建立你的發射（...）對內的子樹。 –

您可以使用堆棧和2個局部變量來解析類似的字符串。如果使用廣度優先遍歷而不是深度優先序列化樹，堆棧就不是必需的（順便說一句，在任何情況下都不必遞歸）。

遞歸解決方案只是使用調用堆棧，並可能導致堆棧溢出 - see here for a better explanation爲什麼這不是最好的方法。

foreach (char c in "a(c()e(g()i()k()))") 
{ 
    if (c == '(') 
    { 
     Stack.Push(Parent); 
     Parent = Child; 
    } 
    else if (c == ')') 
    { 
     Child = Parent; 
     Parent = Stack.Pop(); 
    } 
    else 
    { 
     Child = new SimpleTreeNode() { Value = c }; 
     Parent.Children.Add(Child); 
    } 
}

來源

2011-07-07 05:42:21 gordy

解決方案與此不完全相同，因爲每個節點的值都不止一個字符，但方法的主體是我最終使用的。而且我的節點上有一個父屬性，所以我也不需要這個堆棧。感謝提示 –

我編輯了關於父屬性的筆記 - 消除了按照特定順序對樹進行編碼所需的堆棧。您可能想嘗試向樣本中的[c，d]添加一些孩子，以確保它仍然正常工作！ – gordy

像這樣（僞代碼）：

function parse() = 
    label = read_until('(',')'); 
    read_char('(') 
    children = [] 
    while not peek_char(')') do 
     child = parse() 
     children.add(child) 
    read_char(')') 
    return new Node(label,children)

read_until(...)讀取，直到但不包括指定的字符。
read_char(c)讀取一個字符，如果不匹配會引發錯誤。
peek_char(c)查看下一個字符，並返回指示它是否匹配的真值。

來源

2011-07-07 05:33:09

樹形結構作爲字符串 - 如何匹配嵌套大括號？

回答

相關問題