Подтвердить что ты не робот

Расширение алгебраического члена

Я пытаюсь расширить алгебраический член.

(x+1)(x+1)/x => x + 2 + x^-1
(x+1)^3 => x^3 + 3x^2 + 3x + 1
(x^2*x)(x^2) => x^5

Это моя попытка. Я пробовал много способов, чтобы решить проблемы ниже.

Проблемы:

  • Подобные термины должны быть добавлены вместе

  • (x+1)(x+1)(x+1) должен быть действительным.

  • (x+1)^2 должен быть равен (x+1)(x+1)

  • x(x+1) должен быть действительным

  • 1x^n должен быть x^n

  • Не должно быть терминов 0x^n.

  • nx^0 термины должны быть n

Фрагмент кода:

function split(input) {

    return ((((input.split(")(")).toString()).replace(/\)/g, "")).replace(/\(/g, "")).split(','); }

function strVali(str) {
    str = str.replace(/\s+/g, "");

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

    // accumulate the results
    return parts.reduce(function(res, part) {
        var coef = parseFloat(part) || +(part[0] + "1") || 1;
        var x = part.indexOf('x');
        var power = x === -1 ?
            0:
            part[x + 1] === "^" ?
                +part.slice(x + 2) :
                1;
        res[power] = (res[power] || 0) + coef;
        return res;
    }, {});
}

function getCoeff(coeff) {

    var powers = Object.keys(strVali(coeff));

    var max = Math.max.apply(null, powers);

    var result = [];
    for(var i = max; i >= 0; i--)
        result.push(strVali(coeff)[i] || 0);

    return result; }

function evaluate(expression) {
    var term1 = getCoeff(expression[0]);
    var term2 = getCoeff(expression[1]);
    var expand = "";
    for ( var j = 0; j < term1.length; j++ ) {
        for ( var i = 0; i < term2.length; i++ ) {
            expand += Number(term1[j] * term2[i]) + 'x^ ' + (Number(term1.length) - 1 - j + Number(term2.length) - 1 - i) + ' + ';
        }}
        var final = "";
    for ( var Z = 0; Z < getCoeff(expand).length; Z++) {
        final += ' ' + getCoeff(expand)[Z] + 'x^ {' + (getCoeff(expand).length - Z - 1) + '} +';
    }
    final = "$$" + ((((((final.replace(/\+[^\d]0x\^ \{[\d]+\}/g,'')).replace(/x\^ \{0}/g,'')).replace(/x\^ \{1}/g,'x')).replace(/[^\d]1x\^ /g,'+ x^')).replace(/\+ -/g,' - ')).slice(0, -1)).substring(1,(final.length)) + "$$";
    document.getElementById('result').innerHTML = final;
    MathJax.Hub.Queue(["Typeset", MathJax.Hub, document.getElementById('result')]);
}

function caller() {
    var input = document.getElementById('input').value;
    evaluate(split(input)); }
div.wrapper {
    width: 100%;
    height:100%;
    border:0px solid black;
}

input[type="text"] {
    display: block;
    margin : 0 auto;
    padding: 10px;
    font-size:20px;
}

button{
    margin:auto;
    display:block;
    background-color: white;
    color: black;
    border: 2px solid #555555;
    padding-left: 20px;
    padding-right: 20px;
    font-size: 20px;
    margin-top:10px;
}

button:hover {
    box-shadow: 0 12px 16px 0 rgba(0,0,0,0.24),0 17px 50px 0 rgba(0,0,0,0.19);
}
<script type="text/javascript" async
        src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<div class='wrapper'><input id="input" title="Enter Expression" type="text" value="(x^2+x+1)(x^2+x+1)"></div>
<div> <button onclick="caller()">Click</button></div>
<div id="result">$$x^4 + 2x^3 + 3x^2 + 2x + 1$$</div>
4b9b3361

Ответ 1

Он может обрабатывать +, -, / и неявное умножение. Он соответствующим образом расширяет круглые скобки и добавляет их в исходное выражение при удалении версии в скобках. Он собирает аналогичные термины соответственно. Ограничения: он не может делить на многочлен и не поддерживает оператор *.

function strVali(str) {
    str = str.replace(/\s+/g, "");
    var parts = str.match(/[+\-]?[^+\-]+/g);
    return parts.reduce(function(res, part) {
        var coef = parseFloat(part) || +(part[0] + "1") || 1;
        var x = part.indexOf('x');
        var power = x === -1 ?
            0:
            part[x + 1] === "^" ?
                +part.slice(x + 2) :
                1;
        res[power] = (res[power] || 0) + coef;
        return res;
    }, {});
}

function getCoeff(coeff) {
    var powers = Object.keys(strVali(coeff));
    var max = Math.max.apply(null, powers);
    var result = [];
    for(var i = max; i >= 0; i--)
        result.push(strVali(coeff)[i] || 0);
    return result; }

function format(str) {
    str = ' ' + str;
    str = str.replace(/-/g,'+-').replace(/x(?!\^)/g,'x^1').replace(/([+\/*)(])(\d+)([+\/*)(])/g,'$1$2x^0$3').replace(/([^\d])(x\^-?\d+)/g,'$11$2').replace(/(-?\d+x\^\d+)(?=\()/g,'($1)').replace(/(\))(-?\d+x\^\d+)/g,'$1($2)').replace(/([^\)\/])(\()([^\*\/\(\)]+?)(\))(?![(^\/])/g,'$1$3');
    str = str.replace(/(\([^\(\)]+?\))\/(\d+x\^-?\d+)/g,'$1/($2)').replace(/(\d+x\^-?\d+)\/(\d+x\^-?\d+)/g,'($1)/($2)').replace(/(\d+x\^-?\d+)\/(\(\d+x\^-?\d+\))/g,'($1)/$2');
    return str;
}

function expBrackets(str) {
    var repeats = str.match(/\([^\(\)]+?\)\^\d+/g);
    if ( repeats === null ) { return str; } else { var totalRepeat = '';
    for ( var t = 0; t < repeats.length; t++ ) { var repeat = repeats[t].match(/\d+$/); for ( var u = 0; u < Number(repeat); u++ ) { totalRepeat += repeats[t].replace(/\^\d+$/,''); }
        str = str.replace(/\([^\(\)]+?\)\^\d+/, totalRepeat); totalRepeat = ''; }
    return str; }
}

function multiply(str) {
    var pairs = str.match(/\([^\(\)]+?\)\([^\(\)]+?\)/g);
    if ( pairs !== null ) { while ( pairs !== null ) { var output = '';
        for (var i = 0; i < pairs.length; i++) { var pair = pairs[i].slice(1).slice(0, -1).split(')('); var firstCoeff = getCoeff(pair[0]); var secondCoeff = getCoeff(pair[1]);
            for (var j = 0; j < firstCoeff.length; j++) {
                for (var k = 0; k < secondCoeff.length; k++) { output += firstCoeff[j] * secondCoeff[k] + 'x^' + Number(firstCoeff.length - 1 - j + secondCoeff.length - 1 - k) + '+'; } }
            var regexp = new RegExp(pairs[i].replace(/\(/g,'\\(').replace(/\+/g,'\\+').replace(/\)/g,'\\)').replace(/\^/g,'\\^').replace(/\-/g,'\\-'));
            str = str.replace(regexp, '(' + (output.slice(0, -1).replace(/[^\d]0x\^\d+/g,'')) + ')');
            output = ''; }
        pairs = str.match(/\([^\(\)]+?\)\([^\(\)]+?\)/g); } }
        else { }
    str = str.replace(/\+/g,' + ');
    return str;
}

function divide(str) {
    if ( str.match(/\/(\(-?\d+x\^-?\d+.+?\))/g) === null && str.match(/\//g) !== null ) {
        while ( pairs !== null ) {
        var pairs = str.match(/\([^\(\)]+?\)\/\([^\(\)]+?\)/g);
        var output = '';
        for (var i = 0; i < pairs.length; i++) {
            var pair = pairs[i].slice(1).slice(0, -1).split(')/(');
            var firstCoeff = getCoeff(pair[0]);
            var secondCoeff = getCoeff(pair[1]);
            for (var j = 0; j < firstCoeff.length; j++) {
                for (var k = 0; k < secondCoeff.length; k++) {
                    output += firstCoeff[j] / secondCoeff[k] + 'x^' + Number(firstCoeff.length - 1 - j - secondCoeff.length + 1 + k) + '+';
                    output = output.replace(/([+-])Infinityx\^\-?\d+/g,'').replace(/([+-])NaNx\^\-?\d+/g,'');
                } }
            var regexp = new RegExp(pairs[i].replace(/\(/g,'\\(').replace(/\+/g,'\\+').replace(/\)/g,'\\)').replace(/\^/g,'\\^').replace(/\-/g,'\\-'));
            str = str.replace(regexp, '(' + (output.slice(0, -1).replace(/[^\d]0x\^-?\d+/g,'')) + ')');

            output = ''; }
        pairs = str.match(/\([^\(\)]+?\)\/\([^\(\)]+?\)/g); } }
    else { }
    return str;
}

function evaluate(str) {
    var result = format(divide(format(multiply(expBrackets(format((str)))))));
    var resultCollect = '';
    result = result.replace(/\s+/g, "").replace(/[^\d]0x\^-?\d+/g,'').replace(/\+/g,' + ');
    if ( result === '') {
        document.getElementById('result').innerHTML = '$$' + str + '$$'  + '$$ = 0 $$';
        MathJax.Hub.Queue(["Typeset", MathJax.Hub, document.getElementById('result')]);
    } else if ( result.match(/-?\d+x\^-\d+/g) === null && str.match(/\/(\(-?\d+x\^-?\d+.+?\))/g) === null) {
        for ( var i = 0; i < getCoeff(result).length; i++ ) {
        resultCollect += getCoeff(result)[i] + 'x^' + Number(getCoeff(result).length - 1 - i) + '+' ; }
        if ( resultCollect !== '')
        resultCollect = '$$ = ' + resultCollect.slice(0,-1).replace(/[^\d]0x\^-?\d+/g,'').replace(/\+/g,' + ').replace(/x\^0/g,'').replace(/x\^1(?!\d+)/g,'x').replace(/\^(-?\d+)/g,'\^\{$1\}').replace(/\+ -/g,' - ') + '$$';
        else
        resultCollect = 'Error: Trying to divide by a polynomial ';
        document.getElementById('result').innerHTML = '$$' + str.replace(/\^(-?\d+)/g,'\^\{$1\}') + '$$' + resultCollect;
        MathJax.Hub.Queue(["Typeset", MathJax.Hub, document.getElementById('result')]);
    } else {
        resultCollect = '$$ = ' + result.replace(/\^(-?\d+)/g,'\^\{$1\}') + '$$';
        document.getElementById('result').innerHTML = '$$' + str.replace(/\^(-?\d+)/g,'\^\{$1\}').replace(/\+ -/g,' - ') + '$$' + resultCollect;
        MathJax.Hub.Queue(["Typeset", MathJax.Hub, document.getElementById('result')]);
    }
}

function caller() {
    var input = document.getElementById('input').value;
    evaluate(input);
}
div.wrapper {
    width: 100%;
    height:100%;
    border:0 solid black;
}

input[type="text"] {
    display: block;
    margin : 0 auto;
    padding: 10px;
    font-size:20px;
}

button{
    margin:auto;
    display:block;
    background-color: white;
    color: black;
    border: 2px solid #555555;
    padding-left: 20px;
    padding-right: 20px;
    font-size: 20px;
    margin-top:10px;
}

button:hover {
    box-shadow: 0 12px 16px 0 rgba(0,0,0,0.24),0 17px 50px 0 rgba(0,0,0,0.19);
}
<script type="text/javascript" async
        src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input id="input" type="text" title="Enter Expression: ">
<button onclick="caller()">Click</button>
<div id="result"></div>
<div id="errors"></div>

Ответ 2

Изменить: я переписал свой первоначальный ответ, когда в вопрос не вошли операторы - и /). Мой новый ответ поддерживает - и /.

Поскольку вы не определили точную грамматику, я сделал некоторые предположения. Я поддерживаю операторы +, -, /, ^ и неявное умножение. Они могут работать с числами, x и (...) выражениями, за исключением того, что правая часть оператора ^ должна быть числом. Я допускаю пробелы между токенами.

Ограничения: - является двоичным не унарным оператором -, So x-2, если OK, -2 сам по себе является синтаксической ошибкой. / ограничен. Вы можете разделить на значение с одним коэффициентом, таким как 2, 'x', 2x^2, но не может не иметь 1/(x^2+1), который будет оцениваться бесконечной серией.

Сначала он берет строку и обертывает ее в "токенизатор", который позволяет вам смотреть на один токен за раз, где токен - это число, x, ( ) или оператор.

Затем он вызывает evaluateSum(), который вычисляет значения, разделенные символом + или -, где каждая вещь является продуктом, оцененным с помощью evaluateProduct(). Это, в свою очередь, использует evaluatePower() для оценки ^. Наконец evaluateTerm() ищет x, числа и заключенные в скобки подрежимы, которые рекурсивно оцениваются с помощью evaluateSum(). Эта иерархия создает правильный приоритет оператора и порядок оценки.

Каждый уровень оценки возвращает объект "коэффициенты", который подобен массиву, но может содержать мегагенные индексы. Например, [1,0,1] означает 1+x^2.

Он может справиться с любым количеством вложенных скобок, и многие другие случаи, такие как xx(x) - x^3, 2^3 - 8. Я добавил несколько бросков для синтаксических ошибок, например 2^x является незаконным.

function makeTokenizer(source) {
    var c, i, tokenizer;
    i = 0; // The index of the current character.
    c = source.charAt(i); // The current character.
    function consumeChar() { // Move to next c, return previous c.
        var prevC = c;
        i += 1;
        c = source.charAt(i);
        return prevC;
    }
    tokenizer = {
        next : function () {
            var str;
            while (c === ' ') { // Skip spaces
                consumeChar();
            }
            if (!c) {
                tokenizer.token = undefined; // End of source
            } else if (c >= '0' && c <= '9') { // number
                str = consumeChar(); // First digit
                while (c >= '0' && c <= '9') { // Look for more digits.
                    str += consumeChar();
                }
                tokenizer.token = Number(str);
            } else if (c === "x") {
                tokenizer.token = consumeChar();
            } else { // single-character operator
                tokenizer.token = consumeChar();
            }
        }
    };
    tokenizer.next(); // Load first token.
    return tokenizer;
}
function makeCoefficients() { // Make like an array but can have -ve indexes
    var min = 0, max = 0, c = {};
    return {
        get: function (i) {
            return c[i] || 0;
        },
        set: function (i, value) {
            c[i] = value;
            min = Math.min(i, min);
            max = Math.max(i + 1, max);
            return this; // for chaining
        },
        forEach: function (callback) {
            var i;
            for (i = min; i < max; i += 1) {
                if (this.get(i)) {
                    callback(this.get(i), i);
                }
            }
        },
        toString: function () {
            var result = "", first = true;
            this.forEach(function (val, power) {
                result += (val < 0 || first) ? "" : "+";
                first = false;
                result += (val === 1 && power !== 0) ? "" : val;
                if (power) {
                    result += "x";
                    if (power !== 1) {
                        result += "^" + power;
                    }
                }
            });
            return result;
        },
        toPowerOf: function (power) {
            if (power === 0) {
                return makeCoefficients().set(0, 1); // Anything ^0 = 1
            }
            if (power === 1) {
                return this;
            }
            if (power < 0) {
                throw "cannot raise to negative powers";
            }
            return this.multiply(this.toPowerOf(power - 1));
        },
        multiply: function (coefficients) {
            var result = makeCoefficients();
            this.forEach(function (a, i) {
                coefficients.forEach(function (b, j) {
                    result.set(i + j, result.get(i + j) + a * b);
                });
            });
            return result;
        },
        divide: function (coefficients) {
            // Division is hard, for example we cannot do infinite series like:
            // 1/(1 + x^2) = sum_(n=0 to infinity) 1/2 x^n ((-i)^n + i^n)
            // So we do a few easy cases only.
            var that = this, result = makeCoefficients(), done;
            coefficients.forEach(function (value, pow) {
                that.forEach(function (value2, pow2) {
                    result.set(pow2 - pow, value2 / value);
                });
                if (done) {
                    throw "cannot divide by " + coefficients.toString();
                }
                done = true;
            });
            return result;
        },
        add: function (coefficients, op) {
            var result = makeCoefficients();
            this.forEach(function (value, i) {
                result.set(value, i);
            });
            op = (op === "-" ? -1 : 1);
            coefficients.forEach(function (value, i) {
                result.set(i, result.get(i) + value * op);
            });
            return result;
        }
    };
}
var evaluateSum; // Called recursively
function evaluateTerm(tokenizer) {
    var result;
    if (tokenizer.token === "(") {
        tokenizer.next();
        result = evaluateSum(tokenizer);
        if (tokenizer.token !== ")") {
            throw ") missing";
        }
        tokenizer.next();
    } else if (typeof tokenizer.token === "number") {
        result = makeCoefficients().set(0, tokenizer.token);
        tokenizer.next();
    } else if (tokenizer.token === "x") {
        tokenizer.next();
        result = makeCoefficients().set(1, 1); // x^1
    } else {
        return false; // Not a 'term'
    }
    return result;
}
function evaluatePower(tokenizer) {
    var result;
    result = evaluateTerm(tokenizer);
    if (tokenizer.token === "^") {
        tokenizer.next();
        if (typeof tokenizer.token !== "number") {
            throw "number expected after ^";
        }
        result = result.toPowerOf(tokenizer.token);
        tokenizer.next();
    }
    return result;
}
function evaluateProduct(tokenizer) {
    var result, term, divOp;
    result = evaluatePower(tokenizer);
    if (!result) {
        throw "Term not found";
    }
    while (true) {
        divOp = (tokenizer.token === "/");
        if (divOp) {
            tokenizer.next();
            term = evaluatePower(tokenizer);
            result = result.divide(term);
        } else {
            term = evaluatePower(tokenizer);
            if (!term) {
                break;
            }
            result = result.multiply(term);
        }
    }
    return result;
}
function evaluateSum(tokenizer) {
    var result, op;
    result = evaluateProduct(tokenizer);
    while (tokenizer.token === "+" || tokenizer.token === "-") {
        op = tokenizer.token;
        tokenizer.next();
        result = result.add(evaluateProduct(tokenizer), op);
    }
    return result;
}

function evaluate(source) {
    var tokenizer = makeTokenizer(source),
        coefficients = evaluateSum(tokenizer);
    if (tokenizer.token) {
        throw "Unexpected token " + tokenizer.token;
    }
    console.log(source + " => " + coefficients.toString());
}

// Examples:
evaluate("(x+1)(x+1)"); // => 1+2x+x^2
evaluate("(x+1)^2"); // => 1+2x+x^2
evaluate("(x+1)(x+1)(x+1)"); // => 1+3x+3x^2+x^3
evaluate("(x+1)^3"); // => 1+3x+3x^2+x^3
evaluate("(x)(x+1)"); // => x+x^2
evaluate("(x+1)(x)"); // => x+x^2
evaluate("3x^0"); // => 3
evaluate("2^3"); // => 8
evaluate("(x+2x(x+2(x+1)x))"); // => x+6x^2+4x^3
evaluate("(x+1)(x-1)"); // => -1+x^2
evaluate("(x+1)(x+1)/x"); // x^-1+2+x
//evaluate("(x+1)/(x^2 + 1)"); //throws  cannot divide by 1+2x

Ответ 3

Мой подход использует два вспомогательных класса:

- Term: Здесь хранится коэффициент и объект, ключи которого являются переменными и значениями которых являются показатели. Он имеет методы определения того, являются ли термины "одинаковыми" (то есть, имеют ли они одни и те же переменные с одинаковыми показателями, что позволяет им добавлять), добавляя термины и умножая термины. - Polynomial: Здесь хранится массив терминов. Он имеет методы для добавления двух многочленов, умножения двух многочленов и упрощения многочленов (исключения членов с 0 коэффициентами и объединения таких членов).

Он имеет две существенные вспомогательные функции: - findOuterParens - заданная строка, эта функция возвращает индексы первой самой внешней пары левых и правых круглых скобок. - parseExpressionStr - эта функция использует регулярное выражение для разбиения строки на три типа подстрок: 1) число, 2) символ (т.е. переменную, например 'x' или 'y'), или 3) оператор (*, -, +, ^,/). Он создает объекты Polynomial для первых двух типов и оставляет операторы в виде строк.

Функция expand запускает показ. Он принимает строку и возвращает объект Polynomial, представляющий расширенную форму полинома в строке. Он делает это следующим образом: 1) Рекурсия связана с круглыми скобками. Он использует findOuterParens для поиска всех внешних партизированных подстрок. Так, например, для "3x * (x + 4) + (2 (y + 1)) * t" он найдет "x + 4" и "2 (y + 1)" в качестве партизированных подстрок. Затем он передает их для дальнейшего разбора. Для "2 (y + 1)" он будет идентифицировать "y + 1" в качестве подстроки в скобках и передать это самому себе для трех уровней рекурсии для этого примера. 2) Он обрабатывает другие части строки, используя parseExpressionStr. После шагов 1 и 2 у него есть массив, содержащий полиномиальные объекты и операторы (хранимые как строки). Затем он переходит к упрощению и расширению. 3) Он преобразует подзадачи вычитания в добавочные подзадачи, заменяя все - на + и умножая все полиномы, следующие за -1. 4) Он преобразует подзадачи деления в подзадачи умножения, заменяя/на * и инвертируя Polynomial, следуя за /. Если многочлен, следующий за /, имеет более одного члена, он выдает ошибку. 5) Он преобразует подзадачи власти в подзадачи умножения, заменяя ^ на ряд умножений. 6) Он добавляет неявные *. То есть если два полиномиальных элемента находятся рядом друг с другом в массиве, то он предполагает, что они умножаются, т.е. '2 * x' == '2x'. 7) Теперь массив имеет полиномиальные объекты, чередующиеся с "+" или "*". Сначала он выполняет все полиномиальные умножения, а затем выполняет все дополнения. 8) Он выполняет последний шаг упрощения и возвращает полученный расширенный многочлен.

<html>
<head></head>
<body></body>
<script>

function findOuterParens(str) {
	var leftIndex = str.indexOf('('), leftNum = 1, rightNum = 0;

	if (leftIndex === -1)
		return

	for (var i=leftIndex+1; i<str.length; i++) {
		if (str[i] === '(')
			leftNum++;
		else if (str[i] === ')')
			rightNum++, rightIndex=i;
		if (leftNum === rightNum)
			return {start: leftIndex, end: rightIndex}
	}

	throw Error('Parenthesis at position ' + leftIndex + ' of "' + str + '" is unpaired.');
}

function parseExpressionStr(inputString) {
	var result = [], str = inputString;
	while (str) {
		var nextPart = str.match(/([\d]+)|([\+\-\^\*\/])|([a-zA-z])/);
		if (!nextPart)
			return result;
		if (nextPart.length === 0)
			throw Error('Unable to parse expression string "' + inputString + '". Remainder "' + str + '" could not be parsed.');
		else if (nextPart[1])					// First group (digits) matched
			result.push(new Polynomial(parseFloat(nextPart[0])));
		else if (nextPart[3])					// Third group (symbol) matched
			result.push(new Polynomial(nextPart[0]));
		else									// Second group (operator) matched
			result.push(nextPart[0]);
		str = str.substring(nextPart.index+nextPart[0].length);
	}
	return result
}

function isOperator(char) {
	return char === '*' || char === '/' || char === '^' || char === '+' || char === '-';
}


function Polynomial(value) {
	this.terms = (value!==undefined) ? [new Term(value)] : [];
}

Polynomial.prototype.simplify = function() {
	for (var i=0; i<this.terms.length-1; i++) {
		if (this.terms[i].coeff === 0) {
			this.terms.splice(i--, 1);
			continue;
		}
		for (var j=i+1; j<this.terms.length; j++) {
			if (Term.same(this.terms[i], this.terms[j])) {
				this.terms[i] = Term.add(this.terms[i], this.terms[j]);
				this.terms.splice(j--, 1);
			}
		}
	}
}

Polynomial.add = function(a, b) {
	var result = new Polynomial();
	result.terms = a.terms.concat(b.terms);
	result.simplify();
	return result
}

Polynomial.multiply = function(a, b) {
	var result = new Polynomial();
	a.terms.forEach(function(aTerm) {
		b.terms.forEach(function (bTerm) {
			result.terms.push(Term.multiply(aTerm, bTerm));
		});
	});
	result.simplify();

	return result
}

Polynomial.prototype.toHtml = function() {
	var html = ''
	for (var i=0; i<this.terms.length; i++) {
		var term = this.terms[i];
		if (i !== 0)
			html += (term.coeff < 0) ? ' - ' : ' + ';
		else
			html += (term.coeff < 0) ? '-' : '';
		var coeff = Math.abs(term.coeff);
		html += (coeff === 1 && Object.keys(term.symbols).length > 0) ? '' : coeff;

		for (var symbol in term.symbols) {
			var exp = term.symbols[symbol];
			exp = (exp !== 1) ? exp : '';
			html += symbol + '<sup>' + exp + '</sup>';
		}
	}
	return html;
}

function Term(value) {
	this.symbols = {};
	if (typeof value==='string') {			// Symbol
		this.symbols[value] = 1;
		this.coeff = 1;
	} else if (typeof value==='number') {	// Number
		this.coeff = value;
	} else {
		this.coeff = 1;
	}
}

Term.same = function(a, b) {
	if (Object.keys(a.symbols).length != Object.keys(b.symbols).length)
		return false
	else
		for (var aSymbol in a.symbols)
			if (a.symbols[aSymbol] != b.symbols[aSymbol]) return false
	return true
}

Term.add = function(a, b) {
	var result = new Term();
	Object.assign(result.symbols, a.symbols);
	result.coeff = a.coeff + b.coeff;
	return result
}

Term.multiply = function(a, b) {
	var result = new Term();
	Object.assign(result.symbols, a.symbols);
	for (var symbol in b.symbols) {
		if (!(symbol in result.symbols))
			result.symbols[symbol] = 0;
		result.symbols[symbol] += b.symbols[symbol];
		if (result.symbols[symbol] === 0)
			delete result.symbols[symbol];
	}
	result.coeff = a.coeff * b.coeff;
	return result
}

function expand(str) {
	var result = [];

	var parens = findOuterParens(str);
	while (parens) {
		result = result.concat(parseExpressionStr(str.slice(0,parens.start)));
		result.push(expand(str.slice(parens.start+1, parens.end)))
		str = str.slice(parens.end+1);
		parens = findOuterParens(str);
	} 
	result = result.concat(parseExpressionStr(str));

	// Move -s to coefficients
	var minus = result.indexOf('-'), minusPoly = new Polynomial(-1);
	while (minus !== -1) {
		result[minus] = '+';
		result[minus+1] = Polynomial.multiply(minusPoly, result[minus+1]);
		minus = result.indexOf('-');
	}

	// Get rid of +s that follow another operator
	var plus = result.indexOf('+');
	while (plus !== -1) {
		if (plus===0 || isOperator(result[plus-1])) {
			result.splice(plus--, 1);
		}
		plus = result.indexOf('+', plus+1);
	}

	// Convert /s to *s
	var divide = result.indexOf('/');
	while (divide !== -1) {
		result[divide] = '*';
		var termsToInvert = result[divide+1].terms;
		if (termsToInvert.length > 1)
			throw Error('Attempt to divide by a polynomial with more than one term.');
		var termToInvert = termsToInvert[0];
		for (var symbol in termToInvert.symbols) {
			termToInvert.symbols[symbol] = -termToInvert.symbols[symbol];
		}
		termToInvert.coeff = 1/termToInvert.coeff;
		divide = result.indexOf('/');
	}

	// Convert ^s to *s
	var power = result.indexOf('^');
	while (power !== -1) {
		var exp = result[power+1];
		if (exp.terms.length > 1 || Object.keys(exp.terms[0].symbols).length != 0)
			throw Error('Attempt to use non-number as an exponent');
		exp = exp.terms[0].coeff;
		var base = result[power-1];
		var expanded = [power-1, 3, base];
		for (var i=0; i<exp-1; i++) {
			expanded.push('*');
			expanded.push(base);
		}
		result.splice.apply(result, expanded);
		power = result.indexOf('^');
	}

	// Add implicit *s
	for (var i=0; i<result.length-1; i++)
		if (!isOperator(result[i]) && !(isOperator(result[i+1])))
			result.splice(i+1, 0, '*');

	// Multiply
	var mult = result.indexOf('*');
	while (mult !== -1) {
		var product = Polynomial.multiply(result[mult-1], result[mult+1]);
		result.splice(mult-1, 3, product);
		mult = result.indexOf('*');
	}

	// Add
	var add = result.indexOf('+');
	while (add !== -1) {
		var sum = Polynomial.add(result[add-1], result[add+1]);
		result.splice(add-1, 3, sum);
		add = result.indexOf('+');
	}

	result[0].simplify();
	return result[0];
}

var problems = ['(x+1)(x+1)/x', '(x+1)^3', '(x^2*x)(x^2)', '(x+1)(x+1)(x+1)',
				'(x+1)^2', 'x(x+1)', '1x^4', '(x + (x+2))(x+5)', '3x^0', '2^3',
				'(x+2x(x+2(x+1)x))', '(x+1)(x-1)', '(x+1)(y+1)', '(x+y+t)(q+x+7)'];

var solutionHTML = '';
for (var i = 0; i<problems.length; i++) {
	solutionHTML += problems[i] + '    =>    ' + expand(problems[i]).toHtml() + '<br>';
}
document.body.innerHTML = solutionHTML;


</script>
</html>