Getting coefficients of algebraic term

Question

Given a input of an algebraic term, I am trying to get the coefficients of the variables. The only operators in the input is + - and only one variable.

Examples:

2x^2+3x+4 => [ 2, 3, 4 ]

3-x => [ -1, 3 ]

x^2+x => [ 1, 1, 0 ]

x+x^3 => [ 1, 0, 1, 0 ]

Invalid Input:

2x^2+2x^2

This is my first attempt at it:

var str = " 2x^4-1+9x^3-100x^2";

    function getCoeff(term) {

        var nterm = (term.replace(/[^0-9|-]x(?!\^)/g,"1x")).replace(/[^0-9|\+]x(?!\^)/g,"-1x"); // ==> Replace ‘-/x’ with ‘-/1x’

        for ( var i = 0; i < 10; i++ ) { // ==> Loop true the regexs to replace all ‘x^n’ to ‘1x^n’

            var re = new RegExp('[^0-9|\-]x\\^' + i); // ==> Regex for x^n
            var re2 = new RegExp('[^0-9|]x\\^' + i); // ==> Regex for -x^n

            nterm = (nterm.replace(re,"1x^" + i)).replace(re2,"-1x^" + i); }

        for ( var m = 10; m > 1; m--  ) { // ==> Get the coefficients of ax^n in descending order
            var re3 = new RegExp('\\W?\\d+(?=x\\^' + m + ')' ); 
            if ( nterm.match(re3) === null ) {
                var result = "";
            } else {
                result += ((nterm.match(re3)+', ').toString()).replace(/\+/g,""); }}

        if ( nterm.match(/\W?\d+(?=x(?!\^))/g) === null ) { // Regex for coefficient x
            var result2 = "";
        } else {
            result2 = ((nterm.match(/\W?\d+(?=x(?!\^))/g)).toString()).replace(/\+/g,"") + ',';  }

        if ( nterm.match(/[^\^]\d+(?!\d|x)/g) === null ) { // Regex for constant
            var result3 = "";
        } else {
            result3 = ((nterm.match(/[^\^]\d+(?!\d|x)/g)).toString()).replace(/\+/g,""); }

        console.log(('[' + ' ' + result + result2 + ' ' + result3 + ']' ).replace(/\s/g,"")); }

    getCoeff(str)

Problems:

• Does not work when there is a missing x term.

Eg: x^4 + x + 1 ==> Expected: [1, 0, 0, 1, 1] ==> Actual: [ 1, 1 ]

• x should return [ 1,0 ] , but it returns [ 1, ]

This is my second attempt at it.

var str = "-999x^2+x^3+x+3";
function getCoeff(string) {
if ( string.charAt(0) === 'x' ) { // If the first term is x, because of my regex it needs a space to match it
    string = ' ' + string;
}

for ( var i = 0; i < 10; i++ ) { // ==> Loop true the regexs to replace all ‘x^n’ to ‘1x^n’

    var re = new RegExp('[^0-9|\-]x\\^' + i);
    var re2 = new RegExp('[^0-9|]x\\^' + i);
    string = (string.replace(re,"+1x^" + i)).replace(re2," -1x^" + i); } 

var final = string.replace(/-/g,'+-'); // ==> Spilt(‘x’) later so to retain the -ve sign

final = (final.replace(/[^0-9|-]x(?!\^)/g,"+1x")).replace(/[^0-9|+]x(?!\^)/g,"-1x");  // ==> Replace ‘-/x’ with ‘-/1x’

final = final.replace(/[^\^](\d+(?!\d|x))/g,'+$1x^0'); // ==> Replace ‘c’ with ‘cx^0’
final = final.replace(/x(?!\^)/g, "x^1"); // ==> Replace ‘x’ with ‘x^1’
final = final.split('+'); // ==> Right now array looks something like this [ ax^(n), bx^(n-1), … yx^1,  zx^0]
final = final.filter(function(entry) { return entry.trim() !== ''; }); // Sorts array by the number behind in descending order

var reS = /^-?\d+/,
    reE = /\d+$/;
var result = final.sort(function(a, b) {
    a = reE.exec(a);
    b = reE.exec(b);
    return b - a;
}).reduce(function(res, str, i) {
    var gap = reE.exec(final[i - 1]) - reE.exec(str);
    if(gap > 0)
        while(--gap) res.push(0);
    res.push(+reS.exec(str));
    return res;
}, []); // Return the coefficients
console.log("Result:", result); 
}

getCoeff(str);

Questions:

1. Is there a way to do it without using regular expressions mostly?

2. How do I fix this problem? When no constant term is

   getCoeff(“x^3”) ==> [ 1 ] , when it should give [ 1, 0, 0 ]

3. How can I make my code more efficient?

4. How to match x^n terms but not -x^n terms using regex? This is my current one: [^0-9|\-]x\\^' + i, but it needs a space in front of it.

Reference:

How to sort array based on the numbers in string?

Answer 1

function getCoef(str) {
  str = str.replace(/\s+/g, "");                   // remove spaces (optional)
  
  var parts = str.match(/[+\-]?[^+\-]+/g);         // get the parts: see explanation bellow

  // accumulate the results
  return parts.reduce(function(res, part) {        // for each part in parts
    var coef = parseFloat(part) || +(part[0] + "1") || 1;// the coeficient is the number at the begining of each part (34x => 34), if there is no number it is assumed to be +/-1 depending on the sign (+x^2 => +1)
    var x = part.indexOf('x');                     // the index of "x" in this part (could be -1 if there isn't)
    // calculating the power of this part
    var power = x === -1 ?                         // if the index of "x" is -1 (there is no "x")
                  0:                               // then the power is 0 (Ex: -2)
                  part[x + 1] === "^" ?            // otherwise (if there is an "x"), then check if the char right after "x" is "^", if so...
                    +part.slice(x + 2) :           // then the power is the number right after it (Ex: 55x^30)
                    1;                             // otherwise it's 1 (Ex: 55x)
    res[power] = (res[power] || 0) + coef;         // if we have already encountered this power then add this coeficient to that, if not then just store it 
    return res;
  }, {});
}

/** TESTS **/
[
  "-999x^2 + x^3 + x + 3", "5x + 3 - 10x", "55x^3 + 1", "55.12x^4 + 20x^4 - 120x^4"
].forEach(function(test) {
  console.log(test, "=>", getCoef(test));
});

The output:

The result of the function getCoef will be an object in this format:

{
    "power": "coeficient",
    "other power": "other coeficient",
    ...
}

Explanation:

1. str = str.replace(/\s+/g, "");:

Removing spaces (obvious).

2. var parts = str.match(/[+\-]?[^+\-]+/g);:

Split the string into parts. The string "-5x^2-3+10x" will return ["-5x^2", "-3", "+10x"]. The regex will look for:

[+\-]?  : a "+" or "-" sign (if any)
[^+\-]+ : anything that isn't a "+" nor "-" (get everything up until the new + or - or the end is reached)
g       : to get all parts

3. var coef = parseFloat(part) || +(part[0] + "1") || 1;:

Get the coeficient of this part using:

parseFloat     : for parts that have a number before "x" like: "+55x", "-34.22x^11", "5x", ...
+(part[0] + 1) : for parts that have only a sign like: "+x", "-x^2", ... (get the sign part[0] concatinate it with "1" and then cast the result into a number using binary +)
1              : for parts that doesn't have a number nor a sign like "x^3", "x", ...

just note that parts like "0x^4" will be assumed as having a coeficient of 1 using the above (but I don't see why one will need a null coeficient anyway)!

4. var x = part.indexOf('x');:

Get the index of the character "x" in the part to distinguish between parts that have it like "3x", "x^11", ... and parts that doesn't like "+5", ...

5. var power = ...:

If there isn't an "x" in the part (x === -1) then the power of this part is 0.

Otherwise (an "x" is present), then we check if the character right after "x" (part[x + 1]) is "^", if it is then the power is whaterver number that comes after it (cut that bit of the string part.slice(x + 2) and cast it to number using unary +), if there isn't a "^" after "x", then the power is 1.

6. res[power] = (res[power] || 0) + coef;:

Add the coeficient coef that has just been calculated to the already accumulated coeficient of this power (if nothing is accumulated then use 0).

This line could be simplified like this:

if(res[power])         // if we already encountered this power in other parts before
  res[power] += coef;  // then add this coeficient to the sum of those previous coeficients
else                   // otherwise
  res[power] = coef;   // start a new sum initialized with this coeficient

this makes it possible to include the same power more than one time in the same string like: "5x + 10x + 1 + x", ...

Transform the resultant object into the desired array:

So that:

{
    "3": 7,
    "0": 19
}

will be:

[7, 0, 0, 19]

var ret = { "3": 7, "0": 19 }; // the returned object

var powers = Object.keys(ret); // get all the powers (in this case [3, 0])

var max = Math.max.apply(null, powers); // get the max power from powers array (in this case 3)

var result = [];
for(var i = max; i >= 0; i--)  // from the max power to 0
  result.push(ret[i] || 0);    // if that power has a coeficient then push it, otherwise push 0
  
console.log(result);