从字符串验证多项式

Question

我试图做一个多项式运算符（两个，多个多项式的和，余数，乘法和除法）。该代码必须使用Java并使用链接列表。

我想知道如何使用计算器或如何验证多项式是否有效。我想从字符串构造一个多项式，但是我不知道是否有另一个类可以简化事情。

这是一项家庭作业，因此我并不需要完整的代码，只是为我指明了正确的方向。

有两类，一类用于节点（命名为Monomio），一类用于列表（命名为Polinomio，是单项式的总和）。节点类具有

Monomio siguienteMonomio; // The next monomial
int exponente; // I don't know how to say this in English, maybe power
int coeficiente; // The coefficient
// A bunch of methods, to sum, multiply etc.

并且列表类具有

Monomio primerMonomio; //First Monomial
Monomio ultimoMonomio; //Last Monomial
// A bunch of methods, like organize the polynomial by the power, multiply, sum, etc.

现在，我需要一个这样的构造函数。

public Polinomio(String polinomio){
    enter code here
}

用户应输入以下内容：

10x ^ 2-7x + 9

因此，构造函数列出了三个节点：

//First node
int coeficiente = 10;
int exponente = 2;
Monomio siguienteMonomio = //secondNode

//Second node
int coeficiente = -7;
int exponente = 1;
Monomio siguienteMonomio = //thirdNode

//Third node
int coeficiente = 9;
int exponente = 0;
Monomio siguienteMonomio = null;

那么，关于如何做到这一点的任何想法？我可以简单地跟踪特定字符（+-^ x）。但这会很长，也许还有更好的方法。

Answer 1

通常，可以使用解析器解决此问题-
有许多库允许执行此操作，请在此处查看。由于这不是一个复杂的解析问题，而是一项家庭作业，因此您可能需要手工编写所有内容-
为此，递归下降解析器（也称为自顶向下解析器）是最简单的。还可以看看类似的问题](http://codingdict.com/questions/93835)。

您提到的内容-
按字符拆分，在这种情况下效果很好。通常，您需要考虑优先级。首先评估^，然后评估和/，再评估+和-。递归下降解析器自上而下工作，因此您首先划分为最后求值的事物-即，在+和-上划分，然后在和/上划分，最后在^上划分。

在您的示例中，您从以下内容开始：

10x^2 - 7x + 9

因此，首先通过在+和-上分开来获得三个节点：

T1 = 10x^2
T2 = -7x
T3 = +9

这为您提供了+/- n * x ^ k形式的多项式项：

 10x^2 = +10 * x ^ 2
-7x    =  -7 * x ^ 1
+9     =  +9 * x ^ 0

因此，对于以上每种情况，您：

• 看看字符串的开头是+还是-
• 看看术语中是否有“ x”
  • 如果否，那么您有x ^ 0的情况，所以您只有一个数字
  • 如果是，那么您看是否有^
  • 如果否，则为x ^ 1种情况
  • 如果是，则为x ^ k

您提到了验证。也就是说，您要舍弃无效输入，例如：

1 + 2x^
-- 1 + 4^
x^2^3 + x

要做更多的工作，您可以为此使用正则表达式及其Java实现。如果您如上所述使用自上而下的解析器，则将在每个级别上执行此操作。就像是：

• 通过用+和-拆分将表达式拆分为项

• 检查每个术语的形式是否为：+/-（n，nx或nx ^ k）

  • 您可以使用这样的正则表达式（注意-我没有测试过）：

“（（\\ +？|-）（[1-9] [0-9] ）？（x（\ ^ [1-9] [0-9] ）？）？”

基本上说：

* 可选的加号或减号：（\\\ +？|-）， 
* 也许一组以非零数字开头的数字：（[1-9] [0-9] *）?, 
* 也许x：（x ...）?, 
* 也许^数字：（\\\ ^ [1-9] [0-9] *）？

如果您从未使用过它们，请查看上面的文档。注意Java字符串中使用“ \\”转义“ \”字符。

使用正则表达式组，您甚至可以轻松捕获各个部分。您可以使用像这样的正则表达式测试器来帮助您。

一个好主意是在处理之前删除空间-实际上，这可能是必要的。请注意，如果您需要处理负系数和/或括号，则这将比上面的复杂一些，倾向于使用真正的解析器。

希望这可以帮助。