title: How to convert a mathematical expression tree to its reduced form?
body: <p>I'm working on some numerical analysis assignment where I'm supposed to evaluate, plot and differentiate mathematical expressions. Among other stuff. I implemented expression trees with <strong>Java</strong>.  </p>
  
  <p>So far, I can build the expression tree, display it with Latex, evaluate it, plot it and get its derivative. The is the interface that is implemented by the composite functions in the tree has the following methods: <code>
      Function[] child();<br>
      void addChild(Function chld);<br>
      double evaluate(HashMap subMap);<br>
      String toLatex();<br>
      int precedence();<br>
      Function derivative();</code><br>
  The implementations I coded so far are: <code>Constant, Variable, Add, Subtract, Multiply, Divide, Power, Sine, Cosine, Ln</code>.<br>
  Now, when I differentiate some basic function, I get it in a non-reduced form:<br>
  <code>d/dx(x^2) ===> x^2 * (1 * 2 / x + 0 * ln(x))</code><br>
  That's because the derivative is implemented in the most general way.  </p>
  
  <p>The solution I thought of is that on the construction of each node <code>f</code> in the tree, given <code>f</code>'s children, I reduce the children recursively and then do some naive reconstruction. After such reconstruction, the children are "together" reduced with respect to <code>f</code>.<br>
  For example, given the expression 0 * x, the tree should look like:</p>
  
  <pre>
    *
   / \
  0   x
  </pre>
  
  <p>On the construction of the * node, if one of its children is a zero constant, the * node becomes a zero constant. And of course throws away its children.</p>
  
  <pre>
    0
  
  
  </pre>
  
  <p>And so on for all the different cases for multiplication.
  This requires a lot of analysis on my behalf and may not cover all the cases -- keeping in mind that multiplication isn't the only function required --.  </p>
  
  <p>The task is: <strong>given an expression tree, how can I do basic reduction on it?</strong> If you could refer me to any links or papers that present a solution for this problem -- preferably in an elegant OO way -- or if you have tackled it before, your help would be <strong>really</strong> appreciated.</p>