文字列として表されるツリーを逆シリアル化します。

Question

私は、ツリーを逆シリアル化するための最小限のコードを探しています。

バイナリツリーではありません。普通のもの。 Node.childsはリストとして表されます。 empty listは葉を意味します。

私のシリアライズ方法：

override 
public String ToString() 
{ 
    String toRet = "("; 
    toRet += data; 
    foreach (Node node in childs) 
     toRet += " " + node.ToString(); 
    toRet += ")"; 
    return toRet; 
} 

次のツリーは、文字列になります：

(A (B (F) (G)) (C) (D) (E)) 

Answer 1

トリックは、一致する括弧を見つけることです。 2つの一致する括弧がサブツリーを定義します。一番外側のマッチする括弧は木全体を与える。以下は、まっすぐな解決策です。言葉の意味合いは間違いありません。

private static int match(String s) { 
     int balance = 0; 
     for(int i = 0; i < s.Length; i++) { 
      if(s[i] == '(') { 
       balance++; 
      } else if(s[i] == ')') { 
       balance--; 
      } 
      if(balance == 0) { 
       return i; 
      } 
     } 
     throw new FormatException("Parens not balanced!"); 
    } 

    public static Node Deserialize(String s) { 
     if(s.Length == 0) { 
      return null; 
     } 
     // Find the ending index of current node value 
     int end = s.IndexOf(' '); 
     if(end == -1) { 
      end = s.IndexOf(')'); 
     } 
     int i = end + 1; // skip past node value and seek for children 
     List<Node> children = new List<Node>(); 
     while(i < s.Length) { 
      if(s[i] == '(') { 
       int j = Node.match(s.Substring(i)); 
       children.Add(Node.Deserialize(s.Substring(i, j + 1))); 
       i += j; 
      } 
      i++; 
     } 
     return new Node(s.Substring(1, end - 1), children); 
    }