简化代数表达式

Question

可能重复：
简化数学表达式的策略

我有一个数学表达式解析器，它构建一棵树来表示表达式。例如，如果我输入2+y+3+y，其内部表示形式将是：

现在，我们作为人类可以立即看出2+y+3+y = 2y + 5。我认为对于计算机来说棘手的部分是，如果我站在左边的+上，我不知道在另一个分支中右侧还有一个加法 - 在评估时这并不重要，但在简化时我不知道如何很好地完成这个任务。

这是类之间的关系图： 我尝试过谷歌搜索，但没有找到任何能帮助我的东西。只要有一些一般性的路标、网址或其他任何东西都会受到赞赏。

注意，对于示例，我仅包括了加法。解析器支持像：1+2*(3^4-4/5*(1+2))这样的表达式。

- ErikTJ

---

你能让“+”拥有超过2个子元素吗？我相信像Mathematica这样的符号数学语言会将你的示例存储为一个列表“[2，y，3，y]”，其头部为“Plus”，然后使用一些规则自动简化。 - JohnPS

你们的语法树真的是这样构建的吗？我敢打赌不是这样的。 - Novak

@Novak 你可能是对的。我猜左分支只包含常数2。 - ErikTJ

你看过这个网页吗？https://dev59.com/_2sz5IYBdhLWcg3w9syr? - ie.

我猜我也不确定你为什么要这样做：是为了编译器优化以使编译后的代码运行更快吗？还是作为符号包的一部分，旨在向人类显示信息？还是其他原因？ - Novak

Answer 1

由于您的类结构可以表达的表达式集合非常有限，因此您可以简单地计算每个变量出现的次数并总和所有常量。

var nodes = tree.Flatten();

var variables = nodes
    .OfType<Variable>()
    .GroupBy(x => x.Name)
    .Select(g => new Multiplication(
        new Variable(g.Key), new Constant(g.Count())));

var constants = nodes
    .OfType<Constant>()
    .Sum(x => x.Value);

var result = new Addition(
    variables.Aggregate((x, y) => new Addition(x, y)), 
    new Constant(constants));

- dtb

---

我包含了有限数量的运算符和函数。我有 + - * / log pow exp ( )。 - ErikTJ

但是你只问了关于加法的问题。对于任意代数表达式的通用解决方案，你可能会在计算机科学课本中找到；在我看来，在这里要求太多了。 - dtb