写在前面

1到13个数字(对应扑克牌点数)取4张排列组合，+、-、×、÷四个符号，计算结果为24，这就是数字游戏24点的玩法。

因为小时候玩过，又因为身边朋友小孩也多了，就打算花两三天时间撸一个(当时确实是打算的两三天)，结果还真小瞧了它。

最原始的算法很容易想到，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 = expr.split(' ');
  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 < exps.length; 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 (tempArr.length === len) {
      //
      res.push(tempArr);
    } else {
      //
      leftArr.forEach((item, index) => {
        const temp = [...leftArr];
        temp.splice(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 (tempArr.length === len) {
      //
      res.push(tempArr);
    } else {
      //
      leftArr.forEach((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，涉及到的情况还有点多。在此感谢“数网4shu.net”作者的整理，可见其在这方面花费的时间和功夫，真不是两三天就能够搞定的。

完成小程序的开发，10.24是来不及了，靠后吧！

在此呢，也对各位程序员兄弟姐妹道一声，节日快乐，加班无我！