admin 因为小时候玩过，又因为身边朋友小孩也多了，就打算花两三天时间撸一个(当时确实是打算的两三天)，结果还真小瞧了它。
最原始的算法很容易想到，4个数字的计算，随机选择2个数字进行计算，演变为3个数字的计算，最终2个数字的计算，进行循环遍历。
简单计算一下排列组合，13个数字，选出四个，而且是可重复的，也就有13*13*13*13=28561种结果(未排除其中有的数字不能组合得到24的情况)。4个符号选择3个进行运算，也有4*4*4种结果。可想而知，即使在不考虑括号更改顺序的情况下，这无疑也是一个很大的数字。
换一种思路，尽可能减少可能出现的排列组合，上面的过程，很容易就可以知道，其中包含了一些重复的表达式，比如4×3×2×1和1×2×3×4，就可以看做是等价的，应该排除。一开始没有细想这个过程，其实后面发现处理等价表达式才是最麻烦的过程，想法排列组合的处理根本就不是事。
ABCD四个数字+三个符号，可以得到一组表达式，一组表达式对应一组结果，很显然对于表达式的处理，对于数字较多的情况越有利。对此，还去了解了下逆波兰表达式，通过逆波兰表达式处理排列组合要方便很多。
逆波兰表达式
逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)在1929年就提出来了，因为其运算量在前，运算符在后，区别于常规的写法，而我们常规的写法叫中缀表达式，逆波兰表达式也叫后缀表达式。其实，我也是第一次听说，之前没有研究过。
逆波兰表达式有两个好处：1是符合计算机的出栈入栈过程；2是没有括号。举个简单的例子就是：
4 * 3 + 2 -1 => 4 3 * 2 + 1 -
4 * 3 + (2 -1) => 4 3 * 2 1 - +左侧为中缀表达式，也就是我们常见的表达式写法；右侧是后缀表达式，也就是逆波兰表达式写法。
逆波兰表达式JS实现(其中calculate为常规的+-×÷运算)：
const rpnCalculate =(expr) => {
//
const arr = ex(' ');
const elems = [];
//
let item;
//
while (item = arr.shift()) {
//
if (!isNaN(+item)) {
//
elems.push([+item])
} else {
//
const a = elems.pop()
const b = elems.pop();
//
const r = calculate(b, a, item)
//
elems.push(r)
}
}
//
return elems.pop()
}就是一个入栈、出栈的简单实现。当然，在实际处理过程中，还需要得到表达式输出，不仅仅是计算结果，需要对该过程进行改造。
优化算法
有了逆波兰表达式，通过表达式来优化上面的算法。四个数字用ABCD表示，运算符用*号表示，有效的表达式就有如下几种情况：
// 无括号
A*B*C*D => A B * C * D *
// 1个括号
(A*B)*C*D => A B * C * D *
A*(B*C)*D => A B C * * D *
A*B*(C*D) => A B * C D * *
(A*B*C)*D => A B * C * D *
A*(B*C*D) => A B C * D * *
// 2个括号
((A*B)*C)*D => A B * C * D *
(A*(B*C))*D => A B C * * D *
A*((B*C)*D) => A B C * D * *
A*(B*(C*D)) => A B C D * * *
(A*B)*(C*D) => A B * C D * *整理之后得到：
A*B*C*D => A B * C * D *
A*B*(C*D) => A B * C D * *
A*(B*C)*D => A B C * * D *
A*(B*C*D) => A B C * D * *
A*(B*(C*D)) => A B C D * * *
// 等价表达式
(A*B*C)*D => A B * C * D *
(A*(B*C))*D => A B C * * D *
(A*B)*(C*D) => A B * C D * *
(A*B)*C*D => A B * C * D *
((A*B)*C)*D => A B * C * D *
A*((B*C)*D) => A B C * D * *只有5种表达式，后面几种是等价的。
其实，我们可以直接从逆波兰表达式来思考，而不是通过常规的中缀表达式的角度来思考。有效的逆波兰表达式也就只有上述5种情况。
一共7个位置，_ _ _ _ _ _ _，前两个必须是数字，A B _ _ _ _ _，再来进行组合排列，很容易就得到有效的表达式只有以下几种情况：
AB*C*D*
AB*CD**
ABC**D*
ABC*D**
ABCD***四个数字ABCD有4*3*2*1=24种组合，4个运算符选择3个有4*4*4=64种组合，再加上5种表达式组合，一共有24*64*5=7680种结果。其实，5种表达式中，根据运算符，很多还是等价的。
由此，可以得到一个大概的处理过程：
const exps = P(['+','-','*','/'], 3);// 64
const numbers = A(value);// 24
for (let i = 0; i < numbers.length; i++) {
//
const number = numbers[i];
const [A, B, C, D] = number;
//
for (let j = 0; j < ex; j++) {
//
const exp = exps[j];
const [exp1, exp2, exp3] = exp;
// A B * C * D *
transform([A, B, exp1, C, exp2, D, exp3], 'AB*C*D*', exp)
// A B * C D * *
transform([A, B, exp1, C, D, exp2, exp3], 'AB*CD**', exp)
// A B C * * D *
transform([A, B, C, exp1, exp2, D, exp3], 'ABC**D*', exp)
// A B C * D * *
transform([A, B, C, exp1, D, exp2, exp3], 'ABC*D**', exp)
// A B C D * * *
transform([A, B, C, D, exp1, exp2, exp3], 'ABCD***', exp)
}
}其中value为输入的4个数字数组，如：[4,3,2,1]。A、P方法是进行排列组合处理，简单实现如下：
A(m,m)，输出如[[1,1,1,1],[1,1,1,2],...,[4,4,4,4]]这样的结果。
// A(m,m)
const A = (arr) => {
const len = arr.length
const res = [] //
//
const loop = (tempArr, leftArr) => {
//
if === len) {
//
res.push(tempArr);
} else {
//
le((item, index) => {
const temp = [...leftArr];
(index, 1);
//
loop([...tempArr, item], temp);
})
}
}
//
loop([], arr)
//
return res
}P(m,n)，输入如[['+','+','+'],['+','+','-'],...,['*','*','*']]这样的结果。
// P(m,n)
const P = (arr, len) => {
const res = [] //
if (!len || len > arr.length) {
return res;
}
//
const loop = (tempArr, leftArr) => {
//
if === len) {
//
res.push(tempArr);
} else {
//
le((item) => {
//
loop([...tempArr, item], [...leftArr]);
})
}
}
//
loop([], arr)
//
return res
}transform方法进行等价表达式转换，比如ABC**D*表达式在以下情况，可以转换为AB*C*D*表达式。
// ABC**D* => AB*C*D*
// ++- ABC++D- =>A+B+C-D =>AB+C+D-
// ++* ABC++D* =>(A+B+C)*D =>AB+C+D*
// ++/ ABC++D/ =>AB+C+D/
// -++ ABC-+D+ =>A+B-C+D =>AB+C-D+
// -+- ABC-+D- =>A+B-C-D =>AB+C-D-
// **+ ABC**D+ =>A*B*C+D =>AB*C*D+
// **- ABC**D- =>A*B*C-D =>AB*C*D-
// **/ ABC**D/ =>A*B*C/D =>AB*C*D/
// /*+ ABC/*D+ =>A*B/C+D =>AB*C/D+
// /*- ABC/*D- =>A*B/C-D =>AB*C/D-
// /*/ ABC/*D/ =>A*B/C/D =>A*B/C/D =>AB*C/D/转换之后，我们就可以集中进行处理。
写在后面
其实，上述过程都很好处理，其中还有一种表达式等价处理，比如b+a => a+b，(a+1)*b =>(a+b)*1，a/1 =>a*1，涉及到的情况还有点多。在此感谢“数网4”作者的整理，可见其在这方面花费的时间和功夫，真不是两三天就能够搞定的。
完成小程序的开发，10.24是来不及了，靠后吧！
在此呢，也对各位程序员兄弟姐妹道一声，节日快乐，加班无我！