title: Construct binary tree from s-expression in c++
body: <pre><code>empty tree ::= ()
  tree ::= empty tree | (w tree tree)
  ex:
  ()
  empty tree
  
  (99(5()())(35(-5()())()))
  
       99
      /  \
     5   35
        /
       -5
  
  class Node
  {
  public:
      int weight; // weight can be negative!
      Node *left, *right;
      Node():weight(0),left(NULL),right(NULL){}
      Node(int d):weight(d),left(NULL),right(NULL){}
  };
  </code></pre>
  
  <p>Construct a binary tree by given condition</p>
  
  <p>I get problem with construct it, my program will crush and I have no idea about why it happened, the following is my code and I print out some information for debug, take (99(5()())(35(-5()())())) as a test case, it will print out 99(5( and crush, I think maybe problem is at which I deal with ) where I return node which is NULL, but I can’t find problem with it. By the way, this tree is expected to handle HUNDREDS of nodes in each tree, and Each of the test cases contains up to TEN-THOUSAND trees, will I run out of time with this program or what should I need to do?Thank for your time</p>
  
  <pre><code>Node* MyBinaryTreeOps::constructTree(Node *root, std::string treeStr)const
  {
      int idex = 1;//always look at the treeStr[1]
      Node *cur=NULL;//use to pass in recursive call
      if(treeStr[idex]!='('&amp;&amp;treeStr[idex]!=')'){//meet number create new node
         stringstream ss;
         while(treeStr[idex]!='('){
               ss&lt;&lt;treeStr[idex];
               if(treeStr.size()&gt;1){//if size &gt; 1 then remove the treeStr[1],to let treeStr[1] become next char in treeStr
                  treeStr.erase(1,1);
               }
          }
          int num=0;
          ss&gt;&gt;num;
          std::cout&lt;&lt;num&lt;&lt;std::endl;//print out just for debug
          std::cout&lt;&lt;treeStr[idex]&lt;&lt;std::endl;//print out just for debug
          root = new Node(num);
       }
  
      if(treeStr[idex]==')'){//meet ')' return subtree constructed
        if(treeStr.size()&gt;1){
           treeStr.erase(1,1);
        }
         return root;
      }
      if(treeStr[idex]=='('){//meet first '(' then construct left subtree
         if(treeStr.size()&gt;1){
            treeStr.erase(1,1);
         }
  
         root-&gt;left = constructTree(cur,treeStr);
  
      }
  
      if(treeStr[idex]=='('){ //meet second '(' then construct right subtree
         if(treeStr.size()&gt;1){
            treeStr.erase(1,1);
         }
         root-&gt;right = constructTree(cur,treeStr);
  
      }
      if(treeStr[idex]==')'){ //meet ')' return subtree constructed
         if(treeStr.size()&gt;1){
            treeStr.erase(1,1);
         }
         return root;
      }
  }
  </code></pre>