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

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方式--或者如果您以前处理过它，那么您的帮助将非常感激。

- MSiddeek

---

实际上，你需要实现很多规则，并忘记覆盖所有情况。你需要的是来自那些曾经做过这个的人（不是我）的经验，他们可以告诉你一个明智的面向对象设计（例如策略、访问者、组合等）。但在我看来，你最好使用一种函数式语言。 - Alexandre C.

好的，感谢您的快速回复。这就是我正在寻找的“之前做过这个的人”。我只能使用Java，除此之外什么都不行。 :) - MSiddeek

你选择（或被分配）了一个相当困难的问题。这个网站http://issc.uj.ac.za/symbolic/symbolic.html可能会有所帮助。 - High Performance Mark

Answer 1

我有一个相似的任务：我需要简化代数表达式，例如(-1)*a + (b - a) + 2*a => b

经过一番搜索，发现计算机代数系统应该能够处理这样的任务。

这里有一个很好的这类库的列表：http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

我刚刚尝试了MathEclipse/symja库 - 它有一个相当不错的在线求值器（使用此库实现），似乎正是我所需要的，即简化像0*x => 0，a - b + (-1)*a => -b这样的表达式。

您还可以查看其他Java CAS库。

希望这可以帮到您...

- Yuriy Nakonechnyy

---

有点晚了，但非常感谢！Symja正是我在寻找的。 - MSiddeek

Answer 2

我有完全相同的作业，只是没有涉及到 LaTeX。我相信你在求导的评估上走错了方向。

这基本上是从我的作业中复制粘贴的，关键在于使用某种 epsilon 并利用你已经有的其他函数。 关于求导的进一步解释 差商可以在维基百科上找到。

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

- raam86

---

谢谢，但那不是我想要的。演绎只是一个例子，不是任务的重点。我的意思是，在构建任何表达式时，您可能会遇到一些奇形怪状的函数或冗余。比如用户输入[x * x]，你必须将其简化。或者当你试图相乘两个函数[2 * x] * [3 * x^2]时，你不能让它保持这样。任务的主要目的是绘制一些输入函数。 - MSiddeek