21点益智类小游戏是利用给出的四个数字，通过四则运算与加括号这些办法，凑出结果为21的表达式。出于需要，今自己构思了一套算法以实现表达式的全组合罗列，现将具体思路及关键问题的解决方案写下与大家一起分享，不足之处还望各位多多指正。
点击这里打开程序演示页面，点击这里下载算法源文件。
相信诸位前辈看过源程序后就明白晚辈算法的主旨了，当然也有一些新手朋友可能不是很懂，尤其是里面的正则表达式部分比较纠结。那不妨让我在下面做一些较详细的介绍与讨论，来说明这套算法的思想。
在此之前，我从网上找了一下相关的算法，但多数不是因为太过复杂就是因为太过低效。有的写了上百行，模块散乱而思路模糊。有的则是在生成的一些表达式中辗转反侧，不详为之奈何，搞的结果冗余，难以复用。所以我没有借鉴网友们的经验，原创了一套思路。
那开始正题吧！生成21点的这套程序，其目的应该是根据给定的4个数字，凑出所有能满足给定结果的表达式。比如：你可以用1，2，3，4这四个数字生成所有组合结果为10的表达式，也可以用1，1，1，1这四个数字生成结果为100的表达式（无解）。因此，类的开发要本着接收四个数字和一个结果来组合表达式的这个原则，不管给定的四个数字是否重复，不管结果是否为21，也不管是否有解。
Java语言不同于JavaScript，后者是一种弱变量类型语言。一句“var a”就可以声明任意类型的一个变量“a”。正是因为弱类型，也大大增加了JavaScript语言开发的灵活性。举个例子：在JavaScript语言中，可以：
var number = "1+2";
alert(eval(number)); // 输出3
没错，JS内置的解析函数"eval"可以解析字符串，而Java语言就不存在什么“eval”来帮助解析了。所以我们第一步就是要写一个Eval类，来做数字型字符串的运算解析工作。
这里我插入一下对解析的讨论。为什么要使用解析字符串而不是直接用数字直接进行操作？举个例子：现在我们要计算1+2和1-2。或许有的朋友会选择直接写两行语句：
System.out.println(1+2);
System.out.println(1+2);
好！完全正确。下面要算的是这些：1+2+3，1+2-3，1+2*3，1+2/3，1-2+3，1-2-3 …… 看到规律没？这才只涉及到了三个数字的最简单的全组合罗列，还要一行一行的用if来写吗？这就是问题的所在。假如你开发的类，是使用int类型而不是字符串类型，作为参数并参与运算的，那么将更难用通式来解析，也更难扩展。例如要计算1+2+3，传入int类型参数后，还要判断两两之间的运算符，再逐个输出。刚才说了，这只是最简单的三个操作数，我们最终要做的是实现4个操作数而且要加括号运算。因此，这种直接用int进行运算的方案不如解析String。如果现在后者的优点还不那么明显，那么请继续看。
否定了前者，下面我们着手要做的就是开发一个Eval类(biz.wushen.points_game.util.Eval)来实现解析数字型字符串的运算。那么这个类具体怎么做？
第一步就是拆分。再庞大的一个表达式，第一步要做的，肯定还是两个操作数的运算。我们开发的第一个方法自然就是用来解析这个基本的运算(calculate方法)。这个方法非常简单，就是利用正则表达式的分组，捕获出两个操作数和运算符，然后把运算后的结果作为字符串返回。这是任何复合操作都必须走的一个方法，虽然简单但也无可替代。
第二步就要进行字符串的分析了。解析字符串终究还是靠一套运算法则：先括号，后乘除，再加减。那是否可以用一个方法来集中处理这套法则就可以了呢？不能。想一下这个问题：刚才说先括号，假如括号里面又有括号会怎样？那自然是再先括号，后乘除，再加减。答案就出来了，要想一种办法循环执行所有括号里的操作。如果括号不嵌套，则直接执行加减乘除，否则循环直到所有括号都被执行完毕。自然，这些操作会牵扯到三个类的工作：执行加减操作的方法（getAdditionOrSubtraction），执行乘除操作的方法（getMultiplicationOrDivision）和执行去括号操作的方法（getPriority）。
加减乘除方法的工作原理也很简单，就是各自向match方法传递一个可以匹配自身的正则表达式。match方法在接收的字符串中，根据各自传来的正则表达式来提取出匹配的操作数，然后用匹配到的操作数去执行一次calculate方法的计算，再用执行后的新的结果去替换原有的表达式。比如：一个字符串"1+2*3+4"，先调用乘除方法，再调用加减方法的过程是这样，第一次是"1+6+4"，第二次是"7+4"，第三次就是"11"。因为这两个方法要在去括号的时候再次被调用，所以返回的仍然是一个字符串类型。
剩下要做的就只有去括号了。这个方法内部使用了正则表达式的惰性模式（Lazy Pattern）来保证去括号的过程是由内到外，从左到右。然后用同上面类似的方法，每次去括号后，用匹配到的操作数去调用一次calculate方法，然后把新的结果替换给原有表达式，如此完成解析操作。
现在，任何复杂的表达式都可以用我们的Eval函数解析出结果来了，下面要做的就是最困难的一项任务：生成所有组合。这个游戏的核心类(biz.wushen.points_game.util.PointsGame)要做这些事：在构造方法里接收四个参与计算的数字和一个指定的结果；获得所有组合的表达式；为表达式加括号；在所有表达式中筛选出结果等于指定结果的组合。呵呵，分析完发现也不怎么困难。下面介绍如何生成四个数字的全组合。
数据结构方面，要生成一些组合最好用的还是数组。但是受Java数组的长度不可变性的制约，我们不能自由的为原始数组增加新元素，所以这里使用了List接口。四个数字的全组合，应该有这些：1+2+3+4；1+2+3-4；1+2+3*4；1+2+3/4；1+2-3+4；1+2-3-4 …… 规律出来了。如果仔细分析不难发现，用循环可以非常容易的生成这些。当然要先建立一个“根”。然后用一种遍历法来增加这些“根”。可以这样：
还是拿1，2，3，4这四个数来讲。开始，定义一个“根”是“1”，传递进来下一个操作数“2”。定义好要生成的操作符“+，-，*，/”。循环后便是：1+2，1-2，1*2，1/2。现在，让“根”变成刚循环出来的这四个。再传入下一个数字“3”，再循环，再变根，再传入“4”。如此一来，全组合就被穷举了。这里用来“变根”的就是getAllPossible方法，而用来循环操作符的就是operate方法。
然后给这些表达式执行加括号(priority)方法。这是用正则表达式最多的方法。因为正则本身就很难被看懂，所以还是只在这里简单说明一下思路吧。加括号只能用手动的穷举法了：加前两个，加中间两个，加最后两个，加前三个，加后三个，加前两个和后两个；再嵌套的加：前三个里再加前两个，前三个里再加后两个，后三个里再加前两个，后三个里再加后两个。应该就是这10种，如果哪位还有方法的话欢迎不吝赐教。
最后便是利用我们开发的Eval方法，给所有表达式进行解析计算，筛选出结果为想要数值的表达式，放到结果集里面去，把结果集(List类)返回给客户端便完成了开发。
不能忘记提一下本程序的不足。这个开发课题是2010年全国软件人才专业大赛组委会给的专科组考试样题，因为马上要参加决赛了，才在匆忙之中进行开发的。着手之前，我并没有去了解，是否应该根据给定的四个数字，进行无序的生成组合？比如给定1，2，3，4，程序并没有生成有关诸如4，3，2，1这样打乱顺序的组合。如果需要的话，还是劳您写一个Decorator类作为PointsGame类的装饰者去给客户调用吧！
点击这里打开程序演示页面，点击这里下载算法源文件。
相信诸位前辈看过源程序后就明白晚辈算法的主旨了，当然也有一些新手朋友可能不是很懂，尤其是里面的正则表达式部分比较纠结。那不妨让我在下面做一些较详细的介绍与讨论，来说明这套算法的思想。
在此之前，我从网上找了一下相关的算法，但多数不是因为太过复杂就是因为太过低效。有的写了上百行，模块散乱而思路模糊。有的则是在生成的一些表达式中辗转反侧，不详为之奈何，搞的结果冗余，难以复用。所以我没有借鉴网友们的经验，原创了一套思路。
那开始正题吧！生成21点的这套程序，其目的应该是根据给定的4个数字，凑出所有能满足给定结果的表达式。比如：你可以用1，2，3，4这四个数字生成所有组合结果为10的表达式，也可以用1，1，1，1这四个数字生成结果为100的表达式（无解）。因此，类的开发要本着接收四个数字和一个结果来组合表达式的这个原则，不管给定的四个数字是否重复，不管结果是否为21，也不管是否有解。
Java语言不同于JavaScript，后者是一种弱变量类型语言。一句“var a”就可以声明任意类型的一个变量“a”。正是因为弱类型，也大大增加了JavaScript语言开发的灵活性。举个例子：在JavaScript语言中，可以：
var number = "1+2";
alert(eval(number)); // 输出3
没错，JS内置的解析函数"eval"可以解析字符串，而Java语言就不存在什么“eval”来帮助解析了。所以我们第一步就是要写一个Eval类，来做数字型字符串的运算解析工作。
这里我插入一下对解析的讨论。为什么要使用解析字符串而不是直接用数字直接进行操作？举个例子：现在我们要计算1+2和1-2。或许有的朋友会选择直接写两行语句：
System.out.println(1+2);
System.out.println(1+2);
好！完全正确。下面要算的是这些：1+2+3，1+2-3，1+2*3，1+2/3，1-2+3，1-2-3 …… 看到规律没？这才只涉及到了三个数字的最简单的全组合罗列，还要一行一行的用if来写吗？这就是问题的所在。假如你开发的类，是使用int类型而不是字符串类型，作为参数并参与运算的，那么将更难用通式来解析，也更难扩展。例如要计算1+2+3，传入int类型参数后，还要判断两两之间的运算符，再逐个输出。刚才说了，这只是最简单的三个操作数，我们最终要做的是实现4个操作数而且要加括号运算。因此，这种直接用int进行运算的方案不如解析String。如果现在后者的优点还不那么明显，那么请继续看。
否定了前者，下面我们着手要做的就是开发一个Eval类(biz.wushen.points_game.util.Eval)来实现解析数字型字符串的运算。那么这个类具体怎么做？
第一步就是拆分。再庞大的一个表达式，第一步要做的，肯定还是两个操作数的运算。我们开发的第一个方法自然就是用来解析这个基本的运算(calculate方法)。这个方法非常简单，就是利用正则表达式的分组，捕获出两个操作数和运算符，然后把运算后的结果作为字符串返回。这是任何复合操作都必须走的一个方法，虽然简单但也无可替代。
第二步就要进行字符串的分析了。解析字符串终究还是靠一套运算法则：先括号，后乘除，再加减。那是否可以用一个方法来集中处理这套法则就可以了呢？不能。想一下这个问题：刚才说先括号，假如括号里面又有括号会怎样？那自然是再先括号，后乘除，再加减。答案就出来了，要想一种办法循环执行所有括号里的操作。如果括号不嵌套，则直接执行加减乘除，否则循环直到所有括号都被执行完毕。自然，这些操作会牵扯到三个类的工作：执行加减操作的方法（getAdditionOrSubtraction），执行乘除操作的方法（getMultiplicationOrDivision）和执行去括号操作的方法（getPriority）。
加减乘除方法的工作原理也很简单，就是各自向match方法传递一个可以匹配自身的正则表达式。match方法在接收的字符串中，根据各自传来的正则表达式来提取出匹配的操作数，然后用匹配到的操作数去执行一次calculate方法的计算，再用执行后的新的结果去替换原有的表达式。比如：一个字符串"1+2*3+4"，先调用乘除方法，再调用加减方法的过程是这样，第一次是"1+6+4"，第二次是"7+4"，第三次就是"11"。因为这两个方法要在去括号的时候再次被调用，所以返回的仍然是一个字符串类型。
剩下要做的就只有去括号了。这个方法内部使用了正则表达式的惰性模式（Lazy Pattern）来保证去括号的过程是由内到外，从左到右。然后用同上面类似的方法，每次去括号后，用匹配到的操作数去调用一次calculate方法，然后把新的结果替换给原有表达式，如此完成解析操作。
现在，任何复杂的表达式都可以用我们的Eval函数解析出结果来了，下面要做的就是最困难的一项任务：生成所有组合。这个游戏的核心类(biz.wushen.points_game.util.PointsGame)要做这些事：在构造方法里接收四个参与计算的数字和一个指定的结果；获得所有组合的表达式；为表达式加括号；在所有表达式中筛选出结果等于指定结果的组合。呵呵，分析完发现也不怎么困难。下面介绍如何生成四个数字的全组合。
数据结构方面，要生成一些组合最好用的还是数组。但是受Java数组的长度不可变性的制约，我们不能自由的为原始数组增加新元素，所以这里使用了List接口。四个数字的全组合，应该有这些：1+2+3+4；1+2+3-4；1+2+3*4；1+2+3/4；1+2-3+4；1+2-3-4 …… 规律出来了。如果仔细分析不难发现，用循环可以非常容易的生成这些。当然要先建立一个“根”。然后用一种遍历法来增加这些“根”。可以这样：
还是拿1，2，3，4这四个数来讲。开始，定义一个“根”是“1”，传递进来下一个操作数“2”。定义好要生成的操作符“+，-，*，/”。循环后便是：1+2，1-2，1*2，1/2。现在，让“根”变成刚循环出来的这四个。再传入下一个数字“3”，再循环，再变根，再传入“4”。如此一来，全组合就被穷举了。这里用来“变根”的就是getAllPossible方法，而用来循环操作符的就是operate方法。
然后给这些表达式执行加括号(priority)方法。这是用正则表达式最多的方法。因为正则本身就很难被看懂，所以还是只在这里简单说明一下思路吧。加括号只能用手动的穷举法了：加前两个，加中间两个，加最后两个，加前三个，加后三个，加前两个和后两个；再嵌套的加：前三个里再加前两个，前三个里再加后两个，后三个里再加前两个，后三个里再加后两个。应该就是这10种，如果哪位还有方法的话欢迎不吝赐教。
最后便是利用我们开发的Eval方法，给所有表达式进行解析计算，筛选出结果为想要数值的表达式，放到结果集里面去，把结果集(List类)返回给客户端便完成了开发。
不能忘记提一下本程序的不足。这个开发课题是2010年全国软件人才专业大赛组委会给的专科组考试样题，因为马上要参加决赛了，才在匆忙之中进行开发的。着手之前，我并没有去了解，是否应该根据给定的四个数字，进行无序的生成组合？比如给定1，2，3，4，程序并没有生成有关诸如4，3，2，1这样打乱顺序的组合。如果需要的话，还是劳您写一个Decorator类作为PointsGame类的装饰者去给客户调用吧！
本文链接： http://wushen.biz/original/programs/index.jsp?id=1279851632000¤t=1 （复制）
阅读次数 ( 10347 )
下载次数 ( 64 )
作者 & 技术支持： 毕飞 主题设计： mono-lab
版权所有 ICP备案号： 苏ICP备09065350号 在线 39 人
Author & Powered By： Bi Fei Theme Designed： mono-lab
Copyright © http://www.wushen.biz
Author & Powered By： Bi Fei Theme Designed： mono-lab
Copyright © http://www.wushen.biz