CODEWITHSUNDEEP
javamathexpressioncomposite
MSiddeek
MSiddeek

Reputation: 71

How to convert a mathematical expression tree to its reduced form?

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 Java.

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: Function[] child();
void addChild(Function chld);
double evaluate(HashMap subMap);
String toLatex();
int precedence();
Function derivative();
The implementations I coded so far are: Constant, Variable, Add, Subtract, Multiply, Divide, Power, Sine, Cosine, Ln.
Now, when I differentiate some basic function, I get it in a non-reduced form:
d/dx(x^2) ===> x^2 * (1 * 2 / x + 0 * ln(x))
That's because the derivative is implemented in the most general way.

The solution I thought of is that on the construction of each node f in the tree, given f's children, I reduce the children recursively and then do some naive reconstruction. After such reconstruction, the children are "together" reduced with respect to f.
For example, given the expression 0 * x, the tree should look like:

  *
 / \
0   x

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.

  0

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 --.

The task is: given an expression tree, how can I do basic reduction on it? 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 really appreciated.

Upvotes: 3

Views: 2620

Answers (2)

Yuriy Nakonechnyy
Yuriy Nakonechnyy

Reputation: 3842

I have quite similar task: I need to simplify algebraic expressions e.g. (-1)*a + (b - a) + 2*a => b

After a bit of googling it was found that Computer algebra systems should deal with such tasks.

There is a good list of such libraries here: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

Have just tried MathEclipse/symja library - it has quite nice online evaluator (implemented using this library) which seems to do just what I need i.e. reduce expressions like 0*x => 0, a - b + (-1)*a => -b.

Also you may check other Java CAS libraries.

Hope this helps...

Upvotes: 1

raam86
raam86

Reputation: 6871

I had the exact same assignment minus the latex. I believe you did not approach the derivative evaluation correctly.

This is basically a copy paste from my assignment the key here is to use some kind of epsilon and using the other functions you already have. Further explanation regarding the derivation difference quotients can be found in wikipedia

<!-- language: lang-java -->
/**
* 
This class represents a RealFunction that is the derivative
 of the other real function.

*/

public class DerivativeFunction implements RealFunction{
      private RealFunction toDiff;
    private double _epsilon;
    private static final int TWO = 2;
    /**
    * Constructs a new DerivativeFunction object.
 Numerical computation of the derivative is performed at each point,
 epsilon is used to approximate the
 lim (f(x+t/2) - f(x-t/2))/t.

    * @param f the function whose derivative is to be approximated
    * @param epsilon the value used instead of t-->0
      in the derivative formula.
    */

    public DerivativeFunction(RealFunction f, double epsilon) {
        this.toDiff = f;
        this._epsilon = epsilon;

    }
    /**
    * returns the value of f'(x).

    * @param x the x value given.

    * @return the value f'(x) of this function i.e (f(x+epsilon/2)-f(x - epsilon/2))/epsilon.
*/

    public double valueAt(double x) {
        double reminder = this._epsilon/TWO;
        return (this.toDiff.valueAt(x + reminder) - this.toDiff.valueAt(x - reminder))/this._epsilon;
    }
}

Upvotes: 0

Related Questions