java - 如何将数学表达式树转换为简化形式？

Question

我正在做一些数值分析作业，我应该在其中评估、绘制和微分数学表达式。除其他外。我用 Java 实现了表达式树。

到目前为止，我可以构建表达式树，用 Latex 显示它，计算它，绘制它并得到它的导数。树中复合函数实现的接口(interface)有以下方法:
Function[] child();<br/>
void addChild(Function chld);<br/>
double evaluate(HashMap subMap);<br/>
String toLatex();<br/>
int precedence();<br/>
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的 child ，我递归地减少 child ，然后做一些朴素的重建。经过这样的重建， children “一起”减少了 f .
例如，给定表达式 0 * x，树应该如下所示:

  * / \0   x

在构造 * 节点时，如果其子节点之一是零常量，则 * 节点变为零常量。当然会扔掉它的 child 。

  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 库。

希望这有助于...