中綴表達式轉後綴（逆波蘭）表達式：棧算法完整 C++ 實現

算法原理（雙棧法）

• S1（運算符棧）：初始放入最低優先級 #，表達式以 # 結尾
• S2（輸出棧）：存儲後綴表達式

處理規則

1. 操作數：直接入 S2
2. 運算符：與 S1 棧頂比較優先級
   • 優先級高 → 入 S1
   • 優先級 ≤ 棧頂 → 棧頂彈出入 S2，重複比較
3. 左括號 (：直接入 S1
4. 右括號 )：彈出 S1 至遇到 (，棄掉括號
5. 結束符 #：彈出 S1 所有運算符入 S2
6. 最終 S2 逆序即為後綴表達式

優先級定義表

左優先級用於棧內元素，右優先級用於輸入元素。相等時彈出（左結合）。

完整 C++ 實現

#include <iostream>
using namespace std;
#define MaxSize 100
#define MaxOp 7

struct OpInfo { char ch; int pri; };
OpInfo lpri[MaxOp] = {{'=',0},{'(',1},{'*',5},{'/',5},{'+',3},{'-',3},{')',6}};
OpInfo rpri[MaxOp] = {{'=',0},{'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}};

int leftpri(char op)  { for(int i=0;i> exp;
    trans(exp, postexp);
    cout << "後綴: " << postexp << endl;
    cout << "結果: " << calculate(postexp) << endl;
    return 0;
}

測試示例

輸入: 3+4*2/(1-5)
後綴: 3#4#2#*1#5#-/#+
結果: 1

工程應用提示

• 生產環境建議使用 std::stack、std::string、std::stod
• 支援一元運算符、函數調用、變量需擴展詞法分析器
• 表達式求值引擎可嵌入腳本系統、配置解析、計算器應用

雙棧法是編譯原理、解析器構建的基石算法，值得徹底掌握。