函數繪圖引擎實現（一）：表達式解析、自動求導與語法樹化簡

專案背景

為繪製隱式函數 f(x,y)=0 圖像，需對任意表達式進行語法分析、求導（牛頓迭代法需要導數）、化簡。採用 C# 實現，利用 unsafe 指針解析字符串，構建語法樹（AST），支持常數、變量、二元運算符、函數調用、冪運算。

架構設計

• Expression 抽象基類，派生：NumberExpression、VariableExpression、Add/Sub/Mul/Div/PowerExpression、NegExpression、FunctionExpression（sin, cos, exp, ln 等）。
• Parser：遞歸下降，算符優先級：Exp3 (+,-) → Exp2 (*,/) → Exp1 (^) → Exp0 (原子：數字、變量、函數、括號、一元負號)。
• 求導：每個節點實現 Differentiate(wrt)，應用鏈式法則構建導數樹。
• 化簡：常數摺疊（如 2*3 → 6）、零元素消除（x+0 → x、x*0 → 0）、冪簡化（x^1 → x）等，遞歸自底向上。

核心解析器代碼（關鍵片段）

unsafe static class ExpressionParser {
    static void SkipSpaces(char** input) {
        while (char.IsWhiteSpace(**input)) (*input)++;
    }
    static bool Char(char** input, char c) {
        SkipSpaces(input);
        if (**input == c) { (*input)++; return true; }
        return false;
    }
    static double Number(char** input) { /* 解析數字含小數點 */ }
    static string Name(char** input) { /* 解析標識符 */ }

    static Expression Exp0(char** input) { /* 原子 */ }
    static Expression Exp1(char** input) { /* ^ 右結合 */ }
    static Expression Exp2(char** input) { /* * / 左結合 */ }
    static Expression Exp3(char** input) { /* + - 左結合 */ }

    public static Expression Parse(string s) {
        fixed (char* input = s.Trim())
            return UnsafeParse(input);
    }
}

運行示例與輸出

輸入表達式 → 解析樹 → 重打印 → 化簡樹 → 檢查含 x/y → 對 x/y 求導 → 導數化簡。

input:  x+2*y+4
parse:  ((x + (2 * y)) + 4)
simplified: ((x + (2 * y)) + 4)
contains x: True
contains y: True
dx: ((1 + ((0 * y) + (2 * 0))) + 0)
simplified dx: 1
dy: ((0 + ((0 * y) + (2 * 1))) + 0)
simplified dy: 2

input:  exp(x)/ln(x)
parse:  (exp(x) / ln(x))
dx: ((((exp(x) * 1) * ln(x)) - (exp(x) * (1 / x))) / (ln(x) ^ 2))
simplified dx: (((exp(x) * ln(x)) - (exp(x) * (1 / x))) / (ln(x) ^ 2))
dy: 0

技術亮點

1. unsafe 指針解析：避免字符串 substring 分配，直接指針推進，高性能。
2. 語法樹不可變：解析、求導、化簡均產生新樹，原樹不變，線程安全、易調試。
3. 導數自動構建：無需手寫導數公式，遞歸應用微分規則自動生成導數樹。
4. 化簡器：模式匹配重寫，如 Mul(Zero, _) → Zero、Add(Const, Const) → Const，顯著減小表達式體積。

下一步計劃

• 實現牛頓迭代法：對屏幕每個像素，固定 x 求 y 或固定 y 求 x，用導數樹快速評估迭代。
• 自適應步長、發散檢測、多線程渲染。
• 支持更多函數（三角、雙曲、絕對值、分段）。

總結

本文展示了從字符串到可求導、可化簡語法樹的完整管線。C# unsafe 配合遞歸下降解析器，構建靈活的表達式引擎核心，為後續隱式曲線繪圖（牛頓法收斂點集）奠定基礎。代碼結構清晰，擴展性強，是編譯器前端技術在圖形學中的典型應用。