那啥……穷举实现的24点（rev1）

相关链接：
那啥……穷举实现的24点

昨天那帖里提到，那个实现并不完整，会漏掉一些情况。漏掉的是什么呢？
假如我们用n代表一个数字，用o代表一个运算符，那么昨天实现的运算是这样的形式的后序表达式：

n n o n o n o

实际上因为减法与除法不满足交换律，所以另外几种情况也必须考虑到。
一共是5种情况：
后序表达式 => 中序表达式

n n n n o o o => n o ( n o ( n o n ) )
n n n o n o o => n o ( ( n o n ) o n ) )
n n n o o n o => ( n o ( n o n ) ) o n
n n o n n o o => ( n o n ) o ( n o n )
n n o n o n o => ( ( n o n ) o n ) o n

思路是：以后序表达式考虑，一共是7个空位，其中头两个必须是数字，最后一个必须是运算符；从左向右看，每个位置之前的数字的个数至少要比运算符的个数多一个。于是得到上面的5种情况。

把昨天漏掉的情况加进来，我做了下面的实现，暂且叫rev1。
不过这个实现并没有尝试去消除所有本质上相同的表达式（在后缀表达式中本质上相同但写法不同的表达式会由满足交换律的运算而产生），只是把三个运算都是加法或者乘法的情况作为特殊情况单独计算了而已。
还是把生成全排列的部分换成了递归的方法。昨天那个三层for循环嵌套的方法太ad-hoc了，不爽。

说起来，我并没有用栈去计算表达式，实际上也没有用后序表达式来做计算。只是用后序表达式来输出，想绕开括号问题而已。在rev1的实现里，只要在Evaluator里把其中的几个toString()方法改掉就能改回到以中序方式输出；不想在括号上多麻烦的话，可以只给加法和减法的两边加括号——因为这里运算优先级最高的除括号外就是乘法和除法了，它们两边加不加括号都可以。有个小陷阱就是了：a * b / c与a * ( b / c )不一定一样，因为b不一定是c的倍数，但a * b可能是c的倍数。

在Operator和两个Tuple类里都添加了些暂时还没用上的方法（例如说运算符优先级、Iteratable<E>的实现、equals()的覆盖等），不过如果以后还想改进的话说不定会用到，就留着了。
Anyway，这代码里一个switch也没有，因为没有这个必要。依靠面向对象的多态性，没必要让代码被switch所污染。在多个地方对某种整型代码做switch的话，很可能改一处就改一堆地方，太麻烦……

要是Java支持类似C#的indexer就好了……那样就不用写一堆get(0)、get(1)之类的 T T

Calc24.java:

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

public class Calc24 {
    private HashSet<OperandTuple> operandTupleSet;
    private HashSet<OperatorTuple> operatorTupleSet;
    private int[] inputOperand;

    public Calc24() {
        this.operandTupleSet  = new HashSet<OperandTuple>();
        this.operatorTupleSet = new HashSet<OperatorTuple>();
        this.inputOperand = promptInput();
        this.permutateOperand();
        for (Operator op1 : Operator.values())
            for (Operator op2 : Operator.values())
                for (Operator op3 : Operator.values())
                    this.operatorTupleSet.add(new OperatorTuple(op1, op2, op3));
    }

    public static void main(String[] args) {
        Calc24 program = new Calc24();
        HashSet<String> resultSet = new HashSet<String>();
        OperandTuple numTuple = new OperandTuple(program.inputOperand[0], program.inputOperand[1], program.inputOperand[2], program.inputOperand[3]);
        OperatorTuple opAddTuple = new OperatorTuple(Operator.Add, Operator.Add, Operator.Add);
        OperatorTuple opMulTuple = new OperatorTuple(Operator.Multiply, Operator.Multiply, Operator.Multiply);
        program.operatorTupleSet.remove(opAddTuple);
        program.operatorTupleSet.remove(opMulTuple);
        
        // special case handling
        if (Evaluator.TYPE1.eval(numTuple, opAddTuple) == 24)
            resultSet.add(Evaluator.TYPE1.toString(numTuple, opAddTuple));
        if (Evaluator.TYPE1.eval(numTuple, opMulTuple) == 24)
            resultSet.add(Evaluator.TYPE1.toString(numTuple, opMulTuple));
        // evaluate all other possible expressions
        for (OperandTuple operandTuple : program.operandTupleSet)
            for (OperatorTuple operatorTuple : program.operatorTupleSet)
                for (Evaluator ev : Evaluator.values())
                    try {
                        if (ev.eval(operandTuple, operatorTuple) == 24)
                            resultSet.add(ev.toString(operandTuple, operatorTuple));
                    } catch (Exception e) { } // skip when modulo is not zero in a division
        for (String expression : resultSet)
            System.out.println(expression);
    }

    private static int[] promptInput() {
        int[] input = new int[4];
        BufferedReader reader = null;
        String line = null;
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            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 try again.");
                    --i;
                }
            }
        } catch (Exception e) { // ignore other exceptions
        }
        return input;
    }

    // print N! permutation of the elements of array a (not in order)
    private void permutateOperand() {
        int[] indices = new int[] { 0, 1, 2, 3 };
        permutateOperand(indices, indices.length);
    }

    private void permutateOperand(int[] array, int length) {
        if (length == 1) {
            this.operandTupleSet.add(new OperandTuple(
                    this.inputOperand[array[0]], this.inputOperand[array[1]],
                    this.inputOperand[array[2]], this.inputOperand[array[3]]));
            return;
        }
        for (int i = 0; i < length; i++) {
            swap(array, i, length - 1);
            permutateOperand(array, length - 1);
            swap(array, i, length - 1);
        }
    }

    // swap the numbers at indices i and j
    private static void swap(int[] array, int i, int j) {
        int temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

OperandTuple.java:

import java.util.Arrays;
import java.util.Iterator;

public class OperandTuple implements Iterable<Integer> {
    private Integer[] numbers;

    public OperandTuple(int first, int second, int third, int fourth) {
        this.numbers = new Integer[4];
        this.numbers[0] = first;
        this.numbers[1] = second;
        this.numbers[2] = third;
        this.numbers[3] = fourth;
    }

    public int get(int index) {
        return this.numbers[index];
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof OperandTuple) {
            OperandTuple rhs = (OperandTuple) obj;
            return Arrays.equals(this.numbers, rhs.numbers);
        }
        return false;
    }
    
    @Override
    public int hashCode() {
        return Arrays.hashCode(this.numbers);
    }

    public Iterator<Integer> iterator() {
        return Arrays.asList(this.numbers).iterator();
    }
}

OperatorTuple.java:

import java.util.Arrays;
import java.util.Iterator;

public class OperatorTuple implements Iterable<Operator> {
    private Operator[] operators;

    public OperatorTuple(Operator first, Operator second, Operator third) {
        this.operators = new Operator[3];
        this.operators[0] = first;
        this.operators[1] = second;
        this.operators[2] = third;
    }
    
    public Operator get(int index) {
        return this.operators[index];
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof OperatorTuple) {
            OperatorTuple rhs = (OperatorTuple) obj;
            return Arrays.equals(this.operators, rhs.operators);
        }
        return false;
    }
    
    @Override
    public int hashCode() {
        return Arrays.hashCode(this.operators);
    }

    public Iterator<Operator> iterator() {
        return Arrays.asList(this.operators).iterator();
    }
}

Operator.java:

public enum Operator {
    Add("+", 1) {
        int invoke(int first, int second) {
            return first + second;
        }
    },
    Minus("-", 1) {
        int invoke(int first, int second) {
            return first - second;
        }
    },
    Multiply("*", 2) {
        int invoke(int first, int second) {
            return first * second;
        }
    },
    Divide("/", 2) {
        int invoke(int first, int second) {
            if (!canDivide(first, second)) throw new CannotDivideException(first + ", " + second);
            return first / second;
        }
    };
    
    private String opChar;
    private int precedence;
    
    Operator(String opChar, int precedence) {
        this.opChar = opChar;
        this.precedence = precedence;
    }
    
    abstract int invoke(int first, int second);
    
    @Override
    public String toString() {
        return this.opChar;
    }
    
    public int getPrecedence() {
        return this.precedence;
    }
    
    public static boolean canDivide(int first, int second) {
        return (first % second) == 0;
    }
}

Evaluator.java:

public enum Evaluator {
    TYPE1 { // num1 num2 num3 num4 op1 op2 op3
        public int eval(OperandTuple nums, OperatorTuple ops) {
            return ops.get(2).invoke(nums.get(0), ops.get(1).invoke(nums.get(1), ops.get(0).invoke(nums.get(2), nums.get(3))));
        }
        public String toString(OperandTuple nums, OperatorTuple ops) {
            return (nums.get(0) + " " + nums.get(1) + " " + nums.get(2) + " " + nums.get(3) + " " + ops.get(0) + " " + ops.get(1) + " " + ops.get(2));
        }
    },
    TYPE2{ // num1 num2 num3 op1 num4 op2 op3
        public int eval(OperandTuple nums, OperatorTuple ops) {
            return ops.get(2).invoke(nums.get(0), ops.get(1).invoke(ops.get(0).invoke(nums.get(1), nums.get(2)), nums.get(3)));
        }
        public String toString(OperandTuple nums, OperatorTuple ops) {
            return (nums.get(0) + " " + nums.get(1) + " " + nums.get(2) + " " + ops.get(0) + " " + nums.get(3) + " " + ops.get(1) + " " + ops.get(2));
        }
    },
    TYPE3{ // num1 num2 num3 op1 op2 num4 op3
        public int eval(OperandTuple nums, OperatorTuple ops) {
            return ops.get(2).invoke(ops.get(1).invoke(nums.get(0), ops.get(0).invoke(nums.get(1), nums.get(2))), nums.get(3));
        }
        public String toString(OperandTuple nums, OperatorTuple ops) {
            return (nums.get(0) + " " + nums.get(1) + " " + nums.get(2) + " " + ops.get(0) + " " + ops.get(1) + " " + nums.get(3) + " " + ops.get(2));
        }
    },
    TYPE4{ // num1 num2 op1 num3 num4 op2 op3
        public int eval(OperandTuple nums, OperatorTuple ops) {
            return ops.get(2).invoke(ops.get(0).invoke(nums.get(0), nums.get(1)), ops.get(1).invoke(nums.get(2), nums.get(3)));
        }
        public String toString(OperandTuple nums, OperatorTuple ops) {
            return (nums.get(0) + " " + nums.get(1) + " " + ops.get(0) + " " + nums.get(2) + " " + nums.get(3) + " " + ops.get(1) + " " + ops.get(2));
        }
    },
    TYPE5{ // num1 num2 op1 num3 op2 num4 op3
        public int eval(OperandTuple nums, OperatorTuple ops) {
            return ops.get(2).invoke(ops.get(1).invoke(ops.get(0).invoke(nums.get(0), nums.get(1)), nums.get(2)), nums.get(3));
        }
        public String toString(OperandTuple nums, OperatorTuple ops) {
            return (nums.get(0) + " " + nums.get(1) + " " + ops.get(0) + " " + nums.get(2) + " " + ops.get(1) + " " + nums.get(3) + " " + ops.get(2));
        }
    };
    
    abstract public int eval(OperandTuple nums, OperatorTuple ops);
    abstract public String toString(OperandTuple nums, OperatorTuple ops);
}

CannotDivideException.java:

public class CannotDivideException extends RuntimeException {
    private static final long serialVersionUID = -9174448473262875939L;

    public CannotDivideException() {
        super();
    }
    
    public CannotDivideException(String message) {
        super(message);
    }
}

评论

3 楼 RednaxelaFX 2008-08-11  

在CodeProject上看到另一种更受限制的24点问题，和对应的一种解：The 24 Puzzle

2 楼 RednaxelaFX 2008-04-09  

我这也是傻瓜型的……总之算法什么的完全跟“优化”沾不上边。只是做了：
1、充分使用Java的语法
2、使用面向对象的“壳”……骨子里嘛，嘛rev1的代码比昨天的稍微好点吧。

1 楼 jhpx 2008-04-09  

偶以前用C写过一个递归的傻瓜型24点……