从String验证多项式 [英] Validating polynomials from a String
问题描述
我正在尝试创建一个多项式运算符（两个或多个多项式的和，休，乘和除）。代码必须是Java并使用链接列表。
我想知道计算器如何或如何验证多项式是否有效。我想从String构造一个多项式，但我不知道是否有另一个类可以缓解事情。
这是一个家庭作业，所以我是没有要求完整的代码，只是让我指向一个好的方向。
有两个类，一个用于节点（名为Monomio），另一个用于列表（命名Polinomio，是单项式的总和）。节点类有
Monomio siguienteMonomio; //下一个单项式
int exponente; //我不知道怎么用英语说这句话，也许是权力
int coeficiente; //系数
//一堆方法，求和，乘法等等。
列表类有
Monomio primerMonomio; // First Monomial
Monomio ultimoMonomio; // Last Monomial
//一堆方法，比如用幂，乘，和等来组织多项式。
现在我需要一个像这样的构造函数。
public Polinomio（String polinomio）{
在此输入代码
}
用户应输入以下内容：
10x ^ 2 - 7x + 9
所以构造函数列出三个节点：
//第一个节点
int coeficiente = 10;
int exponente = 2;
Monomio siguienteMonomio = // secondNode
//第二个节点
int coeficiente = -7;
int exponente = 1;
Monomio siguienteMonomio = // thirdNode
//第三个节点
int coeficiente = 9;
int exponente = 0;
Monomio siguienteMonomio = null;
那么，有关如何制作此产品的想法？我可以简单地跟踪特定字符（+ - ^ x）。但这可能会很长，也许还有更好的方法。
一般来说，这可以通过解析器 - 有许多库允许这样做，看看这里。由于这不是一个复杂的解析问题而且是一个家庭作业，你可能会手工编写 - 为此，递归下降解析器（也称为自顶向下解析器）是最简单的。另请参阅类似的 StackOverflow问题。
你提到的 - 按字符分割，在这种情况下会很好用。一般来说，您想要在优先权方面进行思考。首先评估^，然后是*和/，然后是+和 - 。递归下降解析器自上而下工作，所以你首先划分为最后评估的东西 - 也就是说，除以+和 - ，然后是*和/，最后是^。
在您的示例中，您从以下开始：
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
因此，对于以上各项，您：
- 查看字符串开头是否为+或 -
- 查看术语
$ b $中是否有x b- 如果不是，那么你有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字符串中用于转义\字符。
-
使用正则表达式组，您甚至可以轻松捕获各个部分。您可以使用此等正则表达式测试程序来帮助您。
一个好主意是在处理之前删除空格 - 事实上，这可能是必要的。请注意，如果你需要处理负系数和/或括号，这比上面的更复杂，倾向于真正的解析器。
希望这会有所帮助。 / p>
I'm trying to make a polynomial operator (sum, rest, multiplication and division of two or more polynomials). The code must be in Java and using linked lists.
I was wondering how do calculators or how to validate whether a polynomial is valid or not. I want to construct a polynomial from a String, but I don't know if there is another class that can ease things.
This is a homework assignment so I'm not asking for complete code, just something that points me in a good direction.
There are two classes, one for nodes (named Monomio) and one for the list (named Polinomio, is the sum of monomials). The node class has
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.
and the list class has
Monomio primerMonomio; //First Monomial
Monomio ultimoMonomio; //Last Monomial
// A bunch of methods, like organize the polynomial by the power, multiply, sum, etc.
Now I need a constructor like this.
public Polinomio(String polinomio){
enter code here
}
The user should enter something like this:
10x^2 - 7x + 9
So the constructor makes a list of three nodes:
//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;
So, any ideas of how to make this? I can simply track specific characters (+ - ^ x). But that would be long and maybe there is a better way to do.
In general, this is solved using parsers - there are many libraries that allow doing this, take a look here. As this is not a complex parsing problem and is a homework, you will probably write all by hand - for that, recursive descent parsers (also called top-down parsers) are the easiest. Also take a look at a similar StackOverflow question.
What you mentioned - splitting by characters, would work pretty well in this case. In general, you want to think in the terms of precedence. You first evaluate ^, then * and /, then + and -. Recursive descent parsers work top-down, so you first divide into things that evaluate last - that is, divide on + and -, then on * and / and finally on ^.
In your example, you start with:
10x^2 - 7x + 9
so you first get three nodes by splitting on + and -:
T1 = 10x^2
T2 = -7x
T3 = +9
This gives you the polynomial terms which are in the form +/- n*x^k:
10x^2 = +10 * x ^ 2
-7x = -7 * x ^ 1
+9 = +9 * x ^ 0
Thus, for each of the above you:
- See if it's + or - at the start of the string
- See if there's an "x" in the term
- If no, then you have x ^ 0 case, so you just have a number
- If yes, then you see if there's a ^
- If no, then it's x ^ 1 case
- If yes, then it's x ^ k case
You mentioned validation. I.e. you'd like to discard invalid inputs such as:
1 + 2x^
-- 1 + 4^
x^2^3 + x
A bit more work, you can use regular expressions and their Java implementation for this job. If you use top-down parser as mentioned above, you'd do this on each level. Something like:
- Split the expression into terms by splitting by + and -
Check that each term is of the form: +/- (n, nx or nx^k)
You can use regex such as this (note - I did not test it):
"(\\+?|-)([1-9][0-9])?(x(\^[1-9][0-9])?)?"
which basically says:
- An optional plus or a minus sign: (\\+?|-),
- Maybe a set of digits that starts with non-zero digit: ([1-9][0-9]*)?,
- Maybe x: (x...)?,
Maybe ^digits: (\\^[1-9][0-9]*)?.
If you never used them, take a look at the above docs. Note "\\" are used in Java strings to escape "\" character.
Using regex groups, you can even capture the respective parts easily. You can use regex testers such as this for this to help you out.
A good idea is removing spaces before processing - in fact, that would probably be necessary. Note that if you need to handle negative coefficients and/or parentheses, this gets a bit more complicated then the above, leaning towards the real parsers.
Hope this helps.
这篇关于从String验证多项式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
