摘要：而對于前綴表達式和后綴表達式的計算，則十分的簡單。由上一篇文章可知，我們目前的類所表示的，就是中綴表達式，所以我們需要提供算法，將中綴表達式轉(zhuǎn)換為前綴表達式或者后綴表達式，從而方便我們計算表達式的值。

上一篇 文章講了如何通過正則來將輸入的表達式解析為多個 Token，而這篇文章的核心在于如何對 表達式求值。
我們輸入的表達式，即我們通常見到的表達式，都是中綴表達式 —— 中綴的含義是，在表達式中，運算符是放中間的，比如 (1 + 2) * 3，運算符都是在數(shù)的中間。然而在計算機的世界里，還存在著前綴表達式和后綴表達式 —— 由名字也很容易知道，前綴表達式是將運算符放在數(shù)之前，后綴表達式是將運算符放到數(shù)之后。

中綴表達式的劣勢在于，一旦表達式復雜化，比如多層括號嵌套同時還要注意運算符的優(yōu)先級，那么要編寫計算中綴表達式的值的代碼也十分的復雜。而對于前綴表達式和后綴表達式的計算，則十分的簡單。

以后綴表達式為例：

從左往右掃描表達式，如果遇到數(shù)，那么將數(shù)入棧

如果遇到運算符，那么從棧中依次彈出兩個數(shù) n1 和 n2，使用該運算符對這兩個數(shù)進行運算（n2 op n1），將獲得的結(jié)果數(shù)入棧

重復 1 和 2 直到表達式掃描結(jié)束，那么棧中最后剩余的數(shù)便是表達式的值。

比如上面的例子，1 + (3 - 2) * 4 / 5 = 1.8，對于后綴表達式 1 3 2 - 4 * 5 / +：

所以可見計算后綴表達式非常容易編碼。

由 上一篇 文章可知，我們目前的 Expression 類所表示的，就是中綴表達式，所以我們需要提供算法，將中綴表達式轉(zhuǎn)換為前綴表達式或者后綴表達式，從而方便我們計算表達式的值。當然，算法的流程，我們的計算機先輩們早就想出來了，而我們只需要做出實現(xiàn)即可。

同樣以后綴表達式為例，中綴表達式轉(zhuǎn)換為后綴表達式的算法流程如下：

初始化運算符棧 S 和用來保存中間結(jié)果的列表 L

從左往右掃描中綴表達式：

遇到數(shù)時，直接將其加入到 L

遇到運算符 op 時

2.1 如果 S 為空，那么直接將 op 入棧 S
2.2 如果 S 不空，并且 S 棧頂為左括號 "("，那么將 op 入棧 S
2.3 如果 S 不空，此時 S 棧頂為運算符，如果 op 的優(yōu)先級大于 S 棧頂元素的優(yōu)先級，那么將該運算符入棧 S
2.4 否則（即 op 的優(yōu)先級小于 S 棧頂元素的優(yōu)先級），將 S 的棧頂元素彈出，并將該元素加入 L；然后轉(zhuǎn)到 2.1 繼續(xù)判斷并比較。

遇到括號時

3.1 如果是左括號 "("，直接將該左括號入棧 S
3.2 如果是右括號 ")"，依次彈出 S 中的運算符，直到遇到一個左括號為止，然后將這一對括號都丟棄

將 S 中的剩余運算符依次彈出并加入 L

此時 L 中的所有的 Token 按順序即為后綴表達式

（關(guān)于中綴、前綴、后綴表達式轉(zhuǎn)換算法更詳細的內(nèi)容和例子，可以參考 前綴、中綴、后綴表達式 這篇文章，本文所寫的算法流程也是參考這篇文章而來。）

根據(jù)上面的算法，我們就不難在目前的 Expression 基礎(chǔ)上，寫出將中綴表達式轉(zhuǎn)換為后綴表達式的算法，我們將這個方法命名為 toPostfixExpr()：

/**
 * 獲得該表達式的后綴形式
 *
 * @return 后綴表達式
 */
public Expression toPostfixExpr() {
    ArrayDeque S = new ArrayDeque<>(); // 運算符棧
    ArrayList L = new ArrayList<>();   // 保存中間結(jié)果的列表

    for (Token token : tokens) {
        switch (token.getType()) {
            case NUMBER:
                L.add(token);
                break;

            case OPERATOR:
                Operator op = (Operator) token;
                boolean back = true;

                while (back) {
                    back = false;

                    if (S.isEmpty()) { // 運算符棧為空
                        S.push(op);

                    } else {  // 運算符棧不為空
                        Token top = S.peek();

                        // 運算符棧棧頂為 "("
                        if (top.isBracket() && ((Bracket) top).isLeft()) {
                            S.push(op);

                        // op 的優(yōu)先級大于運算符棧棧頂元素的優(yōu)先級
                        } else if (op.isHigherThan((Operator) top)) {
                            S.push(token);

                        } else { // op 的優(yōu)先級小于運算符棧棧頂元素的優(yōu)先級
                            L.add(S.pop());
                            back = true; // 回到 while
                        }
                    }
                }
                break;

            case BRACKET:
                if (((Bracket) token).isLeft()) {
                    S.push(token);

                } else {
                    for (Token t = S.pop();
                            !t.isBracket(); t = S.pop()) {
                        L.add(t);
                    }
                }
                break;
        }
    }

    while (!S.isEmpty()) {
        L.add(S.pop());
    }

    return new Expression(L, true); // true 表示該表達式為后綴表達式
}

此時我們往 Expression 中添加了一個 boolean 字段 postfix，用來標識該表達式是否為后綴表達式，postfix 默認為 false，如果為 true 則表明該表達式是后綴表達式。

public class Expression {
    ...

    private final List tokens; // 該表達式中的所有 Token
    private final boolean postfix;    // 該表達式是否為后綴表達式的標識

    public Expression(List tokens, boolean postfix) {
        this.tokens = tokens;
        this.postfix = postfix;
    }

    /**
     * 該表達式是否為后綴表達式
     *
     * @return 如果該表達式為后綴表達式返回 true，否則返回 false
     */
    public boolean isPostfix() {
        return postfix;
    }

    ...
}

然后，根據(jù)后綴表達式，我們也很容易寫出計算表達式值的方法，我們將方法命名為 calculate()：

/**
 * 通過后綴表達式計算表達式的值
 *
 * @return 表達式的值
 */
public Num calculate() {
    if (!isPostfix()) {
        throw new RuntimeException("請先將表達式轉(zhuǎn)為后綴表達式再計算");
    }

    ArrayDeque stack = new ArrayDeque<>();

    for (Token token : tokens) {

        if (token.isNumber()) {
            stack.push(token);

        } else {
            Num n1 = (Num) stack.pop();
            Num n2 = (Num) stack.pop();
            Operator op = (Operator) token;

            Num result = n2.operate(op, n1);
            stack.push(result);
        }

    }

    if (stack.size() != 1) { // 棧中最后剩下的不止一個數(shù)，說明表達式有問題
        throw new RuntimeException("錯誤的表達式");
    }

    return (Num) stack.pop();
}

此時我們在 Num 類中定義了一個 operate 方法，用來根據(jù)運算符對兩個數(shù)進行運算：

public static final RoundingMode MODE
        = RoundingMode.HALF_UP;  // 默認對末尾小數(shù)采用 四舍五入

public static final MathContext MATH_CONTEXT
        = new MathContext(6, MODE); // 無限循環(huán)時保留6位有效數(shù)字，末位四舍五入

public Num operate(Operator op, Num other) {
    BigDecimal result = null;

    switch (op.value()) {
        case "+":
            result = value.add(other.value);
            break;
        case "-":
            result = value.subtract(other.value);
            break;
        case "*":
            result = value.multiply(other.value);
            break;
        case "/":
            result = value.divide(other.value, MATH_CONTEXT);
            break;
    }

    if (result == null) {
        throw new RuntimeException(String.format(
                "operate 方法出錯：%s %s %s", value, op.text(), other.value));
    }

    return new Num(result);
}

目前來看一切都很完美 —— 但是我們忽略了一種情況，那就是輸入負數(shù)的情況。而此時存在以下兩種情況：

輸入的表達式開頭是負數(shù)，比如 -1 + 2 * 3，這種情況容易解決，我們只需要在開頭補上一個 0，便能適應(yīng)現(xiàn)在的程序，比如該表達式補上 0 后就成為 0 - 1 + 2 * 3，結(jié)果一致

另一種情況就是表達式中出現(xiàn)負數(shù)了 —— 此時我們需要對負數(shù)進行特殊的標識，比如按照一般情況將負數(shù)使用括號()包圍。所以我們需要補充我們的正則表達式，讓其可以匹配類似于 (-12) 和 (-100.100) 這樣的 Token。

修改之后的 Expression（(-(d*.d+|d+)) 用來匹配負數(shù)）：

public class Expression {

    private static final String REG_EXPR = "s*(((-(d*.d+|d+)))|(d*.d+|d+)|(+|-|*|/)|((|))|([A-Za-z]+(.*)))s*";
    private static final Pattern PATTERN = Pattern.compile(REG_EXPR);

    ...

    private static Token getToken(Matcher matcher) {
        // matcher.group(0) 匹配整個正則，matcher.group(1) 匹配第一個括號
        String m = matcher.group(1);

        if (m != null) {
            if (matcher.group(2) != null) { // 負數(shù)
                // matcher.group(3) 提取形如 (-1.2) 中的 1.2
                return new Num("-" + matcher.group(3));

            } else if (matcher.group(4) != null) { // 正數(shù)
                return new Num(matcher.group(4));

            } else if (matcher.group(5) != null) { // 運算符
                return new Operator(matcher.group(5).charAt(0));

            } else if (matcher.group(6) != null) { // 括號
                return new Bracket(matcher.group(6).charAt(0));

            } else if (matcher.group(7) != null) { // 函數(shù)
                Function function = new Function(matcher.group(7));
                Num num = function.getResult(); // 直接計算出函數(shù)的值作為 Token

                return num;
            }
        }

        throw new RuntimeException("getToken"); // 正則無誤的情況下不會發(fā)生
    }

    ...

}

現(xiàn)在，讓我們來寫一個主類，從命令行獲得輸入并且計算輸入的表達式的值。我們將主類命名為 Launcher：

public class Launcher {

    public static void main(String[] args) throws Exception {

        System.out.println("歡迎使用你的計算器（輸入 e(xit) 退出）");

        try (Reader in = new InputStreamReader(System.in);
                BufferedReader reader = new BufferedReader(in)) {

            String line;
            while (true) {
                System.out.print("> ");
                line = reader.readLine();

                if (null == line
                        || "e".equalsIgnoreCase(line)
                        || "exit".equalsIgnoreCase(line)) {
                    break;
                } else if (line.isEmpty()) {
                    continue;
                }

                try {
                    Expression expr = Expression.of(line);
                    Expression postfixExpr = expr.toPostfixExpr();
                    Num result = postfixExpr.calculate();

                    System.out.println(result);

                } catch (ArithmeticException ex) {
                    System.out.println("運算錯誤：" + ex.getMessage());
                } catch (RuntimeException ex) {
                    System.out.println("運行錯誤：" + ex.getMessage());
                    // ex.printStackTrace(System.err);
                }

            }
        }
    }
}

可以看到，我們已經(jīng)可以成功的解析表達式，并且計算表達式的值（完整的源碼在 GitHub）。

當然，我們總不能每次運行都用 Maven 來運行項目，所以我們把項目打包成 jar，然后寫個腳本來執(zhí)行這個 jar，最后將腳本加入到 PATH 中，那么便可以在命令行下直接調(diào)用。
我們將打包的 jar 命名為 mcalc.jar （打包的配置可參考 pom.xml），然后寫個簡單的腳本。比如，在 Windows 上，寫個 mcalc.bat：

@echo off
:: %~dp0 表示當前批處理文件所在目錄的路徑
set DIR_PATH=%~dp0
java -jar %DIR_PATH%mcalc.jar

然后將 mcalc.bat 和 mcalc.jar 放到同一個文件夾下，然后將這個文件夾的路徑加入到 PATH。此時在命令行中直接輸入 mcalc，便可以進入程序：

參考：

http://blog.csdn.net/antineut...

http://blog.csdn.net/yu757371...