數據結構實戰：C語言棧實現表達式求值(中綴轉後綴/表達式樹)

棧實現表達式求值：兩種經典算法與完整 C 實現

利用棧結構實現算術表達式計算，展示運算符優先級解析與兩棧協作的兩種核心思路，附完整可運行代碼。

核心數據結構

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

typedef int SElemType;
typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

思路一：操作數棧 + 運算符棧 (雙棧法)

算法流程：

1. 初始化運算符棧 OPTR，壓入 # 作為界限
2. 讀取字符：
3. 操作數 → 壓入操作數棧 OPND
4. 運算符 → 比較棧頂優先級 Precede()：
   • <：運算符入棧
   • =：脫括號，彈出 (
   • >：彈出運算符與兩操作數，計算，結果入 OPND
5. 遇 # 且棧頂 # 結束，OPND 棧頂為結果

優先級判定表

SElemType Precede(SElemType top, SElemType curr) {
    // 返回 '<', '>', '='
    // 實現運算符優先級邏輯：*/ > +-，括號最高
}

思路二：中綴轉後綴再求值 (經典編譯原理)

C++ 版本核心：

// 運算符優先級矩陣
unsigned char Prior[8][8] = { ... };

float EvaluateExpression(char* expr) {
    StackChar *OPTR = NULL;
    StackFloat *OPND = NULL;
    // 掃描表達式字符
    // 數字解析入 OPND
    // 運算符按優先級矩陣處理
    // 遇 # 結束
    return OPND->f;
}

關鍵函數

• In(c)：判斷是否運算符
• Operate(a, op, b)：執行二元運算
• Push/Pop：棧操作

測試用例

輸入: 3*(7-5)#
輸出: 6

算法對比

工程化建議

• 錯誤處理：除零、括號不匹配、非法字符
• 支援浮點數、負數、函數調用
• 詞法分析器分離數字解析邏輯
• 遞歸下降解析器替代優先級矩陣

表達式求值是棧應用的教科書級案例，深度理解其機制有助於掌握編譯器前端核心技術。