math - 如何从字符串方程中解析多项式

Question

我想知道，给定字符串 n*3/7+9-5，我可以从中得到多项式，作为数组或字符串，例如 [4, 3/7]。我应该怎么做？

另外，有一个库允许我将它转换成这样的字符串:subtract(add(divide(multiply(n,3),7),9),5)，如果这有帮助。

此外，我正在使用 Javascript 和 Objective - C(服务器和客户端)，如果有帮助的话。

我曾尝试将每个操作表示为一个对象，并将它们存储在一个数组中，然后按操作顺序对数组进行排序，评估每个操作，然后使用它，但我真的迷路了，无法弄清楚如何让它发挥作用。

如果您需要更多信息，请告诉我。

我的问题是，将 n*3/7+9-5 转换为它的多项式([4, 3/7]) 有什么好的算法？

谢谢，阿里

Answer 1

有两个步骤:解析和微分/简化。

有多种方法可以进行解析。您可以使用现有的东西，或者我所做的是一个简单的递归下降解析器。无论哪种方式，结果都是解析树数据结构。

为了区分/简化，可以编写相当简单的递归函数。

(如果您只需要答案，我是 Maxima 的忠实粉丝。)

否则你可以写这些东西:

简化器:这将一个解析树作为输入，并通过应用如下规则生成一个新的解析树:
- 任何时间为 0 的都是零
- 任何乘以 1 的东西都是
- 任何东西加 0 就是那个东西
- 任何数值加上/减去任何其他数值只是一个新数值
- 任何数值乘以/除以任何其他数值只是一个新数值

替换:这需要一个解析树 A，一个像“n”这样的标记名称，以及另一个树 B，遍历树 A，无论“n”出现在哪里，都将其替换为 B 的副本。结果是将 A 的所有“n”替换为 B 的副本。

因此，例如，要获得表达式的常量部分，您可以将“n”替换为零并简化结果。所有带有“n”的项都将被删除，留下常量。

要用“n”来区分，可以使用基本规则:
- d(n) = 1
- d(任何不包含 n 的东西) = 0
- d(a +/- b) = d(a) +/- d(b)
- d(a * b) = bd(a) + ad(b)
- d(a/b) = (bd(a) - ad(b))/(b^2)

因此，对于最多 n^2 个项，整体策略可能是:
- 用 x 代替 n^2，用 x 微分，得到的常数 q 是 n^2 的因数。
- 对原式减去qn^2，化简。这是新表达式减去 n^2 项。
- 现在用 n 对它进行微分，得到的常量 p 就是它的因数。
- 减去 pn 并简化，以产生最终的加法常数 r。

您可以通过编写一个简单的计算器来解释解析树来查看它是否正确。只需将 n 的一个奇怪值代入原始公式，看看会得到什么。如果你解释 (qn^2 + pn + r)，你应该得到同样的结果。

害怕吗？它比看起来容易，而且是一项很棒的技能。

编辑:这是千里马:

历史:Maxima 起源于 Macsyma(MAC 符号操作)，它始于 70 年代初的麻省理工学院人工智能实验室，它基于 MacLisp 并从 Joel Moses 的符号集成程序开始。它可以做代数、微分和积分、矩阵和张量数学、微分方程等等。