这并不意味着是最快的解决方案,而是一个有启发性的解决方案。
- 它以后缀符号递归生成所有方程
- 它还提供从后缀到中缀符号的翻译
- 没有实际的算术计算,所以你必须自己实现
使用 4 个操作数,4 个可能的运算符,它生成所有 7680 = 5 * 4!* 4^3 种可能的表达方式。
- 5是加泰罗尼亚语(3)。Catalan(N) 是对 N+1 个操作数进行括号运算的方法数。
- 4!因为 4 个操作数是可置换的
- 4^3 因为这 3 个操作员各有 4 个选择
这肯定不能很好地扩展,因为 N 个操作数的表达式数量是 [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...]。
一般来说,如果你有n+1
操作数,并且必须插入n
从k
可能性中选择的运算符,那么就有(2n)!/n! k^n
可能的方程。
祝你好运!
import java.util.*;
public class Expressions {
static String operators = "+-/*";
static String translate(String postfix) {
Stack<String> expr = new Stack<String>();
Scanner sc = new Scanner(postfix);
while (sc.hasNext()) {
String t = sc.next();
if (operators.indexOf(t) == -1) {
expr.push(t);
} else {
expr.push("(" + expr.pop() + t + expr.pop() + ")");
}
}
return expr.pop();
}
static void brute(Integer[] numbers, int stackHeight, String eq) {
if (stackHeight >= 2) {
for (char op : operators.toCharArray()) {
brute(numbers, stackHeight - 1, eq + " " + op);
}
}
boolean allUsedUp = true;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != null) {
allUsedUp = false;
Integer n = numbers[i];
numbers[i] = null;
brute(numbers, stackHeight + 1, eq + " " + n);
numbers[i] = n;
}
}
if (allUsedUp && stackHeight == 1) {
System.out.println(eq + " === " + translate(eq));
}
}
static void expression(Integer... numbers) {
brute(numbers, 0, "");
}
public static void main(String args[]) {
expression(1, 2, 3, 4);
}
}