我们可以考虑多项式。
对于在X中的两个多项式，我们可以得到'+'-reducer和'*'-reducer。
现在，在树中，我们可以考虑一个“不可约”多项式，而不是将标量或x作为节点考虑。
然后，如果节点运算符是*，我们应用'*'-reducer，否则应用'+'-reducer，这两者都将两个不可约多项式转换为新的不可约多项式。
例如，其中P_a，P_b是两个多项式。
P_a = {
x0: 1
x1: 2
x3: 4
}
并且 P_b = {x1: 3}
我们得到的求和结果为：P_a + P_b = {x0: 1, x1: 5, x3: 4}
(因此树 ['+', P_a, P_b] 的简化形式为 {x: 0, x1: 5, x3: 4})
我们得到的乘积结果为：P_a * P_b = {x1: 3, x2: 6, x3: 12}
最终，我们得到了一个在 X 中不可约的多项式。
我们可以将该多项式写成二叉树的形式（也就是简化后的树）：
对于每个单项式（在 X^i 中），写出其关联的二叉树（该二叉树仅包含 * 运算符）
例如：5x^3 => ['*', ['*', ['*', x, x], x], 5]
然后相加
例如：1 + x + x^2 => ['+', 1, ['*', x, 1], ['*', x, x]
同样的想法（实现
'+'-reducer/
'*'-reducer）可以应用于具有
X、
Y或
Z多项式的表达式，或者任何其他表达式（因此在您的情况下，
x，
y）。
下面是一个实现示例（您可以取消注释并使用nodejs通过测试）
const add = (a, b) => {
const out = Object.assign({}, a)
Object.entries(b).forEach(([monomialKey, scalar]) => {
out[monomialKey] = (out[monomialKey] || 0) + scalar
if (out[monomialKey] === 0) {
delete out[monomialKey]
}
})
return out
}
const parseKey = s => s.match(/[a-z]+\d+/g).reduce((o, kv) => {
const [,varname,deg] = kv.match(/([a-z]+)(\d+)/)
o[varname] = parseInt(deg)
return o
}, {})
const writeKey = o => Object.entries(o).reduce((s, [varname, deg]) => s + varname+deg, '')
const timesMonomialKey = (iA, iB) => {
const a = parseKey(iA)
const b = parseKey(iB)
const out = {}
;[a,b].forEach(x => Object.entries(x).forEach(([varname, deg]) => {
if (deg === 0) return
out[varname] = (out[varname] || 0) + deg
}))
if (Object.keys(out).length === 0) return writeKey({ x: 0 })
return writeKey(out)
}
const times = (a, b) => {
const out = {}
Object.entries(a).forEach(([monimalKeyA, sA]) => {
Object.entries(b).forEach(([monimalKeyB, sB]) => {
const key = timesMonomialKey(monimalKeyA, monimalKeyB)
out[key] = (out[key] || 0) + sA * sB
if (out[key] === 0) {
delete out[key]
}
})
})
return out
}
const reduceTree = t => {
if (!Array.isArray(t)) {
return typeof(t) === 'string'
? { [writeKey({ [t]: 1 })]: 1 }
: { [writeKey({ x: 0 })]: t }
}
const [op, leftTree, rightTree] = t
const left = reduceTree(leftTree)
const right = reduceTree(rightTree)
return op === '+' ? add(left, right) : times(left, right)
}
const writePolynomial = o => {
const writeMonomial = ([key, s]) => {
const a = parseKey(key)
const factors = Object.entries(a).flatMap(([varname, deg]) => {
return Array.from({length: deg}).fill(varname)
}).concat(s !== 1 ? s : [])
return factors.reduce((t, next) => ['*', t, next])
}
if (Object.keys(o).length === 0) return 0
return Object.entries(o).map(writeMonomial).reduce((t, next) => ['+', t, next])
}
console.log(writePolynomial(reduceTree(['+', ['+', 'x', 'y'], 'x'])))
+和*，但正确的方法可能是允许回溯，并比较表达式的可优先性，如果找到两个或更多简化形式。您将希望能够枚举从初始表达式到简化形式的可能路径，允许备份并沿着不适用任何内容的不同路径向下走（这是回溯部分）。 - Robert Dodier