这个问题有几个挑战。下面的解决方案大约有两百行。它可能比任务要求的稍微长一点，因为我将其推广到了任意数量的术语。我鼓励你学习算法并编写自己的解决方案。
我们必须克服的主要障碍如下：
- 如何生成不重复的排列？
- 如何构建和评估算术表达式？
- 如何将表达式转换为唯一字符串？
生成排列的方法有很多。我选择了递归方法，因为它很容易理解。主要的复杂性在于术语可以重复，这意味着可能少于4! = 4 * 3 * 2 * 1个排列。例如，如果术语是1 1 1 2，则只有四种排列。
为了避免重复排列，我们首先对术语进行排序。递归函数从左到右找到所有重复项的位置，而不需要回溯。例如，一旦第一个1被放置在数组中，所有剩余的1术语都放置在它的右侧。但当我们到达2术语时，我们可以返回数组的开头。
为了构建算术表达式，我们使用另一个递归函数。该函数查看排列两个术语之间的每个位置，将数组分成左侧和右侧的段。它对左侧和右侧段分别进行一对递归调用，以构建表达式。最后，它使用四个算术运算符之一将生成的子表达式连接起来。基本情况是数组大小为1，因此无法拆分。这将导致一个没有运算符和子节点，只有值的节点。
通过对double值执行算术运算来评估表达式可能存在问题，因为浮点除法的不精确性。例如，1.0 / 3 = 0.33333 ...，但3 * 0.33333 ... = 0.99999 ...。当你使用double值时，这使得很难确定1/3 * 3 = 1。为避免这些困难，我定义了一个Fraction类。它在分数上执行算术运算，并始终通过最大公约数简化结果。除以零不会导致错误消息。相反，我们存储分数0/0。
拼图的最后一块就是将表达式转换为字符串。我们希望生成规范化的字符串，以避免不必要的重复。例如，我们不想显示
1 + (1 + (1 + 2))和
((1 + 1) + 1) + 2，因为这些实际上是相同的表达式。我们只想显示
1 + 1 + 1 + 2，而不是所有可能的括号组合。
我们可以通过仅在必要时添加括号来实现这一点。也就是说，如果具有高优先级运算符（乘法或除法）的节点是具有低优先级运算符（加法或减法）的节点的父节点，则需要使用括号。优先级指的是运算符优先级，也称为运算顺序。高优先级运算符比低优先级运算符更紧密地绑定。因此，如果父节点的优先级高于子节点的运算符，则需要给子节点加括号。为确保我们得到唯一的字符串，我们在将其添加到结果列表之前将其与哈希集进行比较。
以下程序Equation.java接受用户在命令行上的输入。游戏的参数在Equation类的第一行中。您可以修改这些参数以构建具有更多项、更大项和不同目标值的表达式。
import java.lang.*;
import java.util.*;
import java.io.*;
class Fraction {
int num, denom;
static int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
Fraction(int num, int denom) {
if (denom == 0) {
this.num = this.denom = 0;
} else {
int x = Fraction.gcd(num, denom);
this.num = num / x;
this.denom = denom / x;
}
}
Fraction plus(Fraction other) {
return new Fraction(this.num * other.denom + other.num * this.denom,
this.denom * other.denom);
}
Fraction minus(Fraction other) {
return this.plus(new Fraction(-other.num, other.denom));
}
Fraction times(Fraction other) {
return new Fraction(this.num * other.num, this.denom * other.denom);
}
Fraction divide(Fraction other) {
return new Fraction(this.num * other.denom, this.denom * other.num);
}
public String toString() {
if (denom == 1) {
return ""+num;
}
return num+"/"+denom;
}
}
class Expression {
Fraction value;
String operator;
Expression left, right;
static int level(String operator) {
if (operator.compareTo("+") == 0 || operator.compareTo("-") == 0) {
return 0;
}
return 1;
}
Expression(int x) {
value = new Fraction(x, 1);
}
Expression(Expression left, String operator, Expression right) {
if (operator == "+") {
value = left.value.plus(right.value);
} else if (operator == "-") {
value = left.value.minus(right.value);
} else if (operator == "*") {
value = left.value.times(right.value);
} else if (operator == "/") {
value = left.value.divide(right.value);
}
this.operator = operator;
this.left = left;
this.right = right;
}
public String toString() {
if (operator == null) {
return value.toString();
}
int level = Expression.level(operator);
String a = left.toString(), aOp = left.operator,
b = right.toString(), bOp = right.operator;
if (aOp != null && Expression.level(aOp) < level) {
a = "("+a+")";
}
if (bOp != null && Expression.level(bOp) < level) {
b = "("+b+")";
}
return a + " " + operator + " " + b;
}
}
public class Equation {
static int need = 4, min = 1, max = 9, target = 24;
int[] terms, permutation;
boolean[] used;
ArrayList<String> wins = new ArrayList<String>();
Set<String> winSet = new HashSet<String>();
String[] operators = {"+", "-", "*", "/"};
ArrayList<Expression> make(int left, int right) {
ArrayList<Expression> result = new ArrayList<Expression>();
if (left+1 == right) {
result.add(new Expression(permutation[left]));
} else {
for (int i = left+1; i < right; ++i) {
ArrayList<Expression> leftSide = make(left, i);
ArrayList<Expression> rightSide = make(i, right);
for (int j = 0; j < leftSide.size(); ++j) {
for (int k = 0; k < rightSide.size(); ++k) {
for (int p = 0; p < operators.length; ++p) {
result.add(new Expression(leftSide.get(j),
operators[p],
rightSide.get(k)));
}
}
}
}
}
return result;
}
void formulate() {
ArrayList<Expression> expressions = make(0, terms.length);
for (int i = 0; i < expressions.size(); ++i) {
Expression expression = expressions.get(i);
Fraction value = expression.value;
if (value.num == target && value.denom == 1) {
String s = expressions.get(i).toString();
if (!winSet.contains(s)) {
wins.add(s);
winSet.add(s);
}
}
}
}
void permute(int termIx, int pos) {
if (pos == terms.length) {
return;
}
if (!used[pos]) {
permutation[pos] = terms[termIx];
if (termIx+1 == terms.length) {
formulate();
} else {
used[pos] = true;
if (terms[termIx+1] == terms[termIx]) {
permute(termIx+1, pos+1);
} else {
permute(termIx+1, 0);
}
used[pos] = false;
}
}
permute(termIx, pos+1);
}
void solve(int[] terms) {
this.terms = terms;
Arrays.sort(terms);
permutation = new int[terms.length];
used = new boolean[terms.length];
permute(0, 0);
if (wins.size() == 0) {
System.out.println("There are no feasible expressions.");
} else if (wins.size() == 1) {
System.out.println("There is one feasible expression:");
} else {
System.out.println("There are "+wins.size()+" feasible expressions:");
}
for (int i = 0; i < wins.size(); ++i) {
System.out.println(wins.get(i) + " = " + target);
}
}
public static void main(String[] args) {
if (args.length != need) {
System.out.println("must specify "+need+" digits");
return;
}
int digits[] = new int[need];
for (int i = 0; i < need; ++i) {
try {
digits[i] = Integer.parseInt(args[i]);
} catch (NumberFormatException e) {
System.out.println("\""+args[i]+"\" is not an integer");
return;
}
if (digits[i] < min || digits[i] > max) {
System.out.println(digits[i]+" is outside the range ["+
min+", "+max+"]");
return;
}
}
(new Equation()).solve(digits);
}
}
b + a的情况，是否绝对需要包括a + b的情况？如果不是必需的，那么这可以减少并且括号可以轻松处理。 - Obicere