24点解法

孟君

发布于 2020-03-06 09:19:56

6170

发布于 2020-03-06 09:19:56

24点游戏是小时候很喜欢玩的游戏，给出4个数，通过加、减、乘、除完成运算，最终得到结果为24。比如数字1、3、5和9，可以通过3 * 5 + 9 * 1 得到结果24。本篇文章将通过Java程序来实现对给定数字的求解。

数字范围为1-9
运算符号支持+-*/

▼

从指定可能的计算表达式入手

思路

计算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)

这样，两个方法的处理都有了。

▼

小结

针对上述程序，我们可以完成一个简单的交互，用于锻炼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
... ...

有兴趣的读者可以思考下，如何去完成？

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-02-21，如有侵权请联系 cloudcommunity@tencent.com 删除

java

jdk

stack

本文分享自孟君的编程札记微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

java

jdk

stack

登录后参与评论

0 条评论

热度

24点解法

24点解法

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐