title: Binary expression tree C++
body: <p>I have a little problem. I'm trying to add a mathematical expression to a binary tree but I can't understand the algorithm. Here it is:</p>
  
  <pre><code>If the current token is a '(':
   Add a new node as the left child of the current node, and 
   descend to the left child.
  If the current token is in the list ['+','-','/','*']:
   Set the root value of the current node to the operator represented by the current token.
   Add a new node as the right child of the current node and descend to the right child.
  If the current token is a number:
   Set the root value of the current node to the number and return to the parent.   
  If the current token is a ')':
    go to the parent of the current node.
  </code></pre>
  
  <p>and the code that I made so far:</p>
  
  <pre><code>template&lt;class T&gt;
  void Tree&lt;T&gt;::Expr(Node&lt;T&gt; *node, char expr[], int &amp;i)
  {
      i++;
      T x = expr[i];
      if(x == '(')
          {
              node = node-&gt;Left;
  
              node = new Node&lt;T&gt;;
              node-&gt;Left = NULL;
              node-&gt;Right = NULL;
              Expr(node, expr, i);
          }
      if(x == '+' || x == '-' || x == '*' || x == '/')
          {
              node-&gt;data = x;
              node = node-&gt;Right;
              node = new Node&lt;T&gt;;
              node-&gt;Left = NULL;
              node-&gt;Right = NULL;
              Expr(node, expr, i);
          }
      if(x &gt;= '0' &amp;&amp; x &lt;= '9')
          {
              node-&gt;data = x;
              return;
          }
      if(x == ')') return;
  }
  </code></pre>
  
  <p>I know it's a big mess but I can't realize how to implement it. Can somebody explain the algorithm to me or give me a source with C++ code or better explained algorithm?</p>
  
  <p><strong>P.S. Here is the new code that I wrote but it works only for expressions like: (5+2)</strong></p>
  
  <pre><code>template&lt;class T&gt;
  void Tree&lt;T&gt;::Expr(Node&lt;T&gt; *&amp;node, char expr[], int &amp;i)
  {
      i++;
      if(i &gt;= strlen(expr)) return;
      char x = expr[i];
      node = new Node&lt;T&gt;;
      node-&gt;Left = NULL;
      node-&gt;Right = NULL;
      if(x == '(')
          {
              Expr(node-&gt;Left, expr, i);
              i++;
              x = expr[i];
          }
      if(x &gt;= '0' &amp;&amp; x &lt;= '9')
          {
              node-&gt;data = x;
              return;
          }
      if(x == '+' || x == '-' || x == '*' || x == '/')
          {
              node-&gt;data = x;
              Expr(node-&gt;Right, expr, i);
          }
      if(x == ')') return;
  }
  </code></pre>