如何操纵数学符号？

Question

这更像是一个“教育性”的问题。 :)

虽然我最终可能会想做这样的事情。

假设我有一个方程，可以是任何类型的方程，只要它不荒谬，并且能够被擅长数学的人解决。

比如... 0 = (x-1)(x+2) 或者... y = (x^2)，y = 1/x 或正弦函数等等。基本上就是像我们在学校里做数学那样。

问题是，我该如何编写计算机程序来解决这个问题呢？我知道这是可能的，因为像Mathematica、Maple等程序已经做了几十年了！但是我找不到任何好的文档来制作甚至是简单的方程求解器。

我不指望有人告诉我“这就是你该怎么做”，因为这样的东西当然是一整个大程序，而不仅仅是一小段代码。

但是，一个通用的概述，或者一些好的文档链接呢？那就太好了！谢谢：）

尤其是需要哪种数据结构和算法。

如果找不到，我就得想出我如何求解方程，并对此进行编码。但这需要几个月的时间才能正确完成（我以前做过这种事情，将自己的思考过程形式化为代码，这很有效但也很慢）。

- user213265

---

这是一个非常棘手的问题...什么是人类“擅长数学”？不同国家和学校之间的“学校数学”差异很大...当然，如果你限制自己只做二次方程，那应该是可行的。Mathematica 处理复杂性的方式似乎部分在于将 所有东西 都转化为列表的方式，以至少以一种连贯的方式表示方程式。例如，0=(x-1)(x+2) 将被表示为 Equals(0,Product(Sum(x,-1),Sum(x,+2))) 或类似的形式... - Jonas Heidelberg

Answer 1

Wolfram Alpha是您最容易获取的基准。

您输入的是字符串，因此第一步是编写词法分析器/解析器，以将这些字符串分解为令牌并将其放入抽象语法树（AST）中。

您并没有说明要在哪种编程语言中实现此功能，但我建议您查看ANTLR。它是一个可以帮助您创建 AST 的解析器生成器。您需要为方程式构建一个语法。

一旦您拥有了 AST，您的求解器将遍历该树，并将更具体的操作与“+”、“-”等符号关联起来。您处理的运算符越多，您的求解器就越强大而全面。

但是，您将不得不处理或排除许多复杂性：

1. 并非所有方程式都有解。
2. 并非所有方程式都具有封闭形式的解。
3. 并非所有方程式都是线性的。
4. 许多有趣的问题包含许多耦合的方程式（考虑线性代数）。
5. 当封闭形式无法解决问题时，您可能需要了解许多数值方法。

我建议您从简单的算术和多项式开始，并逐步提高难度。 Stephen Wolfram并非一日之间编写出 Mathematica。

- duffymo

Answer 2

请查看关于符号计算的一些论文。

Peter Norvig的PAIP书介绍了一个非常简单的符号计算和方程求解系统，值得一读。它介绍了一个名为MacSyma的AI程序的基础知识，最终形成了Mathematica的基础。

- Jeff Foster

---

Peter Norvig是一个天才。他写的任何东西都值得一看。我很想多给点评价，但+1就是他们允许的全部了。感谢您发布它。 - duffymo

我强烈推荐PAIP。我通过将其中的示例从Common LISP转换为类似Clojure的东西来学习Clojure。我从那本书中学到的比我看过的任何其他教材都多。 - Jeff Foster

Answer 3

基本技术是在计算机程序中表示数学方程的结构。这与编译器所做的非常相似，但编译器主要将其输入转换为机器可读格式，而计算机代数系统主要产生与其输入格式相同但以某种有趣的方式转换的输出。无论哪种情况，即时输出都是抽象语法树。下一步将是应用一些模式匹配技术（类似于正则表达式的工作方式）以及一些机械变换来以某种有用的方式重写树。

如果您想看看这实际上可能如何完成，SymPy是一个Python符号数学库，它既是开源的，又专注于主要的符号操作方面。

- SingleNegationElimination

Answer 4

除了其他人提供的有用答案之外：这个链接似乎很有趣：http://en.wikipedia.org/wiki/Pattern_matching 此外，“抽象语法树”也很有趣。基本上，它是关于在语法树上进行“模式匹配”！有点像正则表达式但是针对代码。

我实际上已经编写了自己的“抽象语法树” :) 所以我已经走了一小段路到一个符号操纵器。

- user213265