用 C# 設計四則運算解釋器（五）——AST 插入運算子規則與優先權處理

核心法則：AST 運算子插入規則

透過前四篇分析，歸納出關鍵規則：

當插入新運算子到 AST 樹時，若樹根為運算子且優先權相同、結合性為左至右，新運算子將成為新樹根，原樹變為新樹的左子樹。

啟發式規則驅動開發

整個解釋器開發遵循「啟發式」原理：將解釋過程分解為一條條明確規則，任務是找出所有規則並盡可能完善。

優先權差異情況：1 + 2 * 3

當插入優先權較高的 * 運算子：

• * 必須移至右子樹並成為右子樹根節點
• 原右子樹 (2) 成為新右子樹的左子樹
• 結果樹結構正確反映「先乘後加」語意

運算子插入核心代碼實作

if (token is OpToken) 
{
    // 情況 1：樹根為運算子且右子樹為空 → 語法錯誤 (如 "1 + +")
    if (root.Token is OpToken && root.RightChild == null) 
    {
        throw new ParseFailureException(
            "The expression '{0} {1}' is not a valid arithmetic expression.",
            root.Token.ToString(), token.ToString());
    }

    // 情況 2：樹根為數值 → 新運算子成為新根，原根變左子樹
    if (root.Token is NumToken) 
    {
        Syntax newRoot = new Syntax(token);
        newRoot.LeftChild = root;
        root = newRoot;
        return newRoot;
    }

    // 情況 3：樹根為運算子 → 比較優先權
    if (root.Token is OpToken) 
    {
        OpToken token1 = (OpToken)token;      // 新運算子
        OpToken token2 = (OpToken)root.Token; // 當前根運算子

        // 新運算子優先權 <= 根運算子 (同級或較低)
        // 如: 1 + 2 + 3 或 1 * 2 + 3
        if (token1.Priority <= token2.Priority) 
        {
            Syntax newRoot = new Syntax(token1);
            newRoot.LeftChild = root;
            root = newRoot;
            return newRoot;
        }

        // 新運算子優先權 > 根運算子 (如 1 + 2 * 3)
        if (token1.Priority > token2.Priority) 
        {
            // 遞迴插入至右子樹
            root.RightChild = Append(root.RightChild, token);
            return root;
        }
    }
}

關鍵設計決策對照

下一步

完成 AST 建構後，下階段將實作 樹的遍歷評估 (Evaluate)，遞迴計算子樹並回傳最終結果，同時處理除零、溢位等執行期錯誤。