代数项的展开
Expansion of algebraic term
我正在尝试扩展一个代数项。
(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>
参考：
编辑：当问题不包括 - 和 / 运算符 时，我重写了我的原始答案。我的新答案支持 - 和 /.
由于你没有定义一个精确的语法，我做了一些假设。我支持 +、-、/、^ 运算符和隐式乘法。这些可以对数字、x 和 (...) 表达式进行运算，除了 ^ 运算符的右侧必须是数字。我允许标记之间有空格。
局限性：- 是二进制而非一元 - 运算符，因此 x-2 如果正常，-2 本身就是语法错误。 / 是有限的。您可以除以具有单个系数的值，例如 2、'x'、2x^2，但不能除以 1/(x^2+1)，这将计算为无限级数。
它首先获取字符串并将其包装在 'tokenizer' 中，这样您就可以一次查看一个标记，其中标记是一个数字，x、( ) 或运算符.
然后它调用 evaluateSum() 评估由 + 或 - 分隔的事物，其中每个事物都是由 evaluateProduct() 评估的产品。这反过来使用 evaluatePower() 来评估 ^。最后 evaluateTerm() 查找 x、数字和括号中的子表达式，这些子表达式使用 evaluateSum() 递归求值。此层次结构创建正确的运算符优先级和评估顺序。
评估的每一层returns一个'coefficients'类似于数组的对象，但可能包含宏索引。例如 [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
它可以处理+、-、/和隐式乘法。它相应地扩展括号并将它们添加到原始表达式中，同时删除括号 ed 版本。它相应地收集相似的术语。限制：它不能除以多项式，并且不支持 * 运算符。
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,'x^0').replace(/([^\d])(x\^-?\d+)/g,'').replace(/(-?\d+x\^\d+)(?=\()/g,'()').replace(/(\))(-?\d+x\^\d+)/g,'()').replace(/([^\)\/])(\()([^\*\/\(\)]+?)(\))(?![(^\/])/g,'');
str = str.replace(/(\([^\(\)]+?\))\/(\d+x\^-?\d+)/g,'/()').replace(/(\d+x\^-?\d+)\/(\d+x\^-?\d+)/g,'()/()').replace(/(\d+x\^-?\d+)\/(\(\d+x\^-?\d+\))/g,'()/');
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,'\^\{\}').replace(/\+ -/g,' - ') + '$$';
else
resultCollect = 'Error: Trying to divide by a polynomial ';
document.getElementById('result').innerHTML = '$$' + str.replace(/\^(-?\d+)/g,'\^\{\}') + '$$' + resultCollect;
MathJax.Hub.Queue(["Typeset", MathJax.Hub, document.getElementById('result')]);
} else {
resultCollect = '$$ = ' + result.replace(/\^(-?\d+)/g,'\^\{\}') + '$$';
document.getElementById('result').innerHTML = '$$' + str.replace(/\^(-?\d+)/g,'\^\{\}').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>
我的方法使用了两个助手 类:
-Term：存放一个系数和一个对象，键为变量，值为指数。它具有确定项是否为 "same"（即它们是否具有具有相同指数的相同变量，从而允许将它们相加）、相加项和相乘项的方法。
-Polynomial：这存储了一个术语数组。它有两个多项式相加、两个多项式相乘和简化多项式（消除系数为0的项并合并类似项）的方法。
它有两大辅助功能：
-findOuterParens - 给定一个字符串，此函数 returns 第一对最外面的左右括号的索引。
-parseExpressionStr - 此函数使用正则表达式将字符串拆分为三种类型的子字符串：1) 数字，2) 符号（即变量，如 'x' 或 'y'） ，或 3) 一个运算符（*、-、+、^、/）。它为前两种类型创建 Polynomial 对象，并将运算符保留为字符串。
expand 函数运行表演。它接受一个字符串和 returns 一个 Polynomial 对象，表示字符串中多项式的扩展形式。它按如下方式执行此操作：
1）它通过递归处理括号。它使用 findOuterParens 查找所有最外层带括号的子字符串。因此，例如，对于“3x*(x+4)+(2(y+1))*t”，它会找到 "x+4" 和“2(y+1)”作为带括号的子字符串。然后它将这些传递给自己以进行进一步解析。对于“2(y+1)”，它会将 "y+1" 标识为带括号的子字符串，并将其传递给自身，对于此示例的三级递归。
2) 它使用 parseExpressionStr 处理字符串的其他部分。在步骤 1 和 2 之后，它有一个包含 Polynomial 对象和运算符（存储为字符串）的数组。然后进行简化和扩展。
3) 它通过用+替换所有-'s并将-'s之后的所有多项式乘以-1，将减法子问题转换为加法子问题。
4) 它通过用 * 替换 / 并将 / 后面的 Polynomial 取反，将除法子问题转换为乘法子问题。如果 / 后面的多项式有多于一项，它会抛出一个错误。
5) 通过将 ^ 替换为一系列乘法，它将幂子问题转换为乘法子问题。
6) 它添加了隐含的*。 IE。如果两个多项式元素在数组中彼此相邻，则推断它们正在相乘，因此，例如'2*x' == '2x'。
7) 现在数组有多项式对象，交替出现 '+' 或 '*'。它首先执行所有多项式乘法，然后执行所有加法。
8) 它执行最后的简化步骤和 returns 生成的扩展多项式。
<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>
它输出：
我正在尝试扩展一个代数项。
(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>
参考：
编辑：当问题不包括 - 和 / 运算符 时，我重写了我的原始答案。我的新答案支持 - 和 /.
由于你没有定义一个精确的语法，我做了一些假设。我支持 +、-、/、^ 运算符和隐式乘法。这些可以对数字、x 和 (...) 表达式进行运算，除了 ^ 运算符的右侧必须是数字。我允许标记之间有空格。
局限性：- 是二进制而非一元 - 运算符，因此 x-2 如果正常，-2 本身就是语法错误。 / 是有限的。您可以除以具有单个系数的值，例如 2、'x'、2x^2，但不能除以 1/(x^2+1)，这将计算为无限级数。
它首先获取字符串并将其包装在 'tokenizer' 中，这样您就可以一次查看一个标记，其中标记是一个数字，x、( ) 或运算符.
然后它调用 evaluateSum() 评估由 + 或 - 分隔的事物，其中每个事物都是由 evaluateProduct() 评估的产品。这反过来使用 evaluatePower() 来评估 ^。最后 evaluateTerm() 查找 x、数字和括号中的子表达式，这些子表达式使用 evaluateSum() 递归求值。此层次结构创建正确的运算符优先级和评估顺序。
评估的每一层returns一个'coefficients'类似于数组的对象，但可能包含宏索引。例如 [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
它可以处理+、-、/和隐式乘法。它相应地扩展括号并将它们添加到原始表达式中，同时删除括号 ed 版本。它相应地收集相似的术语。限制：它不能除以多项式，并且不支持 * 运算符。
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,'x^0').replace(/([^\d])(x\^-?\d+)/g,'').replace(/(-?\d+x\^\d+)(?=\()/g,'()').replace(/(\))(-?\d+x\^\d+)/g,'()').replace(/([^\)\/])(\()([^\*\/\(\)]+?)(\))(?![(^\/])/g,'');
str = str.replace(/(\([^\(\)]+?\))\/(\d+x\^-?\d+)/g,'/()').replace(/(\d+x\^-?\d+)\/(\d+x\^-?\d+)/g,'()/()').replace(/(\d+x\^-?\d+)\/(\(\d+x\^-?\d+\))/g,'()/');
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,'\^\{\}').replace(/\+ -/g,' - ') + '$$';
else
resultCollect = 'Error: Trying to divide by a polynomial ';
document.getElementById('result').innerHTML = '$$' + str.replace(/\^(-?\d+)/g,'\^\{\}') + '$$' + resultCollect;
MathJax.Hub.Queue(["Typeset", MathJax.Hub, document.getElementById('result')]);
} else {
resultCollect = '$$ = ' + result.replace(/\^(-?\d+)/g,'\^\{\}') + '$$';
document.getElementById('result').innerHTML = '$$' + str.replace(/\^(-?\d+)/g,'\^\{\}').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>
我的方法使用了两个助手 类:
-Term：存放一个系数和一个对象，键为变量，值为指数。它具有确定项是否为 "same"（即它们是否具有具有相同指数的相同变量，从而允许将它们相加）、相加项和相乘项的方法。
-Polynomial：这存储了一个术语数组。它有两个多项式相加、两个多项式相乘和简化多项式（消除系数为0的项并合并类似项）的方法。
它有两大辅助功能：
-findOuterParens - 给定一个字符串，此函数 returns 第一对最外面的左右括号的索引。
-parseExpressionStr - 此函数使用正则表达式将字符串拆分为三种类型的子字符串：1) 数字，2) 符号（即变量，如 'x' 或 'y'） ，或 3) 一个运算符（*、-、+、^、/）。它为前两种类型创建 Polynomial 对象，并将运算符保留为字符串。
expand 函数运行表演。它接受一个字符串和 returns 一个 Polynomial 对象，表示字符串中多项式的扩展形式。它按如下方式执行此操作：
1）它通过递归处理括号。它使用 findOuterParens 查找所有最外层带括号的子字符串。因此，例如，对于“3x*(x+4)+(2(y+1))*t”，它会找到 "x+4" 和“2(y+1)”作为带括号的子字符串。然后它将这些传递给自己以进行进一步解析。对于“2(y+1)”，它会将 "y+1" 标识为带括号的子字符串，并将其传递给自身，对于此示例的三级递归。
2) 它使用 parseExpressionStr 处理字符串的其他部分。在步骤 1 和 2 之后，它有一个包含 Polynomial 对象和运算符（存储为字符串）的数组。然后进行简化和扩展。
3) 它通过用+替换所有-'s并将-'s之后的所有多项式乘以-1，将减法子问题转换为加法子问题。
4) 它通过用 * 替换 / 并将 / 后面的 Polynomial 取反，将除法子问题转换为乘法子问题。如果 / 后面的多项式有多于一项，它会抛出一个错误。
5) 通过将 ^ 替换为一系列乘法，它将幂子问题转换为乘法子问题。
6) 它添加了隐含的*。 IE。如果两个多项式元素在数组中彼此相邻，则推断它们正在相乘，因此，例如'2*x' == '2x'。
7) 现在数组有多项式对象，交替出现 '+' 或 '*'。它首先执行所有多项式乘法，然后执行所有加法。
8) 它执行最后的简化步骤和 returns 生成的扩展多项式。
<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>
它输出：