9 8 7 6 5 4 3 2 1 = 100

题目描述：现有一等式；9 8 7 6 5 4 3 2 1 = 100。为了使等式成立，需要在数字间填写加号或者减号（可以不填，但不能填入其他符号）。之间没有填入符号的数字组合成一个数。例如；98 - 76 + 54 + 3 + 21 = 100 和 98 - 7 - 6 - 5 - 4 + 3 + 21 = 100。请编写代码找出所有符合等式的答案。

解决思路：

• 用暴力解法，一共9个数字，数字与数字之间有8个空，那么每个空有三种情况：加号、减号和空。那么一共有种情况。

import java.util.Stack;

/**
 * 1 2 3 4 5 6 7 8 9 = 110
 * 在数字间填入加号或者减号（可以不填，但不能填入其它符号）使等式成立。
 * 一种更好的方法是：
 * 每一个空隙之间都有三种可能，"+", "-", ""，所以一共有3^8种可能。
 */
public class Main {

    private static final char[] NUMBERS = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    private static final String[] OPERATORS = {"+", "-", ""};
    private static final int RESULT = 100;  // 计算结果


    private static void sortAndCompute(int numIndex, String buffer) {
        // 说明到最后一个字符了
        if(numIndex == NUMBERS.length - 1) {
            buffer += NUMBERS[numIndex];
            String formula = buffer.toString();
            if(sum(formula) == RESULT) {
                System.out.println(formula + " = " + RESULT);
            }
            return;
        }

        for(int operIndex = 0; operIndex < OPERATORS.length; ++operIndex) {
            buffer += NUMBERS[numIndex];
            buffer += OPERATORS[operIndex];
            sortAndCompute(numIndex + 1, buffer);
            // 消除前面两个已经添加的字符恢复原状，以便下一次循环的叠加
            // 但是当中间连接符变为''的时候，则只删除buffer中的前面一个字符
            buffer = operIndex != 2 ? buffer.substring(0, buffer.length() - 2)
                    : buffer.substring(0, buffer.length() - 1);
        }
    }

    private static int sum(String formula) {
        if(formula == null || formula.trim().length() == 0)
            throw new IllegalArgumentException("formula is invalid!");

        Stack<String> numStack = new Stack<String>();
        Stack<String> operStack = new Stack<String>();
        StringBuffer numBuffer = new StringBuffer();

        formula += "#"; // 添加一个结束符到公式末尾便于计算
        char[] chs = formula.toCharArray();
        for(int index = 0; index < formula.length(); ++index) {
            if(chs[index] != '+' && chs[index] != '-' && chs[index] != '#') {
                numBuffer.append(chs[index]); //把数放进入，如果是9 8，则会拼接起来
            } else {
                numStack.push(numBuffer.toString()); //将数放入stack
                numBuffer.delete(0, numBuffer.length()); //将buffer清空

                if(operStack.isEmpty()){
                    operStack.push(chs[index] + "");
                }else {
                    int numAft = Integer.parseInt(numStack.pop()); //取一数
                    int numBef = Integer.parseInt(numStack.pop());//取另一个数
                    String oper = operStack.pop(); // 取符号
                    int sum = oper.equals("+") ? numBef + numAft : numBef - numAft;
                    numStack.push(sum + ""); //将运算后的数压栈
                    operStack.push(chs[index] + ""); //将新符号压栈
                }
            }
        }
        return Integer.parseInt(numStack.pop());
    }

    public static void main(String[] args) {
        sortAndCompute(0, "");
    }
}