title: Tree structure as string - how to match nested braces?
body: <p>I have a tree structure set up and wish to save it to / read it from a string, with a minimal amount of text (so XML serialization is out). I set up a simple (or so I thought) structure for this, but can't figure out how to read it in, so my structure will most likely have to change. Let me demonstrate with an example.</p>
  
  <p>My tree is made up of X,Y coordinates, like in the following example:</p>
  
  <pre><code>[a,b]
    |-----|
  [c,d] [e,f]
          |-----|-----|
        [g,h] [i,j] [k,l]
  </code></pre>
  
  <p>When I run my algorithm to turn this tree into a string, I get the following output:</p>
  
  <pre><code>a,b(c,d()e,f(g,h()i,j()k,l()))
  </code></pre>
  
  <p>And here it the code I'm using:</p>
  
  <pre><code>public string SerializeMe()
  {
      StringBuilder ret = new StringBuilder(this.Value.ToString())
      ret.Append("(");
      foreach (SimpleTreeNode&lt;T&gt; child in _Children)
      {
          ret.Append(child.SerializeMe());
      }
      ret.Append(")");
      return ret.ToString();
  }
  </code></pre>
  
  <p>That works great, but now I can't parse the string back into my tree structure. I can get the substring up to the first open brace and convert that to the node's value, but I'm unsure how to split the rest of the string into children. Is there any way I can easily find an opening brace, and then find it's closing brace? I've looked into some complicated regex stuff that I couldn't get working properly and quickly became completely lost.</p>
  
  <p>Does anyone have any ideas?</p>
  
  <p>EDIT:<br>
  Here's the code I have so far:</p>
  
  <pre><code>public static SimpleTreeNode&lt;SPoint&gt; 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&lt;SPoint&gt; node = new SimpleTreeNode&lt;SPoint&gt;(value);
  
          //now we have the child nodes enclosed in brackets
          string innerstring = input.Substring(input.IndexOf('('));
  
          List&lt;string&gt; children = new List&lt;string&gt;();
          // how do we split innerstring into siblings?? //
  
          foreach (string child in children)
          {
              node.Children.Add(SimpleTreeNode&lt;SPoint&gt;.ParsePointTree(child));
          }
  
          return node;
      }
  }
  </code></pre>
  
  <p>The problem I'm having, is that I will get a string that has to be split up into siblings. In the example above, <code>c,d</code> and <code>e,f</code> are siblings, represented in the form <code>(c,d()e,f(g,h()i,j()k,l()))</code>. I need to split this string into <code>c,d()</code> and <code>e,f(g,h()i,j()k,l())</code>, which is where I'm stuck.</p>