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

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

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

以后綴表達(dá)式為例：

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

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

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

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

所以可見計(jì)算后綴表達(dá)式非常容易編碼。

由 上一篇 文章可知，我們目前的 Expression 類所表示的，就是中綴表達(dá)式，所以我們需要提供算法，將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式或者后綴表達(dá)式，從而方便我們計(jì)算表達(dá)式的值。當(dāng)然，算法的流程，我們的計(jì)算機(jī)先輩們?cè)缇拖氤鰜砹?，而我們只需要做出?shí)現(xiàn)即可。

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

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

從左往右掃描中綴表達(dá)式：

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

遇到運(yùn)算符 op 時(shí)

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

遇到括號(hào)時(shí)

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

將 S 中的剩余運(yùn)算符依次彈出并加入 L

此時(shí) L 中的所有的 Token 按順序即為后綴表達(dá)式

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

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

/**
 * 獲得該表達(dá)式的后綴形式
 *
 * @return 后綴表達(dá)式
 */
public Expression toPostfixExpr() {
    ArrayDeque S = new ArrayDeque<>(); // 運(yùn)算符棧
    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()) { // 運(yùn)算符棧為空
                        S.push(op);

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

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

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

                        } else { // op 的優(yōu)先級(jí)小于運(yùn)算符棧棧頂元素的優(yōu)先級(jí)
                            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 表示該表達(dá)式為后綴表達(dá)式
}

此時(shí)我們往 Expression 中添加了一個(gè) boolean 字段 postfix，用來標(biāo)識(shí)該表達(dá)式是否為后綴表達(dá)式，postfix 默認(rèn)為 false，如果為 true 則表明該表達(dá)式是后綴表達(dá)式。

public class Expression {
    ...

    private final List tokens; // 該表達(dá)式中的所有 Token
    private final boolean postfix;    // 該表達(dá)式是否為后綴表達(dá)式的標(biāo)識(shí)

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

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

    ...
}

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

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

    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) { // 棧中最后剩下的不止一個(gè)數(shù)，說明表達(dá)式有問題
        throw new RuntimeException("錯(cuò)誤的表達(dá)式");
    }

    return (Num) stack.pop();
}

此時(shí)我們?cè)?Num 類中定義了一個(gè) operate 方法，用來根據(jù)運(yùn)算符對(duì)兩個(gè)數(shù)進(jìn)行運(yùn)算：

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

public static final MathContext MATH_CONTEXT
        = new MathContext(6, MODE); // 無限循環(huán)時(shí)保留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 方法出錯(cuò)：%s %s %s", value, op.text(), other.value));
    }

    return new Num(result);
}

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

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

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

修改之后的 Expression（(-(d*.d+|d+)) 用來匹配負(fù)數(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) 匹配整個(gè)正則，matcher.group(1) 匹配第一個(gè)括號(hào)
        String m = matcher.group(1);

        if (m != null) {
            if (matcher.group(2) != null) { // 負(fù)數(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) { // 運(yùn)算符
                return new Operator(matcher.group(5).charAt(0));

            } else if (matcher.group(6) != null) { // 括號(hào)
                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(); // 直接計(jì)算出函數(shù)的值作為 Token

                return num;
            }
        }

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

    ...

}

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

public class Launcher {

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

        System.out.println("歡迎使用你的計(jì)算器（輸入 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("運(yùn)算錯(cuò)誤：" + ex.getMessage());
                } catch (RuntimeException ex) {
                    System.out.println("運(yùn)行錯(cuò)誤：" + ex.getMessage());
                    // ex.printStackTrace(System.err);
                }

            }
        }
    }
}

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

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

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

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

參考：

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

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