Deserialize einen Baum, als String dargestellt

Question

Ich bin auf der Suche nach dem kleinsten Stück Code zum Deserialisieren eines Baumes.

Kein binärer Baum. Ein regelmäßiger. Node.childs wird als Liste dargestellt. Ein empty list bedeutet ein Blatt.

Meine Serialisierungsmethode:

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

Der folgende Baum im String führt:

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

Answer 1

Der Trick passenden Pars findet. Zwei übereinstimmende Parens definieren einen Teilbaum. Die äußersten passenden Parens geben den ganzen Baum. Es folgt eine einfache Lösung, die im wahrsten Sinne des Wortes nicht minimal ist.

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); 
    }