24点破解的Java实现(一)

一、基本思想

要想计算24点游戏的结果，则必须要采用基于搜索的算法（即穷举法）对每种情况进行遍历，我们怎么样才能遍历所有的情况呢？其实我们只要总结一下，还是有规律可以找的。
输入a、b、c、d，组成a Op1 bOp2 c Op3 d的表达式，其中先算哪个子表达式未知，一共有5种计算方式，如下图所示：


此时如果要实现该程序，需要存储5棵树，为了能够使得存储量达到最小，通过分析，其实总的来说，只需要存储2棵树即可，即：

其他树都是冗余的，因为我们可以通过a、b、c、d的交换，比如((a+(b*c))+d)可以变为(((b*c)+a)+d)；
对于每棵树来说，abcd的可能性为4*3*2*1=24;op1op2 op3的可能性为4*4*4=64,因此总个数为1536，而两棵树的总个数为3072。因此只需要穷举这些方法，就可以知道结果。

TfUtils类为实现穷举24点所有可能情况的类，calculate函数用于计算，参数a、b、c、d分别为给定的4个数，而TfUtils类中的expr属性为求解的表达式。

二、代码实现

CalculatorUtils.java
[java]
package org.xiazdong;

import java.util.Stack;

public class CalculatorUtils {

/**
* 计算后缀表达式
*/
public static String calculateReversePolish(String str) {

String[] splitStr = str.split(" ");
Stack s = new Stack();
for (int i = 0; i < splitStr.length; i++) {
String ch = splitStr[i];
if (ch.matches("\\d+.\\d+")||ch.matches("\\d+")) {
s.push(ch);
} else {
if (s.size() >= 2) {
String c1 = s.pop();
String c2 = s.pop();
if (ch.equals("+")) {
if(c1.contains(".")||c2.contains(".")){
s.push(String.valueOf((Double.parseDouble(c2 + "") + Double
.parseDouble(c1 + ""))));
}
else{
s.push(String.valueOf((Integer.parseInt(c2 + "") + Integer
.parseInt(c1 + ""))));
}

} else if ("-".equals(ch)) {
if(c1.contains(".")||c2.contains(".")){
s.push(String.valueOf((Double.parseDouble(c2 + "") - Double
.parseDouble(c1 + ""))));
}
else{
s.push(String.valueOf((Integer.parseInt(c2 + "") - Integer
.parseInt(c1 + ""))));
}
} else if ("*".equals(ch)) {
if(c1.contains(".")||c2.contains(".")){
s.push(String.valueOf((Double.parseDouble(c2 + "") * Double
.parseDouble(c1 + ""))));
}
else{
s.push(String.valueOf((Integer.parseInt(c2 + "") * Integer
.parseInt(c1 + ""))));
}
} else if ("/".equals(ch)) {
s.push(String.valueOf((Double.parseDouble(c2 + "") / Double
.parseDouble(c1 + ""))));
}

} else {
System.out.println("式子有问题!");
return null;
}
}
}
return s.pop();
}
}

TfUtils.java

[java]
package org.xiazdong;

import java.io.Serializable;

public class TfUtils implements Serializable{
private int result;
private String expr = ""; //存放中缀表达式

public String getExpr() {
return expr;
}

public void setExpr(String e