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

1. package org.xiazdong;
3. import java.util.Stack;
5. public class CalculatorUtils {
7. /**
8. * 計算後綴表達式
9. */
10. public static String calculateReversePolish(String str) {
12. String[] splitStr = str.split(" ");
13. Stack<String> s = new Stack<String>();
14. for (int i = 0; i < splitStr.length; i++) {
15. String ch = splitStr[i];
16. if (ch.matches("\\d+.\\d+")||ch.matches("\\d+")) {
17. s.push(ch);
18. } else {
19. if (s.size() >= 2) {
20. String c1 = s.pop();
21. String c2 = s.pop();
22. if (ch.equals("+")) {
23. if(c1.contains(".")||c2.contains(".")){
24. s.push(String.valueOf((Double.parseDouble(c2 + "") + Double
25. .parseDouble(c1 + ""))));
26. }
27. else{
28. s.push(String.valueOf((Integer.parseInt(c2 + "") + Integer
29. .parseInt(c1 + ""))));
30. }
32. } else if ("-".equals(ch)) {
33. if(c1.contains(".")||c2.contains(".")){
34. s.push(String.valueOf((Double.parseDouble(c2 + "") - Double
35. .parseDouble(c1 + ""))));
36. }
37. else{
38. s.push(String.valueOf((Integer.parseInt(c2 + "") - Integer
39. .parseInt(c1 + ""))));
40. }
41. } else if ("*".equals(ch)) {
42. if(c1.contains(".")||c2.contains(".")){
43. s.push(String.valueOf((Double.parseDouble(c2 + "") * Double
44. .parseDouble(c1 + ""))));
45. }
46. else{
47. s.push(String.valueOf((Integer.parseInt(c2 + "") * Integer
48. .parseInt(c1 + ""))));
49. }
50. } else if ("/".equals(ch)) {
51. s.push(String.valueOf((Double.parseDouble(c2 + "") / Double
52. .parseDouble(c1 + ""))));
53. }
55. } else {
56. System.out.println("式子有問題!");
57. return null;
58. }
59. }
60. }
61. return s.pop();
62. }
63. }

TfUtils.java

1. package org.xiazdong;
3. import java.io.Serializable;
5. public class TfUtils implements Serializable{
6. private int result;
7. private String expr = ""; //存放中綴表達式
9. public String getExpr() {
10. return expr;
11. }
13. public void setExpr(String expr) {
14. this.expr = expr;
15. }
17. /*
18. (操作符1)
19. / \
20. (操作符2) (操作數4)
21. / \
22. (操作符3) (操作數3)
23. / \
24. (操作數1) (操作數2)
25. */
26. private int tree1[] = new int[7];; // 存放第一棵樹
27. //private int tree2[]; // 存放第二棵樹
28. private final int PLUS = 1; // 加
29. private final int MINUS = 2; // 減
30. private final int MULT = 3; // 乘
31. private final int DIV = 4; // 除
33. /**
34. * 計算24點的主函數
35. */
36. public void calculate(int a, int b, int c, int d) {
38. int data[] = { a, b, c, d };
41. // 1.用數組構建一棵樹，其中0,1,3處填操作符；2,4,5,6填充操作數
42. // 2.按照參數a,b,c,d不同順序填充樹，+-*/也填充
43. for (int h = 0; h < 4; h++) {
44. for (int i = 0; i < 4; i++) {
45. if (i == h) {
46. continue;
47. }
48. for (int j = 0; j < 4; j++) {
49. if (j == i || j == h) {
50. continue;
51. }
52. for (int k = 0; k < 4; k++) {
53. if (k == h || k == i || k == j) {
54. continue;
55. }
56. tree1[2] = data[h];
57. tree1[4] = data[i];
58. tree1[5] = data[j];
59. tree1[6] = data[k];
61. // 填充操作符
62. for (int m = PLUS; m <= DIV; m++) {
63. for (int n = PLUS; n <= DIV; n++) {
64. for (int o = PLUS; o <= DIV; o++) {
65. tree1[0] = m;
66. tree1[1] = n;
67. tree1[3] = o;
68. String t[] = new String[4];
69. for (int z = 0; z < 4; z++) {
70. switch (tree1[z]) {
71. case PLUS:
72. t[z] = "+";
73. break;
74. case MINUS:
75. t[z] = "-";
76. break;
77. case MULT:
78. t[z] = "*";
79. break;
80. case DIV:
81. t[z] = "/";
82. break;
83. }
84. }
86. // 目前為止tree數組全部已賦值
87. String postexpr = tree1[5] + " " + tree1[6]
88. + " " + t[3] + " " + tree1[4] + " "
89. + t[1] + " " + tree1[2] + " " + t[0];
90. String result = CalculatorUtils
91. .calculateReversePolish(postexpr);
92. if (Double.parseDouble((result)) == 24.0) {
93. expr = "(((" + tree1[5] + t[3] + tree1[6]
94. + ")" + t[1] + tree1[4] + ")"
95. + t[0] + tree1[2] + ")";
96. System.out.println(expr);
97. return;
98. }
99. }
100. }
101. }
102. }
103. }
104. }
105. }
106. //tree2 = new int[7];
107. for (int h = 0; h < 4; h++) {
108. for (int i = 0; i < 4; i++) {
109. if (i == h) {
110. continue;
111. }
112. for (int j = 0; j < 4; j++) {
113. if (j == i || j == h) {
114. continue;
115. }
116. for (int k = 0; k < 4; k++) {
117. if (k == h || k == i || k == j) {
118. continue;
119. }
120. tree1[3] = data[h];
121. tree1[4] = data[i];
122. tree1[5] = data[j];
123. tree1[6] = data[k];
125. // 填充操作符
126. for (int m = PLUS; m <= DIV; m++) {
127. for (int n = PLUS; n <= DIV; n++) {
128. for (int o = PLUS; o <= DIV; o++) {
129. tree1[0] = m;
130. tree1[1] = n;
131. tree1[2] = o;
132. String t[] = new String[3];
133. for (int z = 0; z < 3; z++) {
134. switch (tree1[z]) {
135. case PLUS:
136. t[z] = "+";
137. break;
138. case MINUS:
139. t[z] = "-";
140. break;
141. case MULT:
142. t[z] = "*";
143. break;
144. case DIV:
145. t[z] = "/";
146. break;
147. }
148. }
149. // 目前為止tree數組全部已賦值
150. String postexpr = tree1[4] + " " + tree1[3]
151. + " " + t[1] + " " + tree1[6] + " "
152. + tree1[5] + " " + t[2] + " " + t[0];
153. String result = CalculatorUtils
154. .calculateReversePolish(postexpr);
155. if (Double.parseDouble((result)) == 24.0) {
156. expr = "((" + tree1[3] + t[1] + tree1[4]
157. + ")" + t[0] +"("+tree1[5]
158. + t[2] + tree1[6] + "))";
159. System.out.println(expr);
160. return;
161. }
162. }
163. }
164. }
165. }
166. }
167. }
168. }
169. expr = "無解";
170. }
172. public int getResult() {
173. return result;
174. }
176. public void setResult(int result) {
177. this.result = result;
178. }
182. }

測試代碼：

1. TfUtils tf = new TfUtils();
2. tf.calculate(d1, d2, d3, d4);
3. System.out.println(tf.getExpr());

輸入為：3,3,7,7

輸出為：（（（3/7）+3）*7）