Codingame Solution: Expand the polynomial

Original Problem

You are given a polynomial that is partially or fully factorized and you have to write a code that fully expands it.
For example, if you are given (x-1)*(x+2)=x²+x-2, its coefficients that are 1 1 -2 and you have to write x^2+x-2.

A partially or not factorized polynomial.

The expanded polynomial written in the standard way:
* x^1 is written x
* 1x^3 is written x^3
* 0x^2 and x^0 are not written

All the coefficients are integers (positive, null or negative).
All coefficients are in decreasing order: (x^3 then x^2 then x^1 then x^0)

Solution

This problem can be split into three parts, the input parsing, the multiplication and exponentiation as well as the correct outputting. Similar to Polynomial.js, we use a sparse representation of a polynomial using a hashmap as the foundation, with the key being the exponent and the coefficient it's value. To parse a polynomial string like 5x^3+2x-4 into {3: 5, 1: 2, 0: -4}, we write a simple function:

function parsePoly(poly) {
    return [...poly.matchAll(/([+-]?[0-9.]*)(?:x\^(\d+)|x)?/gi)].reduce((prev, x) => {

        if (x[0] !== '') {

            let c = Number(x[1] === '+' || x[1] === '-' || x[1] === '' ? x[1] + "1" : x[1]);
            let e = Number(x[2] !== undefined ? x[2] : x[0].indexOf("x") !== -1);

            prev[e] = (prev[e] || 0) + c;
        }
        return prev;
    }, {});
}

The multiplication of two polynomials is just basic algebra, where we multiply each monomial of the first polynomial by each monomial of the second polynomial by adding together the exponents as the new key and multiplying the coefficients:

function mulPoly(a, b) {
    let ret = {};
    for (let i in a) {
        i = Number(i);
        for (let j in b) {
            j = Number(j);
            ret[i + j] = (ret[i + j] || 0) + a[i] * b[j];
        }
    }
    return ret;
}

Now that we have a way to parse and multiply polynomials what is still needed is a way to convert the hashmap containing a polynomial back to a string:

function getPolyString(poly) {

    let keys = [];
    for (let i in poly) {
        keys.push(+i);
    }

    if (keys.length === 0)
        return "0";

    keys.sort((a, b) => a - b);

    let str = "", val;
    for (let k = keys.length; k--;) {

        let e = keys[k];

        val = poly[e];

        if (val === 0)
            continue;

        if (str !== "" && val > 0) {
            str+= "+";
        }

        if (val === -1 && e !== 0)
            str+= "-";
        else if (val !== 1 || e === 0)
            str+= val;

        if (e === 1)
            str+= "x";
        else if (e !== 0)
            str+= "x^" + e;
    }

    if (str === "")
        str+= val;

    return str;
}

Finally we read in the partially factorized polynomial and break it apart at the brackets. For each non-bracket string we check if it's just an exponentation of the previous polynomial, if so we add the previous polynomial n times to a terms-array. If it truly is a polynomial, we parse the string within the brackets and put it to our terms array which finally gets multiplied together:

let terms = [];
readline().match(/[^()*]+/g).forEach(poly => {

    if (poly === '^0') {
        terms[terms.length - 1] = { 0: 1 };
    } else if (poly[0] === '^') {
        for (let j = poly.slice(1) - 1; j > 0; j--) {
            terms.push(terms[terms.length - 1]);
        }
    } else {
        terms.push(parsePoly(poly));
    }
});

print(getPolyString(terms.reduce(mulPoly)));