24点解法
- 2020 年 3 月 6 日
- 筆記
24点游戏是小时候很喜欢玩的游戏，给出4个数，通过加、减、乘、除完成运算，最终得到结果为24。比如数字1、3、5和9，可以通过3 * 5 + 9 * 1 得到结果24。本篇文章将通过Java程序来实现对给定数字的求解。
数字范围为1-9 运算符号支持+-*/
01
▼
从指定可能的计算表达式入手
思路
计算24点会使用4个数字，运算符号，可能包含0到2个括号，如：
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点可能使用的表达式：
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点的求值方式。
测试一下
TwentyFourSolution1 solution = new TwentyFourSolution1(); solution.findSolution("4567"); solution.findSolution("3388"); solution.findSolution("1456");
运行结果如下：
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点的多种计算方法, 也支持了分数的计算结果。但是，由于我们在指定括号的时候是没有考虑运算符号的优先级的，所以会出现诸多结果，其结果中的括号是可以简化的，如：
24 = 6/((5/4)-1) --> 24 = 6/(5/4-1) 24 = 4/(1-(5/6)) --> 24 = 4/(1-5/6) ... ...
另外，这个使用了脚本引擎ScriptEngine，计算起来相对较慢。
02
▼
从指定可能的后缀表达式入手
思路
上一个方法是从指定可能的计算表达式入手，此中方法从指定可能的后缀表达式入手：
4个数字和3个运算符号，其后缀表达式有如下几种可能：
nnonnoo nnonono nnnoono nnnonoo nnnnooo //其中n表示数值，o表示运算符号
接下来，我们要做的就是：
- 计算出数字的全排列（去重）以及运算符号的全排列（4*4*4 = 64种组合）
- 将数字和运算符的结果组合在一起，依次对上述可能的后缀表达式进行替换，得到诸如96+56+-的结果
- 然后将后缀表达式（如96+56+-)，转换成中缀表达式，并使用栈（Stack）对进行处理，考虑优先级。
- 同样如果计算结果与24小于某一个较小的误差范围，可认为是一种有效的计算结果，记入下来即可。
具体代码如下：
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"); } }
测试结果如下：
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这样的是不行的。
[10, 10, 4, 4] 结果如下： 24 = (10*10-4)/4
又如：
[11, 12, 1, 6] 结果如下： 24 = (1+11)/(6/12) 24 = (12*(1+11))/6 24 = 12*(1+11)/6 ... ...
有兴趣的读者可以思考下，如何去完成？
