如何將數學表達式樹轉換爲簡化形式？

Question

我正在做一些數值分析任務，我應該評估，繪製和區分數學表達式。其他的東西。我使用Java實現了表達式樹。

到目前爲止，我可以構建表達式樹，用Latex顯示它，評估它，繪製它並得到它的導數。是樹中複合函數實現的接口有以下幾種方法： Function[] child();
void addChild(Function chld);
double evaluate(HashMap subMap);
String toLatex();
int precedence();
Function derivative();
目前我編碼的實現是：Constant, Variable, Add, Subtract, Multiply, Divide, Power, Sine, Cosine, Ln。
現在，當我區分一些基本功能時，我得到它在一個非簡化的形式：
d/dx(x^2) ===> x^2 * (1 * 2/x + 0 * ln(x))
這是因爲衍生工具以最一般的方式實施。

我想到的解決方案是，在樹中每個節點f的構建中，給出f的孩子，我遞歸地減少孩子，然後做一些天真的重建。經過這樣的重建之後，孩子們在「一起」減少了f。
例如，給定的表達式0 * x，則樹應該看起來像：

 
    * 
/\ 
0 x 

在*節點的結構，如果它的一個子是零不變，*節點成爲零恆定。當然會拋棄它的孩子。

 
    0 

等乘法的所有不同情況。 這需要我進行大量分析，可能無法涵蓋所有​​情況 - 請記住，乘法不是唯一需要的功能 - 。

任務是：給出了一個表達式樹，我該如何做基本的還原呢？如果您可以將任何鏈接或論文提交給此問題的解決方案 - 最好採用優雅的OO方式 - 或者如果您之前已經解決了這個問題，那麼您的幫助應該是真的讚賞。

Answer 1

發現我有相當類似的任務：我需要例如簡化代數表達式(-1)*a + (b - a) + 2*a => b

經過一番谷歌搜索發現Computer algebra systems應該處理這樣的任務。

有這樣庫的好名單這裏：http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

剛纔想MathEclipse/symja庫 - 它擁有相當不錯的在線評估（使用這個庫來實現），這似乎做正是我需要的就是減少像0*x => 0表達式，a - b + (-1)*a => -b。

你也可以檢查其他Java CAS庫。

希望這會有所幫助...

Answer 2

我有完全相同的任務減去膠乳。我相信你沒有正確處理派生評估。

這基本上是從我的任務中複製粘貼這裏的關鍵是使用某種類型的epsilon並使用其他已有的功能。 關於推導 difference quotients進一步解釋可在維基百科

<!-- 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; 
    } 
}