24点游戏是小时候很喜欢玩的游戏，给出4个数，通过加、减、乘、除完成运算，最终得到结果为24。比如数字1、3、5和9，可以通过3 * 5 9 * 1 得到结果24。本篇文章将通过Java程序来实现对给定数字的求解。
代码语言：javascript复制数字范围为1-9
运算符号支持 -*/01
▼
从指定可能的计算表达式入手
思路
计算24点会使用4个数字，运算符号，可能包含0到2个括号，如：
代码语言：javascript复制24 = 8/(9-7)*6
24 = 8/((9-7)/6)
24 = (8*6)/(9-7)
24 = 6/((9-7)/8)
24 = (6*8)/(9-7)我们先列举计算24点可能使用的表达式：
代码语言：javascript复制nononon
(non)onon
no(non)on
nono(non)
(nonon)on
no(nonon)
(non)o(non)
((non)on)on
(no(non))on
no(no(non))
no((non)on)
//其中n表示数值，o表示运算符号接下来，我们要做的就是：
- 计算出数字的全排列（去重）以及运算符号的全排列（4*4*4 = 64种组合）
- 将数字和运算符的结果组合在一起，依次对上述可能的计算表达式进行替换，得到诸如8/((9-7)/6)的结果
- 然后借助JDK中的脚本引擎ScriptEngine计算每个表达式的结果（如8/((9-7)/6)的结果），
- 如果计算结果与24的差值小于某一个较小的误差范围，可认为是一种有效的计算结果，记入下来即可
步骤
- 指定可能的表达式
private static final String[] AVAILABLE_PATTERN = {"nononon","(non)onon","no(non)on"
,"nono(non)","(nonon)on","no(nonon)","(non)o(non)"
,"((non)on)on","(no(non))on","no(no(non))","no((non)on)"};- 给出数字的全排列（去重）
public static Set<String> permute(String value) {
int len = value.length();
Set<String> uniqueResult = new HashSet<>();
permuteRecusion(value.toCharArray(), 0, len - 1,uniqueResult);
return uniqueResult;
}
private static void permuteRecusion(char[] charValues, int begin, int end, Set<String> uniqueResult) {
if (begin == end) {
uniqueResult.add(new String(charValues));
return;
}
for (int i = begin; i <= end; i ) {
swap(charValues, begin, i);
permuteRecusion(charValues, begin 1, end,uniqueResult);
swap(charValues, begin, i);
}
}
private static void swap(char[] charValues, int i, int j) {
char temp = charValues[i];
charValues[i] = charValues[j];
charValues[j] = temp;
}- 运算符的组合
public static List<String> availableOperators() {
int n = 4;
int total = 4 * 4 * 4;
List<String> availableResult = new ArrayList<>();
for (int i = 0, npow = n * n; i < total; i ) {
/**
* 000
* 001
* ...
* 333
*/
availableResult.add(String.format("%d%d%d", i / npow, (i % npow) / n, i % n));
}
return availableResult;
}- 表达式内容替换
for (String pattern : AVAILABLE_PATTERN) {
for (String digitals : Permute.permute(value)) {
for (String operator : Permute.availableOperators()) {
String replacePatternResult = this.replacePattern(pattern, digitals, operator);
... ...
/** 支持的操作，包括加減乘除 */
private static final String SUPPORTED_OPERATORS = " -*/";
private String replacePattern(String pattern, String digitals, String operator) {
StringBuilder sb = new StringBuilder();
char[] patternChars = pattern.toCharArray();
int i = 0;
int j = 0;
for(char c : patternChars ) {
if('n' == c) {
sb.append(digitals.charAt(i ));
}else if('o' == c) {
sb.append(SUPPORTED_OPERATORS.charAt( operator.charAt(j ) - '0'));
}else {
sb.append(c);
}
}
return sb.toString();
}- 使用脚本引擎进行计算,并对结果进行比较
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("nashorn");
String replacePatternResult = this.replacePattern(pattern, digitals, operator);
//计算表达式 返回Object
Object result;
try {
result = engine.eval(replacePatternResult);
/**检查是否有结果*/
if(Math.abs(24 -Double.valueOf(result.toString())) < 0.001F) {
solutions.add("24 = " replacePatternResult);
}
} catch (ScriptException e) {
}
通过以上几个步骤，就完成了一个24点的求值方式。
测试一下
代码语言：javascript复制 TwentyFourSolution1 solution = new TwentyFourSolution1();
solution.findSolution("4567");
solution.findSolution("3388");
solution.findSolution("1456");运行结果如下：
代码语言：javascript复制Warning: Nashorn engine is planned to be removed from a future JDK release
4567 结果如下：
24 = (7 5-6)*4
24 = 4*((5-6) 7)
24 = 4*(7-(6-5))
24 = 4*(5 (7-6))
24 = (7 5)*(6-4)
24 = 4*(5 7-6)
24 = (7-(6-5))*4
24 = 4*(7-6 5)
24 = 4*(7 5-6)
24 = ((7 5)-6)*4
24 = (5-6 7)*4
24 = (5 7)*(6-4)
24 = (7-6 5)*4
24 = ((5 7)-6)*4
24 = (5 7-6)*4
24 = 4*((7 5)-6)
24 = 4*(7 (5-6))
24 = ((7-6) 5)*4
24 = 4*(5-(6-7))
24 = (5-(6-7))*4
24 = (6-4)*(5 7)
24 = ((5-6) 7)*4
24 = 4*(5-6 7)
24 = (6-4)*(7 5)
24 = 4*((5 7)-6)
24 = 4*((7-6) 5)
24 = (7 (5-6))*4
24 = (5 (7-6))*4
Warning: Nashorn engine is planned to be removed from a future JDK release
3388 结果如下：
24 = 8/(3-8/3)
24 = 8/(3-(8/3))
Warning: Nashorn engine is planned to be removed from a future JDK release
1456 结果如下：
24 = 6/((5/4)-1)
24 = 4/(1-5/6)
24 = 6/(5/4-1)
24 = 4/(1-(5/6))通过上述方式，我们可以看出，可能计算出24点的多种计算方法, 也支持了分数的计算结果。但是，由于我们在指定括号的时候是没有考虑运算符号的优先级的，所以会出现诸多结果，其结果中的括号是可以简化的，如：
代码语言：javascript复制24 = 6/((5/4)-1) --> 24 = 6/(5/4-1)
24 = 4/(1-(5/6)) --> 24 = 4/(1-5/6)
... ...另外，这个使用了脚本引擎ScriptEngine，计算起来相对较慢。
02
▼
从指定可能的后缀表达式入手
思路
上一个方法是从指定可能的计算表达式入手，此中方法从指定可能的后缀表达式入手：
4个数字和3个运算符号，其后缀表达式有如下几种可能：
代码语言：javascript复制nnonnoo
nnonono
nnnoono
nnnonoo
nnnnooo
//其中n表示数值，o表示运算符号接下来，我们要做的就是：
- 计算出数字的全排列（去重）以及运算符号的全排列（4*4*4 = 64种组合）
- 将数字和运算符的结果组合在一起，依次对上述可能的后缀表达式进行替换，得到诸如96 56 -的结果
- 然后将后缀表达式（如96 56 -)，转换成中缀表达式，并使用栈（Stack）对进行处理，考虑优先级。
- 同样如果计算结果与24小于某一个较小的误差范围，可认为是一种有效的计算结果，记入下来即可。
具体代码如下：
代码语言：javascript复制import java.util.EmptyStackException;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
public class TwentyFourSolution {
/**
* 符合4个数子和三个操作符号的表达格式，n代表数字，o表示操作符号
*/
private static final String[] AVAILABLE_POSTFIX_PATTERNS = { "nnonnoo", "nnonono", "nnnoono", "nnnonoo",
"nnnnooo" };
/** 支持的操作，包括加減乘除 */
private static final String SUPPORTED_OPERATORS = " -*/";
public void findSolution(String value) {
Set<String> solutions = new HashSet<>();
for (String pattern : AVAILABLE_POSTFIX_PATTERNS) {
for (String digitals : Permute.permute(value)) {
for (String operator : Permute.availableOperators()) {
String replacePatternResult = this.replacePattern(pattern, digitals, operator);
// System.out.println(replacePatternResult);
/** 检查是否有结果 */
if (this.evaluate(replacePatternResult.toCharArray())) {
solutions.add("24 = " postfixToInfix(replacePatternResult));
}
}
}
}
if(solutions.isEmpty()) {
System.out.println("未能找到结果" value);
}else {
System.out.println(value " 结果如下：");
for(String s :solutions) {
System.out.println(s);
}
}
}
private String postfixToInfix(String postfix) {
Stack<Expression> expr = new Stack<>();
for (char c : postfix.toCharArray()) {
int idx = SUPPORTED_OPERATORS.indexOf(c);
if (idx != -1) {
Expression r = expr.pop();
Expression l = expr.pop();
int opPrec = idx / 2;
if (l.prec < opPrec)
l.ex = '(' l.ex ')';
if (r.prec < opPrec)
r.ex = '(' r.ex ')';
expr.push(new Expression(l.ex, r.ex, "" c));
} else {
expr.push(new Expression("" c));
}
}
return expr.peek().ex;
}
private String replacePattern(String pattern, String digitals, String operator) {
StringBuilder sb = new StringBuilder();
char[] patternChars = pattern.toCharArray();
int i = 0;
int j = 0;
for (char c : patternChars) {
if ('n' == c) {
sb.append(digitals.charAt(i ));
} else {
sb.append(SUPPORTED_OPERATORS.charAt(operator.charAt(j ) - '0'));
}
}
return sb.toString();
}
private boolean evaluate(char[] line) {
Stack<Float> s = new Stack<>();
try {
for (char c : line) {
if ('0' <= c && c <= '9')
s.push((float) c - '0');
else
s.push(applyOperator(s.pop(), s.pop(), c));
}
} catch (EmptyStackException e) {
}
return (Math.abs(24 - s.peek()) < 0.001F);
}
private float applyOperator(float a, float b, char c) {
switch (c) {
case ' ':
return a b;
case '-':
return b - a;
case '*':
return a * b;
case '/':
return b / a;
default:
return Float.NaN;
}
}
class Expression {
String op, ex;
int prec = 3;
Expression(String e) {
ex = e;
}
Expression(String e1, String e2, String o) {
ex = String.format("%s %s %s", e1, o, e2);
op = o;
prec = SUPPORTED_OPERATORS.indexOf(o) / 2;
}
}
public static void main(String[] args) {
TwentyFourSolution solution = new TwentyFourSolution();
solution.findSolution("4567");
solution.findSolution("3388");
solution.findSolution("1456");
}
}
测试结果如下：
代码语言：javascript复制4567 结果如下：
24 = (7 5) * (6 - 4)
24 = (5 7) * (6 - 4)
24 = (7 - 6 - 5) * 4
24 = 4 * (7 - 6 - 5)
24 = (6 - 4) * (5 7)
24 = (7 - 6 5) * 4
24 = 4 * (5 7 - 6)
24 = 4 * (7 - 6 5)
24 = (5 7 - 6) * 4
24 = (5 - 6 7) * 4
24 = 4 * (5 - 6 7)
24 = (7 5 - 6) * 4
24 = 4 * (7 5 - 6)
24 = 4 * (5 - 6 - 7)
24 = (5 - 6 - 7) * 4
24 = (6 - 4) * (7 5)
3388 结果如下：
24 = 8 / (3 - 8 / 3)
1456 结果如下：
24 = 6 / (5 / 4 - 1)
24 = 4 / (1 - 5 / 6)
这样，两个方法的处理都有了。
03
▼
小结
针对上述程序，我们可以完成一个简单的交互，用于锻炼24点的计算。如：
使用如下数字计算24点: [3, 9, 6, 3]
(输入 'q' 退出, 输入's'获取一种解决方法 )
> s
(3 9) / (3 / 6)
使用如下数字计算24点: [1, 1, 2, 7]
(输入 'q' 退出, 输入's'获取一种解决方法 )
> s
(1 2) * (1 7)
使用如下数字计算24点: [5, 7, 4, 6]
(输入 'q' 退出, 输入's'获取一种解决方法 )
> s
(7 5) * (6 - 4)
使用如下数字计算24点: [5, 5, 8, 2]
(输入 'q' 退出, 输入's'获取一种解决方法 )
> s
(5 / 5 2) * 8
使用如下数字计算24点: [9, 6, 3, 5]
(输入 'q' 退出, 输入's'获取一种解决方法 )
> s
3 - 9 5 * 6
使用如下数字计算24点: [3, 8, 6, 3]
(输入 'q' 退出, 输入's'获取一种解决方法 )
> q
谢谢上述示例中，只支持10以内的数字的24点计算，如果想计算10，10，4，4这样的是不行的。
代码语言：javascript复制[10, 10, 4, 4] 结果如下：
24 = (10*10-4)/4
又如：
代码语言：javascript复制[11, 12, 1, 6] 结果如下：
24 = (1 11)/(6/12)
24 = (12*(1 11))/6
24 = 12*(1 11)/6
... ... 有兴趣的读者可以思考下，如何去完成？
