Construct binary tree from s-expression in c++
<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>