验证字符串中的多项式

Question

我正在尝试使多项式运算符（总和，休息，乘法和两个或多个多项式的除法）。代码必须使用Java并使用链接列表。

我在想如何计算器或如何验证多项式是否有效。我想从String构造一个多项式，但我不知道是否有另一个类可以缓解事情。

这是一项家庭作业，所以我并没有要求完整的代码，只是指出了一个好方向。

有两个类，一个用于节点（名为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 
} 

用户应该进入这样的：

10倍^ 2 - 7倍+ 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

一般来说，这是使用parsers解决 - 有许多库允许这样做，看看here。由于这不是一个复杂的解析问题，并且是一项作业，所以您可能会全部手动编写 - 因此，recursive descent parsers（也称为自顶向下解析器）是最简单的。也看看类似的StackOverflow question。

你提到的 - 按字符分割，在这种情况下工作得很好。一般来说，你想要考虑优先级。你首先评估^，然后*和/，然后+和 - 。递归下降解析器自上而下地工作，所以你首先将事情分成最后一个 - 即分开+和 - 然后分开*和/最后分开^。

在你的榜样，你开始：

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-1K-情况下

你提到了验证。即你想放弃无效的投入，如：

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

多做一些工作，你可以使用regular expressions及其Java implementation这项工作。如果你使用上面提到的自上而下的解析器，你会在每个级别上执行此操作。类似：

• 拆分由+表达成由术语分裂和 -

• 检查每个术语具有以下形式：+/-（N中，nx或NX^K）

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

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

  基本上说：

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

  • 也许^数字：（\\^[1-9] [0-9 ] *）？

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

使用正则表达式组，你甚至可以轻松地捕获的各个部分。您可以使用正则表达式测试器（例如this）来帮助您。

一个好主意是在处理之前删除空格 - 事实上，这可能是必要的。请注意，如果您需要处理负数系数和/或括号，则这会变得更复杂一些，而倾向于真正的解析器。

希望这会有所帮助。