This isn't meant to be the fastest solution, but rather an instructive one.
- It recursively generates all equations in postfix notation
- It also provides a translation from postfix to infix notation
- There is no actual arithmetic calculation done, so you have to implement that on your own
- Be careful about division by zero
With 4 operands, 4 possible operators, it generates all 7680 = 5 * 4! * 4^3
possible expressions.
- 5 is Catalan(3). Catalan(N) is the number of ways to paranthesize N+1 operands.
- 4! because the 4 operands are permutable
- 4^3 because the 3 operators each have 4 choice
This definitely does not scale well, as the number of expressions for N operands is [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...].
In general, if you have n+1
operands, and must insert n
operators chosen from k
possibilities, then there are (2n)!/n! k^n
possible equations.
Good luck!
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);
}
}