C++ 表達式求值器實作：詞法分析、遞迴下降語法分析與堆疊計算

建構支援完整運算子優先級、括號巢狀、負號處理的表達式求值引擎。採編譯器前端經典三階段：詞法分析 → 語法分析 (遞迴下降) → 執行階段 (雙堆疊求值)。

支援語法範圍

• 運算子：+ - * / ( )、一元正負號
• 運算元：整數、雙精度浮點數
• 結束符：#
• 範例：-25*(56+15)#

階段一：詞法分析

輸入字元集：{0-9, ., +, -, *, /, (, ), #}
輸出 Token 序列：

輸入: -25*(56+15)#
Token: [-25, *, (, 56, +, 15, ), #]
類型: [NUM, OP, LP, NUM, OP, NUM, RP, END]

階段二：語法分析 (遞迴下降)

文法定義 (消除左遞迴後)

E  → N E' | (E) E'
E' → + E E' | - E E' | * E E' | / E E' | ε

遞迴下降解析器骨架

double ParseE() {  // 解析 E
    double val = ParsePrimary();
    return ParseEPrime(val);
}

double ParsePrimary() {  // N 或 (E)
    if (CurrentToken == NUM) return ConsumeNumber();
    if (CurrentToken == LP) {
        Consume(LP);
        double val = ParseE();
        Expect(RP);
        return val;
    }
    Error("語法錯誤");
}

double ParseEPrime(double left) {  // E'
    while (true) {
        if (CurrentToken == ADD) { Consume(ADD); left += ParsePrimary(); }
        else if (CurrentToken == SUB) { Consume(SUB); left -= ParsePrimary(); }
        else if (CurrentToken == MUL) { Consume(MUL); left *= ParsePrimary(); }
        else if (CurrentToken == DIV) { Consume(DIV); left /= ParsePrimary(); }
        else break;
    }
    return left;
}

完整程式碼包含錯誤處理、Token 串流管理、一元運算子處理。

階段三：堆疊式求值 (Shunting Yard / 運算子優先)

語法分析同時產生後序表示 (RPN) 或直接雙堆疊計算：

• 運算元堆疊：儲存數值
• 運算子堆疊：儲存運算子
• 優先級表：定義運算子間優先關係

核心演算法

while (tokens remain) {
    if (token is number) operandStack.push(token.value);
    else if (token is operator) {
        while (!opStack.empty() && 
               precedence(opStack.top()) >= precedence(token)) {
            ApplyOperator(operandStack, opStack.pop());
        }
        opStack.push(token);
    }
    else if (token == '(') opStack.push(token);
    else if (token == ')') {
        while (opStack.top() != '(') ApplyOperator(...);
        opStack.pop(); // 彈出 '('
    }
}
while (!opStack.empty()) ApplyOperator(...);
return operandStack.top();

關鍵實作細節

• 負號處理：詞法階段識別一元負號 (行首、( 後、運算子後) → 產生負數 Token
• 錯誤恢復：遇錯誤可嘗試跳過至下一個同步點 (分號、右括號)
• 精度控制：內部統一用 `double`，輸出可格式化
• 擴充性：加入函數呼叫、變數、冪運算 ^ 只需擴充文法與優先級表

測試驗證

原始碼下載

完整專案含詞法分析器、遞迴下降解析器、堆疊計算器、測試主程式。