那啥……穷举实现的24点

呵呵，最近面试某公司的同学真多。早就听说他们上机考试要考24点的实现了，不过没想到那么多个同学都遇到了这一题。这不，对面宿舍有同学又要去面那公司了，找我问这24点怎么写。考虑到也不能写太难得方法不然同学记起来麻烦，干脆就写了个超直观超naive的穷举实现。哈哈。

首先是24点问题的定义。我采纳的定义是用户可以输入4个数字，每个数字可接受的范围是1-13的整数；对这4个数字做4则混合运算得到的结果是24时，则这个表达式被认为符合题目条件。

然后考虑一下如何穷举。如果把四个数字固定顺序，则有时候需要插入括号来改变运算优先级来得到符合条件的表达式，但这样挺麻烦的。这里取个巧，不是插入括号，而是改变4个输入参数的前后顺序来改变运算的先后顺序。
可是加减与乘除的优先级不同，怎么办呢？再取个巧，使用后缀表达式来处理一切与运算优先级相关的问题。用了后缀表达式就不必为括号而头疼了。

所以我们得到的表达式的形式会是类似：

num1 num2 op1 num3 op2 num4 op3

或者：

num1 num2 op1 num3 num4 op2 op3

或者：

num1 num2 num3 op1 num4 op2 op3

例如说，1 2 + 3 + 4 ×就是(1 + 2 + 3) * 4。
于是我们对4个输入的数字的顺序做一个全排列，为每种排列情况再对其中3个间隔上的运算符做穷举。

然后来看看代码。为了让同学有足够东西可以说，我用了Java 5里的3种新特性：泛型、enum和for-each。

不过当前的实现下，会漏掉一些情况。下面的代码只实现了上面列举的3种可能的第一种。
hmm，那倒也不太算个问题，因为反正是他们面试嘛诶……呵呵，明天再把不会漏掉运算情况的穷举的代码发出来。

Calc24.java:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Calc24 {
    public static void main(String[] args) throws Exception {
        int[] input = promptInput();
        int length = input.length;
        ArrayList<TupleOfFour> permutation = new ArrayList<TupleOfFour>();

        // get permutation of the four operands
        for (int i = 0; i < length; ++i) {
            for (int j = 0; j < length; ++j) {
                if (i == j) continue;
                for (int k = 0; k < length; ++k) {
                    if (i == k || j == k) continue;
                    int l = 6 - i - j - k;
                    permutation.add(new TupleOfFour(
                        input[i], input[j], input[k], input[l]));
                }
            }
        }

        // enumerate the operators, and evaluate the postfix expression
        for (TupleOfFour tuple : permutation) {
            int first = tuple.getFirst();
            int second = tuple.getSecond();
            int third = tuple.getThird();
            int fourth = tuple.getFourth();

            for (Operator op1 : Operator.values()) {
                if ((op1 == Operator.Divide) &&
                    !(Operator.canDivide(first, second))) continue;
                int result1 = op1.calculate(first, second);
                for (Operator op2 : Operator.values()) {
                    if ((op2 == Operator.Divide) &&
                        !(Operator.canDivide(result1, third))) continue;
                    int result2 = op2.calculate(result1, third);
                    for (Operator op3 : Operator.values()) {
                        if ((op3 == Operator.Divide) &&
                            !(Operator.canDivide(result2, fourth))) continue;
                        int result3 = op3.calculate(result2, fourth);
                        if (result3 == 24) {
                            // build a string representation
                            // of the postfix expression
                            StringBuilder builder = new StringBuilder();
                            builder.append(first);
                            builder.append(" ");
                            builder.append(second);
                            builder.append(" ");
                            builder.append(op1.getOpChar());
                            builder.append(" ");
                            builder.append(third);
                            builder.append(" ");
                            builder.append(op2.getOpChar());
                            builder.append(" ");
                            builder.append(fourth);
                            builder.append(" ");
                            builder.append(op3.getOpChar());

                            System.out.println(builder.toString());
                        } // end if
                    } // end of for-each op3
                } // end of for-each op2
            } // end of for-each op1
        } // end of for-each permutation
    } // end of main()

    private static int[] promptInput() throws Exception {
        int[] input = new int[4];
        BufferedReader reader = new BufferedReader(
            new InputStreamReader(System.in));
        String line = null;

        for (int i = 0; i < 4; ++i) {
            System.out.print("Enter a number (1 to 13): ");
            line = reader.readLine();
            try {
                input[i] = Integer.parseInt(line);
                if (input[i] < 1 || input[i] > 13)
                    throw new IllegalArgumentException();
            } catch (IllegalArgumentException e) {
                System.out.println("The input is invalid. Please re-enter.");
                --i;
            }
        }

        return input;
    }
}

TupleOfFour.java:

public class TupleOfFour {
    private int first;
    private int second;
    private int third;
    private int fourth;
    
    public TupleOfFour(int first, int second, int third, int fourth) {
        this.first = first;
        this.second = second;
        this.third = third;
        this.fourth = fourth;
    }

    public int getFirst() {
        return first;
    }

    public int getSecond() {
        return second;
    }

    public int getThird() {
        return third;
    }

    public int getFourth() {
        return fourth;
    }
}

Operator.java:

public enum Operator {
    Add('+') {
        int calculate(int first, int second) {
            return first + second;
        }
    },
    Minus('-') {
        int calculate(int first, int second) {
            return first - second;
        }
    },
    Multiply('*') {
        int calculate(int first, int second) {
            return first * second;
        }
    },
    Divide('/') {
        int calculate(int first, int second) {
            return first / second;
        }
    };
    
    private char opChar;
    
    Operator(char c) {
        this.opChar = c;
    }
    
    abstract int calculate(int first, int second);
    
    public char getOpChar() {
        return this.opChar;
    }
    
    public static boolean canDivide(int first, int second) {
        return (first % second) == 0;
    }
}