如何存储一个多项式？

Question

整数可以用来存储单个数字，但不能用于存储数学表达式。例如，假设我有以下表达式：6x^2 + 5x + 3，我该如何存储这个多项式呢？我可以创建自己的对象，但我不知道如何通过成员数据来表示这个多项式。我不想创建一个函数来评估传入的参数，因为我不仅需要评估它，还需要操作表达式。

除了向量，是否有更合适的解决方案？

- fdh

---

我想你可以将其视为一个字符串解析问题，但列表/向量似乎是最合适和高效的表示方式。 - Junuxx

在正式的数学中，多项式可以被视为向量空间，因此我认为这是一个很好的解决方案。 - madth3

Answer 1

一种简单但低效的方法是将其存储为系数列表。例如，问题中的多项式将如下所示：

[6, 5, 3]

如果一个术语缺失，就在它的位置上放置零。例如，多项式2x^3 - 4x + 7会被表示为：

[2, 0, -4, 7]

多项式的次数由列表长度减一确定。这种表示法有一个严重的缺点：对于稀疏多项式，列表将包含大量零。

更合理的稀疏多项式项列表表示方法是作为非零项的列表，其中每个项都是一个包含该项次数和系数的列表；多项式的次数由第一项的次数确定。例如，多项式x^100+2x^2+1将被表示为以下列表：

[[100, 1], [2, 2], [0, 1]]

作为这种表示法有多有用的一个例子，书籍 SICP 利用上述第二种多项式表示法构建了一个简单但非常有效的 符号代数系统。

- Óscar López

---

实际上我采用了另一种方法。我使用了 [3, 5, 6]，这样 for (i=0; i<n; i++) sum += array[i]*x^i。 - user

@Jinxed 这个可以很容易地扩展为多元多项式的多维版本。 - Kyle Strand

Answer 2

列表并不是唯一的选择。

你可以使用一个映射（字典）将指数映射到相应的系数。

使用映射，你的示例代码将会是：

{2: 6, 1: 5, 0: 3}

(系数，指数) 对列表是非常标准的。如果您知道您的多项式是密集的，也就是说，所有的指数位置都是小整数，范围在0到一些小的最大指数之间，您可以使用数组，就像我看到Óscar Lopez刚刚发布的那样。

- Ray Toal

Answer 3

你可以将表达式表示为表达式树。例如，参见.NET表达式树。

这允许使用比简单的多项式更复杂的表达式，并且这些表达式还可以使用多个变量。

在.NET中，你可以将表达式树作为树来操作，也可以将其作为函数进行评估。

        Expression<Func<double,double>> polynomial = x => (x * x + 2 * x - 1);
        double result = polynomial.Compile()(23.0);

- Ian Mercer

Answer 4

一个面向对象的方法会认为多项式是一组单项式，而单项式将系数和指数封装在一起。

当您有像这样的多项式时，这种方法就能发挥作用：

y(x) = x^1000 + 1

将数据结构与多项式顺序绑定的方法对于这种病态情况来说是非常浪费的。

- duffymo

Answer 5

只需将系数存储在数组或向量中。例如，在 C++ 中，如果您仅使用整数系数，则可以使用 std::vector<int>，或者对于实数，可以使用 std::vector<double>。然后，您只需按顺序推送系数，并通过变量指数号访问它们。

例如（再次在 C++ 中），要存储 5*x^3 + 9*x - 2，您可以执行以下操作：

   std::vector<int> poly;
   poly.push_back(-2); // x^0, acceesed with poly[0]
   poly.push_back(9);  // x^1, accessed with poly[1]
   poly.push_back(0);  // x^2, etc
   poly.push_back(5);  // x^3, etc

如果您有大型、稀疏的多项式，那么也许您会想使用映射而不是向量。如果您有固定长度的数据，那么您可能会使用固定长度数组而不是向量。

我在示例中使用了C++，但是这种方案可以在任何语言中使用。

- wjl

Answer 6

向量/数组是显而易见的选择。根据表达式的类型，您可以考虑某种稀疏向量类型（自定义制作，即基于字典或甚至是链表，如果您的表达式有2-3个非零系数，则为5x^100+x）。

在任一情况下，通过自定义类/接口公开将是有益的，因为您稍后可以替换实现。如果您计划编写大量表达式操作代码，您可能希望提供标准操作（+，-，*，equals）。

- Alexei Levenkov

Answer 7

你需要存储两个东西：

1. 你的多项式的次数（例如“3”）
2. 包含每个系数的列表（例如“{3, 0, 2}”）

在标准C++中，“std::vector<>”和“std::list<>”都可以实现。

- paulsm4

---

为什么你需要存储度数，当它可以从列表长度中获取？或者你也允许负幂次吗？ - paxdiablo

Answer 8

你还可以将它转化为逆波兰表示法:

6x^2 + 5x + 3 -> x 2 ^ 6 * x 5 * + 3 +

在这里，x和数字被“推送”到堆栈中，操作（^、*、+）获取堆栈中最顶端的两个值并用操作的结果替换它们。最终，您将在堆栈上获得结果值。

以这种形式计算任意复杂表达式非常容易。

这种表示法也接近于表达式的树形表示法，其中非叶子树节点表示操作和函数，而叶子节点则表示常量和变量。

树的好处在于您可以轻松评估表达式，还可以执行象征性微分等操作。两者都具有递归性质。

- Alexey Frunze

---

只是好奇：在RPN表示法中评估相等性有多容易？多项式环中的除法？我的直觉是“棘手的”，所以如果您需要这些操作，请不要使用该表示法。但是，我想如果您知道您的RPN表达式是一个多项式，您总是可以将其规范化为单独的步骤，因此提取系数就像一直以来都是以这种方式存储它一样准确。 - Steve Jessop

你在谈论什么样的相等性？抱歉，我不熟悉环。 - Alexey Frunze

假设我有一个RPN表达式“x 2 ^ 6 * x 5 * + 3 +”，还有另一个表达式“3 x 2 ^ 6 * x 5 * + +”。要确定它们实际上是相同多项式的不同表示形式需要一定的努力。如果将它们存储为系数排序的序列，则很明显如何比较多项式是否相等。环是一种抽象的数学结构（http://en.wikipedia.org/wiki/Ring_%28mathematics%29），如果您不知道什么是环，那么您不太可能意外地进行多项式除法，因此可能不需要担心 :-) - Steve Jessop

@SteveJessop：啊，那样的话，树可能会更友好一些。但即使是用树，也可能比仅仅比较左子树和右子树更复杂，因为例如，如果它是二叉树，并且你正在使用A+B+C进行计算，那么有超过2种用二叉树表示等价表达式的方法。 - Alexey Frunze