我有一个方法，确定一个等于24的表达式是否可以由4个完整的数组元素组成。
在入口处：从1到9的4个整数数组。
输出：true（如果表达式等于24可以从给定的集合构造）或false（如果不可能从给定集合构建这样的表达式）。
允许的算术运算符：加法，减法，乘法，除法，括号。
Example:
Input: [4, 1, 8, 7]
at the exit: true
explanation: (8 - 4) * (7 - 1) = 24
如果没有一系列组合，我怎么能这样做呢？
public static boolean canBeEqualTo24(int[] nums) {
if (nums.length < 4 || nums.length > 4) return false;
for (int num : nums) {
if (num < 1 || num > 9) return false;
}
final int RESULT = 24;
if (nums[0] + nums[1] + nums[2] + nums[3] == RESULT) return true;
if (nums[0] * nums[1] * nums[2] * nums[3] == RESULT) return true;
int[][] combinations = {
{0, 1, 2, 3},
{0, 1, 3, 2},
{0, 2, 1, 3},
{0, 2, 3, 1},
{0, 3, 2, 1},
{0, 3, 1, 2},
{1, 0, 2, 3},
{1, 0, 3, 2},
{1, 2, 0, 3},
{1, 2, 3, 0},
{1, 3, 2, 0},
{1, 3, 0, 2},
{2, 0, 1, 3},
{2, 0, 3, 1},
{2, 1, 0, 3},
{2, 1, 3, 0},
{2, 3, 0, 1},
{2, 3, 1, 0},
{3, 0, 1, 2},
{3, 0, 2, 1},
{3, 1, 0, 2},
{3, 1, 2, 0},
{3, 2, 0, 1},
{3, 2, 1, 0},
};
int i = 0;
while (i < combinations.length) {
int a = nums[combinations[i][0]];
int b = nums[combinations[i][1]];
int c = nums[combinations[i][2]];
int d = nums[combinations[i][3]];
if (a + b + c - d == RESULT) return true;
if (a + b - c - d == RESULT) return true;
if (a + b + c * d == RESULT) return true;
if (a + b * c * d == RESULT) return true;
if (a - b + c * d == RESULT) return true;
if (-a + b * c - d == RESULT) return true;
if (a * b * c - d == RESULT) return true;
if (a + b * (c + d) == RESULT) return true;
if (a - b * (c + d) == RESULT) return true;
if (a + b * (c - d) == RESULT) return true;
if (a * b * (c + d) == RESULT) return true;
if (a * b * (c - d) == RESULT) return true;
if (-a + b * (c - d) == RESULT) return true;
if (a * (b + c + d) == RESULT) return true;
if (a * (b + c - d) == RESULT) return true;
if (a * (b - c - d) == RESULT) return true;
if (-a + (b * (c + d)) == RESULT) return true;
if ((a + b) * (c + d) == RESULT) return true;
if ((a - b) * (c + d) == RESULT) return true;
if ((a - b) * (c - d) == RESULT) return true;
if ((a * b) + (c * d) == RESULT) return true;
if ((a * b) - (c * d) == RESULT) return true;
if (a * (b * c - d) == RESULT) return true;
if (a * (b * c + d) == RESULT) return true;
if (d != 0) {
if (a * b - c / d == RESULT && c % d == 0) return true;
if (a + b - c / d == RESULT && c % d == 0) return true;
if ((a * b) / d + c == RESULT && (a * b) % d == 0) return true;
if (((a + b) * c) / d == RESULT && ((a + b) * c) % d == 0) return true;
if (((a - b) * c) / d == RESULT && ((a - b) * c) % d == 0) return true;
if (((a * b) - c) / d == RESULT && ((a * b) - c) % d == 0) return true;
if (((a * d + c) * b) / d == RESULT && ((a * d + c) * b) % d == 0) return true;
if (((a * d - c) * b) / d == RESULT && ((a * d - c) * b) % d == 0) return true;
}
if (d * c != 0) {
if ((a * b) / (d * c) == RESULT && (a * b) % (d * c) == 0) return true;
}
if (c - d != 0) {
if ((a * b) / (c - d) == RESULT && (a * b) % (c - d) == 0) return true;
}
if (c + d != 0) {
if ((a * b) / (c + d) == RESULT && (a * b) % (c + d) == 0) return true;
}
if ((a * c - b) != 0) {
if ((d * c) / (a * c - b) == RESULT && (d * c) % (a * c - b) == 0) return true;
}
i++;
}
return false;
}
我以前做过这个，我的解决方案有效，并且给了我很好的成绩。但后来我在一个网站上发现了这个问题，这个解决方案既复杂又冗长，但却采用了更优雅，更系统的方法：
import java.util.*;
public class Game24Player {
final String[] patterns = {"nnonnoo", "nnonono", "nnnoono", "nnnonoo",
"nnnnooo"};
final String ops = "+-*/^";
String solution;
List<Integer> digits;
public static void main(String[] args) {
new Game24Player().play();
}
void play() {
digits = getSolvableDigits();
Scanner in = new Scanner(System.in);
while (true) {
System.out.print("Make 24 using these digits: ");
System.out.println(digits);
System.out.println("(Enter 'q' to quit, 's' for a solution)");
System.out.print("> ");
String line = in.nextLine();
if (line.equalsIgnoreCase("q")) {
System.out.println("\nThanks for playing");
return;
}
if (line.equalsIgnoreCase("s")) {
System.out.println(solution);
digits = getSolvableDigits();
continue;
}
char[] entry = line.replaceAll("[^*+-/)(\\d]", "").toCharArray();
try {
validate(entry);
if (evaluate(infixToPostfix(entry))) {
System.out.println("\nCorrect! Want to try another? ");
digits = getSolvableDigits();
} else {
System.out.println("\nNot correct.");
}
} catch (Exception e) {
System.out.printf("%n%s Try again.%n", e.getMessage());
}
}
}
void validate(char[] input) throws Exception {
int total1 = 0, parens = 0, opsCount = 0;
for (char c : input) {
if (Character.isDigit(c))
total1 += 1 << (c - '0') * 4;
else if (c == '(')
parens++;
else if (c == ')')
parens--;
else if (ops.indexOf(c) != -1)
opsCount++;
if (parens < 0)
throw new Exception("Parentheses mismatch.");
}
if (parens != 0)
throw new Exception("Parentheses mismatch.");
if (opsCount != 3)
throw new Exception("Wrong number of operators.");
int total2 = 0;
for (int d : digits)
total2 += 1 << d * 4;
if (total1 != total2)
throw new Exception("Not the same digits.");
}
boolean evaluate(char[] line) throws Exception {
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) {
throw new Exception("Invalid entry.");
}
return (Math.abs(24 - s.peek()) < 0.001F);
}
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;
}
}
List<Integer> randomDigits() {
Random r = new Random();
List<Integer> result = new ArrayList<>(4);
for (int i = 0; i < 4; i++)
result.add(r.nextInt(9) + 1);
return result;
}
List<Integer> getSolvableDigits() {
List<Integer> result;
do {
result = randomDigits();
} while (!isSolvable(result));
return result;
}
boolean isSolvable(List<Integer> digits) {
Set<List<Integer>> dPerms = new HashSet<>(4 * 3 * 2);
permute(digits, dPerms, 0);
int total = 4 * 4 * 4;
List<List<Integer>> oPerms = new ArrayList<>(total);
permuteOperators(oPerms, 4, total);
StringBuilder sb = new StringBuilder(4 + 3);
for (String pattern : patterns) {
char[] patternChars = pattern.toCharArray();
for (List<Integer> dig : dPerms) {
for (List<Integer> opr : oPerms) {
int i = 0, j = 0;
for (char c : patternChars) {
if (c == 'n')
sb.append(dig.get(i++));
else
sb.append(ops.charAt(opr.get(j++)));
}
String candidate = sb.toString();
try {
if (evaluate(candidate.toCharArray())) {
solution = postfixToInfix(candidate);
return true;
}
} catch (Exception ignored) {
}
sb.setLength(0);
}
}
}
return false;
}
String postfixToInfix(String postfix) {
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 = ops.indexOf(o) / 2;
}
}
Stack<Expression> expr = new Stack<>();
for (char c : postfix.toCharArray()) {
int idx = ops.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;
}
char[] infixToPostfix(char[] infix) throws Exception {
StringBuilder sb = new StringBuilder();
Stack<Integer> s = new Stack<>();
try {
for (char c : infix) {
int idx = ops.indexOf(c);
if (idx != -1) {
if (s.isEmpty())
s.push(idx);
else {
while (!s.isEmpty()) {
int prec2 = s.peek() / 2;
int prec1 = idx / 2;
if (prec2 >= prec1)
sb.append(ops.charAt(s.pop()));
else
break;
}
s.push(idx);
}
} else if (c == '(') {
s.push(-2);
} else if (c == ')') {
while (s.peek() != -2)
sb.append(ops.charAt(s.pop()));
s.pop();
} else {
sb.append(c);
}
}
while (!s.isEmpty())
sb.append(ops.charAt(s.pop()));
} catch (EmptyStackException e) {
throw new Exception("Invalid entry.");
}
return sb.toString().toCharArray();
}
void permute(List<Integer> lst, Set<List<Integer>> res, int k) {
for (int i = k; i < lst.size(); i++) {
Collections.swap(lst, i, k);
permute(lst, res, k + 1);
Collections.swap(lst, k, i);
}
if (k == lst.size())
res.add(new ArrayList<>(lst));
}
void permuteOperators(List<List<Integer>> res, int n, int total) {
for (int i = 0, npow = n * n; i < total; i++)
res.add(Arrays.asList((i / npow), (i % npow) / n, i % n));
}
}
注意：Here你可以找到这个网站。请告诉我这是否适合您，并始终给予所有者信用。
编辑：你必须改变这个代码，因为它产生random numbersand检查它们是否可以是solved得到24结果，如果它们不然后它将产生另一组random variables并保持ding直到它们产生这样的数字可以解决。
提示：检查方法如
isSolvable()getSolvableDigits()randomDigits()并根据您的意愿编辑它们。