title: How to build a parse tree of a mathematical expression?
body: <p>I'm learning how to write tokenizers, parsers and as an exercise I'm writing a calculator in JavaScript.</p>
  
  <p>I'm using a prase tree approach (I hope I got this term right) to build my calculator. I'm building a tree of tokens based on operator precedence.</p>
  
  <p>For example, given an expression <code>a*b+c*(d*(g-f))</code> the correct tree would be:</p>
  
  <pre><code>         +
          / \
         *   \
        / \   \
       a   b   \
                *
               / \
              c   *
                 / \
                d   -
                   / \
                  g   f
  </code></pre>
  
  <p>Once I've the tree, I can just traverse it down and apply the operations at each root node on the left and right nodes recursively to find the value of the expression.</p>
  
  <p>However, the biggest problem is actually building this tree. I just can't figure out how to do it correctly. I can't just split on operators <code>+</code>, <code>-</code>, <code>/</code> and <code>*</code> and create the tree from the left and right parts because of precedence.</p>
  
  <p>What I've done so far is tokenize the expression. So given <code>a*b+c*(d*(g-f))</code>, I end up with an array of tokens:</p>
  
  <pre><code>[a, Operator*, b, Operator+, c, Operator*, OpenParen, d, Operator*, OpenParen, g, Operator-, f, CloseParen, CloseParen]
  </code></pre>
  
  <p>However I can't figure out the next step about how to go from this array of tokens to a tree that I can traverse and figure out the value. Can anyone help me with ideas about how to do that?</p>