<ol id="afmgz"></ol> 表達(dá)式=0此種方程式求解
牛頓法是求解的核心方法，它的維基百科的定義為：牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。方法使用函數(shù)f(x)的泰勒級數(shù)的前面幾項(xiàng)來尋找方程f(x)=0的根。簡言之，牛頓法就是對x進(jìn)行迭代，直至x收斂于某個(gè)很小的范圍
所以，對于任意的一元函數(shù)，我們都可以嘗試用牛頓法來求得其近似解，當(dāng)誤差小于10^-9時(shí)，或者迭代步數(shù)超過10^5時(shí)，迭代結(jié)束
在構(gòu)建求解器時(shí)，有幾個(gè)關(guān)鍵問題需要解決：解析輸入的表達(dá)式，表達(dá)函數(shù)，求導(dǎo)函數(shù)方程，對函數(shù)進(jìn)行代入求值。其中，最優(yōu)先的一個(gè)問題是：我們怎么儲(chǔ)存（表達(dá)）函數(shù)?
為什么選擇這種二分表達(dá)樹表達(dá)方式？主要是因?yàn)樗菢湫谓Y(jié)構(gòu)，方便遞歸處理節(jié)點(diǎn)，而我們之后求導(dǎo)函數(shù)其實(shí)就是用的遞歸思路，包括代入求值也是遞歸的思路\
預(yù)處理表達(dá)式：首先，我們需要預(yù)處理輸入的表達(dá)式字符串。因?yàn)樵跀?shù)學(xué)中有一些簡略或者多余的寫法需要在此規(guī)范化。自然的輸入串經(jīng)過預(yù)處理后，就應(yīng)該是一個(gè)中綴的表達(dá)式字符串，這是人類能夠自然理解的表達(dá)式形式。但是為了將表達(dá)式儲(chǔ)存成二叉表達(dá)樹，我們還需要將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式
調(diào)度場算法：度場算法基本和我們在棧 遞歸 漢諾塔文中提到的利用棧來計(jì)算表達(dá)式的方法類似。它用隊(duì)列表達(dá)輸出的后綴表達(dá)式，利用了棧來儲(chǔ)存操作符和函數(shù)
構(gòu)建二叉表達(dá)式樹：假設(shè)輸入表達(dá)式為：(a+b) * (c * (d+e))，經(jīng)過調(diào)度場算法，我們得到a b + c d e + * *的后綴表達(dá)式。此時(shí)我們便可以利用后綴表達(dá)式的特點(diǎn)，快速的構(gòu)建出一顆二叉表達(dá)樹來
求值：對二叉表達(dá)樹進(jìn)行代入求值的算法應(yīng)該很容易就能想到。利用二叉樹的遞歸特性，根為操作符或函數(shù)，左子樹右子樹是遞歸定義。我們只需要將左右子樹的值遞歸求出，然后在進(jìn)行操作符運(yùn)算即可
構(gòu)建導(dǎo)函數(shù)樹：我們只剩下了求解導(dǎo)函數(shù)的步驟。這一步也是比較復(fù)雜的操作，因?yàn)閷?dǎo)函數(shù)的規(guī)則實(shí)在是很多。首先，表達(dá)導(dǎo)函數(shù)應(yīng)該用二叉表達(dá)樹來進(jìn)行表示，因?yàn)榭梢灾苯訉ζ溥M(jìn)行代入求值，而且二叉表達(dá)樹具有遞歸的特性；其次，由于二叉表達(dá)樹的根節(jié)點(diǎn)總是操作符或函數(shù)的特性，左右子樹也是表達(dá)式，我們可以用遞歸的思路來求解導(dǎo)函數(shù)