Validating polynomials from a String

Question

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.

Answer 1

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.