【编程之美】24点游戏
一，概述
二十四点是一种益智游戏，它能在游戏中锻炼人们的心算，它往往要求人们将四个数字进行加减乘除（允许使用括号）求得二十四。然后将四个数字的计算公式表示出来。
二，中缀表达式求解
最直接的方法就是采用穷举法，游戏中可用的运算符只有四种，四个数字每个只能使用一次。
1）不考虑括号情况
4个数全排列：4！=24种
需要三个运算符，且运算符可以重复：4*4*4=64
总计：1536
2）考虑括号（是个难点）
自己想的加括号：四个数有五种加括号方式： (AB)CD 、 AB(CD)、 A(BC)D 、 A((BC)D) 、 (AB)(CD)、A(B(CD))
错误点：这里添加括号的时候，需要把四个数都看成相乘。需要加两个括号来列举比较直观
AB(CD) = (AB)(CD)
改正后：((AB)C)D 、 (AB)(CD) 、 (A(BC))D 、 A((BC)D) 、A(B(CD))
四个运算数五种不同加括号方式的由来。这是一个经典的Catalan数问题。
这个经典Catalan数问题在组合数学教材上都能找到。原题目是：n 个数相乘, 不改变它们的位置, 只用括号表示不同的相乘顺序，令g(n)表示这种条件下构成不同乘积的方法数，令C(n)表示第n个Catalan数。则有g(n)=C(n-1)。前几个Catalan数为：C(0)=1，C(1)=1，C(2)=2，C(3)=5，C(4)=14，C(5)=42。所以g(4)=C(3)=5。
根据Catalan数的计算公式，有g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)。
Catalan数的计算公式也同时提供了构造答案的方法。对于4个数，中间有3个位置，可以在任何一个位置一分为二，被分开的两半各自的加括号方案再拼凑起来就得到一种4个数的加括号方案：
一个数时：(A)，一种
两个数：g(2)=g(1)g(1)，所以是(A)(B)=(AB)，一种
三个数：g(3)=g(1)g(2)+g(2)g(1)=(A)(BC)+(AB)(C)，两种
四个数：g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)
=(A)[(B)(CD)+(BC)(D)]+(AB)(CD)+[(A)(BC)+(AB)(C)](D)
=A(B(CD)) + A((BC)D) + (AB)(CD) + (A(BC))D + ((AB)C)D
共有五种。于是写代码枚举这五种加括号的方式即可。这种方法只是一种能得到正确答案的方法，扩展性和效率都极差。而且生成的表达式中也有冗余括号。
