建立计算机代数系统

Question

我正在用PHP创建一个CAS（计算机代数系统），但是我现在陷入困境。我正在使用此网站。

现在我写了一个分词器。它将转换这样的方程式： 通用标签

对此： 通用标签

（其中group是另一组令牌）。如何简化这个方程式？是的，我知道您可以做什么：添加X-var，但是它们在子组中。我可以用来处理这些令牌的最佳方法是什么？

Answer 1

下一步真正有用的是构造一个解析树：

您可以通过编写一个infix解析器来实现其中之一。您可以通过编写简单的递归下降解析器或引入强大的武器和使用解析器生成器。无论哪种情况，都有助于构造形式语法： 通用标签

请注意，此语法不处理2x语法，但应易于添加。

请注意在语法规则中巧妙地使用了递归。 primary仅捕获变量，数字和带括号的表达式，并在遇到运算符时停止。 multiplicative解析一个或多个由primary符号分隔的*表达式，但是在遇到+或-符号时会停止。 additive解析由multiplicative和+分隔的一个或多个-表达式，但是在遇到)时会停止。因此，递归方案决定了运算符的优先级。

通过以下方式实现预测解析器并不是很困难。就像我在下面所做的那样（在ideone.com上查看完整示例）： 通用标签

好的，现在您有了这棵可爱的解析树，甚至还有一张漂亮的照片。怎么办？您的目标（目前）可能是简单地组合术语以获得以下形式的结果： 通用标签

我会把那部分留给你。拥有一个分析树应该使事情变得更加简单。

Answer 2

PHP擅长于字符串，数字和数组。但这对于实现符号公式操纵来说是一种糟糕的语言，因为它没有用于处理“符号表达式”的本机机制，对此您确实需要树。是的，您可以实施所有这些机制。更难的是进行代数运算。如果您想构建一些复杂的东西，则需要进行大量的工作。理想情况下，您希望机器可以帮助您直接轻松地编写转换。

例如，您将如何实现任意代数规则？关联性和可交换性？术语“远距离匹配”？例如 通用标签

您可以查看如何使用我们的一个简单的CAS实现一个href=“ http://www.semanticdesigns.com/Products/DMS/ProgramTransformation.html” rel=“ nofollow”> DMS程序转换系统。 DMS具有内置的可交换性和关联性等坚硬的数学构造，并且您可以显式编写代数规则以对符号公式进行运算。

Answer 3

这本书 计算机代数和符号计算：Joel S. Cohen的数学方法 描述了一种自动简化代数表达式的算法。

此算法在符号计算机代数库中用于C＃。与您的示例一起使用以下C＃程序： 通用标签

在控制台上显示以下内容： 通用标签