从多项式函数字符串动态分配数组

Question

我有一个多项式加法问题，就像下面这个：

(1*x+2*x^3-1*x+7)+(1+1*x^2-1*x+1*x^4)

我需要找出如何提取系数和指数的数字，并将它们输入到动态分配的二维数组中（从这里我可以对它们进行排序和相加，然后输出答案）。

我很困惑如何做到这一点，因为多项式的次数可以是任意顺序，并包括任意数量的项。在提取所有数字后，我可以动态分配它们。我需要帮助的部分是：

• 提取所有数字
• 区分它们以查看它是系数还是指数
• 允许这个过程发生在任意数量的项上

如果有人能回答这个问题或至少指点我正确的方向，我将不胜感激。

- proCrow

---

你要找的是 std::vector，它可以是一个有两个成员的类或者一个 std::pair。 - NathanOliver

Answer 1

你的问题看起来像是解析和计算。

步骤1：你需要假设一个中缀表达式来解析字符串，以便可以提取系数。

步骤2：将这些系数推入向量/双端队列等中进行多项式计算。

以下是一些好的示例：

在C++中评估字符串算术表达式

什么是在C++中评估数学表达式的最佳方法？

- Martein Txz

Answer 2

要从字符串中提取系数，您需要创建一个解析器。您可以使用特殊库，例如boost.spirit，您也可以使用构建解析器的特殊工具，例如Flex，或者手动使用正则表达式来创建自己的解析器。

为了存储系数，您可以使用std::vector<int>，使用索引作为x的幂，因此对于1*x+2*x^3-1*x+7，您的向量将具有以下数据：

{ 7, -1, 0, 2 } // 7*x^0 + -1*x^1 + 0*x^2 + 2*x^3 

那么您无需对它们进行排序即可添加系数。要存储所有多项式，您可以相应地使用 std::vector<std::vector<int>>。

- Slava