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表示运算符号
接下来,我们要做的就是:
步骤
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表示运算符号
接下来,我们要做的就是:
具体代码如下:
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
... ...
有兴趣的读者可以思考下,如何去完成?