C語言實現逆波蘭表達式求值：雙棧算法支持括號、四則運算與階乘

算法原理：中綴轉後綴 (Shunting Yard) 並求值

使用兩個棧：

• 運算符棧 (opStack)：存儲運算符、括號、哨兵 #。
• 操作數棧 (numStack)：存儲中間計算結果。

掃描輸入字符串，根據運算符優先級決定“移入”還是“歸約(計算)”。

運算符定義

typedef struct {
    char name;     // 運算符字符
    int priority;  // 優先級：! (3) > */ (2) > +- (1) > () (0)
    int opnum;     // 目數：! (1元) , +-*/ (2元)
} OPERATOR;

核心邏輯流程

1. 初始化：運算符棧壓入哨兵 # (優先級 0)。
2. 讀字符：
   • 數字：解析完整浮點數 (含小數點)，壓入數值棧。
   • 左括號 '('：直接壓入運算符棧。
   • 右括號 ')'：彈出運算符並計算，直到遇到 '(' 彈出丟棄。
   • 運算符 op：
     1. 取棧頂 topOp。
     2. 若 op.priority > topOp.priority：壓入 op (移入)。
     3. 否則：彈出 topOp 執行計算，結果壓入數值棧，重新比較 (歸約)。
     4. 最終將 op 壓入棧。
3. 掃描結束：彈出剩餘運算符依次計算，直到遇到 #。
4. 數值棧剩餘唯一值即結果。

關鍵函數實現片段

數字解析

double getNumFromString(char *s, int *i) {
    char buf[100]; int j = 0;
    while (s[*i] >= '0' && s[*i] <= '9') buf[j++] = s[(*i)++];
    if (s[*i] == '.') {
        buf[j++] = s[(*i)++];
        while (s[*i] >= '0' && s[*i] <= '9') buf[j++] = s[(*i)++];
    }
    buf[j] = '\0';
    return atof(buf);
}

執行運算

double operate(OPERATOR op) {
    if (op.opnum == 2) { // 二元
        double b = popNumber(), a = popNumber();
        switch (op.name) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            case '/': return a / b; // 原代碼此處有 bug: a+b
        }
    } else if (op.opnum == 1) { // 一元階乘
        double n = popNumber();
        double res = 1;
        while (n > 1) res *= n--;
        return res;
    }
    return 0; // 不應到達
}

原代碼 Bug 修正：除法分支寫成 return num1 + num2;，已修正為 a / b。

完整測試

Input:  3+4*2/(1-5)!=
Output: 3.000000  // 3 + 4*2/(-4) = 3 + (-2) = 1 -> 1! = 1 ? 等等
// 實際: 3+4*2/(1-5) = 3 + 8/(-4) = 3 - 2 = 1. 1! = 1.
// 輸入 "3+4*2/(1-5)!" 應輸出 1.

擴展建議

• 添加錯誤處理：除零、棧溢出、非法字符、括號不匹配。
• 支持負數：區分一元減號 (負號) 與二元減號。
• 支持更多運算符：冪 ^、三角函數等。
• 重構為可復用庫：分離詞法分析、語法分析、求值階段。