C++ 從後綴表達式構建表達式樹：算法詳解與完整實現

表達式樹是編譯器前端、計算器引擎、符號計算系統的核心資料結構。本文深度解析從後綴表達式（逆波蘭表示法）構建表達式樹的堆疊算法，提供完整 C++ 實現，並延伸討論樹的三種遍歷與表達式求值關係、編譯器應用場景、錯誤處理與擴展方向。

一、樹的三種遍歷與表達式表示對應關係

以表達式 (A + B) * (C + D) 為例，其表達式樹：

關鍵洞察

• 後綴表達式**無需括號**即可唯一確定運算順序，適合機器求值
• 後序遍歷天然生成後綴表達式，堆疊機器直接執行
• 編譯器前端常將中綴→後綴（Shunting-yard 算法）→構建語法樹

二、後綴表達式構建表達式樹算法

算法步驟

1. 掃描後綴表達式每個 token（運算元/運算符）
2. 若為**運算元**（變數/常數）：創建節點，壓入堆疊
3. 若為**運算符**（+ - * / 等）：
   1. 彈出堆疊頂節點 → 作為**右子樹**
   2. 再次彈出堆疊頂節點 → 作為**左子樹**
   3. 創建運算符節點，左右子樹連接
   4. 將新節點壓回堆疊
4. 掃描結束，堆疊頂元素即為表達式樹根節點

示例演示：a b + c d e + * *

Token: a      Stack: [a]
Token: b      Stack: [a, b]
Token: +      Pop b, a → New(+) left=a, right=b → Push [+]
Token: c      Stack: [+, c]
Token: d      Stack: [+, c, d]
Token: e      Stack: [+, c, d, e]
Token: +      Pop e, d → New(+) left=d, right=e → Push [+, +]
Token: *      Pop +, c → New(*) left=c, right=+ → Push [+, *]
Token: *      Pop *, + → New(*) left=+, right=* → Push [*]  ← 根節點

三、C++ 完整實現

節點定義

struct TreeNode {
    char data;           // 運算元或運算符
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(char ch) : data(ch), left(nullptr), right(nullptr) {}
};

構建函數

TreeNode* buildExpressionTree(const string& postfix) {
    stack<TreeNode*> st;
    
    for (char ch : postfix) {
        if (isspace(ch)) continue;  // 跳過空白
        
        TreeNode* node = new TreeNode(ch);
        
        if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            // 運算符：彈出兩個運算元
            if (st.size() < 2) {
                throw runtime_error("Invalid postfix: insufficient operands");
            }
            TreeNode* right = st.top(); st.pop();
            TreeNode* left  = st.top(); st.pop();
            
            node->left = left;
            node->right = right;
            st.push(node);
        } else {
            // 運算元：直接壓入
            st.push(node);
        }
    }
    
    if (st.size() != 1) {
        throw runtime_error("Invalid postfix: extra operands remain");
    }
    return st.top();
}

釋放樹記憶體

void deleteTree(TreeNode* root) {
    if (root) {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
}

驗證：三種遍歷輸出

void preorder(TreeNode* root) {
    if (root) {
        cout << root->data << ' ';
        preorder(root->left);
        preorder(root->right);
    }
}

void inorder(TreeNode* root) {
    if (root) {
        bool isOp = (root->data == '+' || root->data == '-' || 
                     root->data == '*' || root->data == '/');
        if (isOp) cout << '(';
        inorder(root->left);
        cout << root->data << ' ';
        inorder(root->right);
        if (isOp) cout << ')';
    }
}

void postorder(TreeNode* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        cout << root->data << ' ';
    }
}

四、表達式樹求值（遞歸評估）

double evaluate(TreeNode* root, const unordered_map<char, double>& vars) {
    if (!root) return 0;
    
    char ch = root->data;
    if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
        double left = evaluate(root->left, vars);
        double right = evaluate(root->right, vars);
        switch (ch) {
            case '+': return left + right;
            case '-': return left - right;
            case '*': return left * right;
            case '/': return right != 0 ? left / right : throw runtime_error("Divide by zero");
        }
    } else if (isdigit(ch)) {
        return ch - '0';  // 單位數常數
    } else {
        auto it = vars.find(ch);
        return (it != vars.end()) ? it->second : 0;  // 變數查找
    }
    return 0;
}

五、完整測試程式

int main() {
    string postfix = "ab+cde+**";  // (a+b)*(c*(d+e))
    
    try {
        TreeNode* root = buildExpressionTree(postfix);
        
        cout << "前序: "; preorder(root); cout << endl;
        cout << "中序: "; inorder(root); cout << endl;
        cout << "後序: "; postorder(root); cout << endl;
        
        // 求值測試
        unordered_map<char, double> vars = {{'a',2}, {'b',3}, {'c',4}, {'d',5}, {'e',6}};
        // (2+3) * (4 * (5+6)) = 5 * 44 = 220
        double result = evaluate(root, vars);
        cout << "計算結果: " << result << endl;
        
        deleteTree(root);
    } catch (const exception& e) {
        cerr << "錯誤: " << e.what() << endl;
    }
    return 0;
}

六、工程擴展與生產級考量

1. 多字元 Token 支援

// 使用 string token 而非 char
vector<string> tokenize(const string& expr) {
    // 處理多位數、變數名、浮點數、函數名等
    // 正則或狀態機分割
}

2. 運算符優先級與結合性擴展

3. 錯誤處理增強

• 語法錯誤：運算元不足、運算符不足、棧殘留多餘節點
• 語義錯誤：除零、變數未定義、型別不匹配
• 位置追蹤：Token 記錄行列號，錯誤訊息定位源碼位置

4. 訪問者模式分離操作

class TreeVisitor {
public:
    virtual void visit(TreeNode* node) = 0;
    virtual ~TreeVisitor() = default;
};

void traverse(TreeNode* root, TreeVisitor* visitor) {
    if (root) {
        traverse(root->left, visitor);
        traverse(root->right, visitor);
        visitor->visit(root);  // 後序訪問
    }
}

// 具體訪問者：求值器、代碼生成器、優化器、打印器

5. 編譯器實際應用流程

1. 詞法分析：源碼 → Token 流
2. 語法分析：Token 流 → AST（抽象語法樹），表達式子樹即表達式樹
3. 語義分析：型別檢查、符號表建立
4. 中間代碼生成：AST → IR（三地址碼/SSA）
5. 優化：常量折疊、公共子表達式消除、循環不變量外提
6. 目標代碼生成：IR → 機器碼/位元組碼

七、面試高頻變體題

1. 中綴轉後綴：Dijkstra Shunting-yard 算法，堆疊管理運算符優先級
2. 後綴表達式求值：單堆疊，運算元入棧，運算符彈二推一
3. 表達式樹轉中綴：中序遍歷加括號，或最小括號規則
4. 常量折疊優化：遍歷樹，子樹全為常數則預計算替換為常數節點
5. 公共子表達式消除：哈希子樹結構，重複子樹共享節點（DAG 化）

八、總結

從後綴表達式構建表達式樹是「堆疊 + 樹」雙重經典資料結構的完美結合。本文提供的算法邏輯清晰、代碼完整可編譯、錯誤處理完善，並延伸至求值、遍歷、編譯器應用等實戰場景。掌握此技術不僅能應對面試高頻題，更能深入理解編譯器前端、解釋器引擎、符號計算系統的核心運作機制。建議進一步實現：

1. 完整的中綴→後綴→樹→求值管線
2. 支援函數調用、陣列索引、結構體成員訪問的擴展節點類型
3. 基於訪問者模式的優化器（常量傳播、死代碼消除、代數簡化）
4. 目標代碼生成器（x86/ARM/VM 位元組碼）

表達式樹是連接高級語言語義與機器執行邏輯的關鍵橋樑，深入鑽研將受益匪淺。