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, "");
    }
}