java - 验证字符串中的多项式

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

一般来说，这可以使用 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^k 的情况

您提到了验证。 IE。你想丢弃无效的输入，例如:

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

还有一点工作，您可以使用 regular expressions和他们的 Java implementation为了这份工作。如果您使用上面提到的自上而下的解析器，您将在每个级别上执行此操作。像这样的东西:

• 通过 + 和 - 将表达式拆分为术语

• 检查每一项的形式:+/- (n, nx or nx^k)

  • 您可以使用这样的正则表达式(注意 - 我没有测试它):

    "(\\+?|-)([1-9][0-9])?(x(\^[1-9][0-9])?) ？”

  基本上说:

  • 一个可选的加号或减号:(\\+?|-),
  • 可能是一组以非零数字开头的数字:([1-9][0-9]*)?,
  • 也许 x: (x...)?,

  • 也许 ^digits: (\\^[1-9][0-9]*)?.

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

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

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

希望这对您有所帮助。