在學(xué)習(xí)《算法4》得過程中，被這個(gè)雙棧算法表達(dá)式求值吸引了够坐，畢竟是獲得過圖靈獎(jiǎng)得老爺子寸宵。
算法原理：
表達(dá)式由括號(hào)、運(yùn)算符合操作數(shù)（數(shù)字）組成元咙。我們根據(jù)以下4種情況從左到右逐個(gè)將這些實(shí)數(shù)送入棧處理：
將操作數(shù)壓入操作數(shù)棧梯影；
將運(yùn)算符壓入運(yùn)算符棧；
忽略左括號(hào)庶香；
在遇到右括號(hào)時(shí)甲棍，彈出一個(gè)運(yùn)算符，彈出所需數(shù)量的操作數(shù)赶掖，并將運(yùn)算符和操作數(shù)的運(yùn)算結(jié)果壓入操作數(shù)棧感猛。
在處理完最后一個(gè)右括號(hào)之后，操作數(shù)棧上只會(huì)有一個(gè)值奢赂，它就是表達(dá)式陪白。這種方法乍一看有些難以理解，但要證明它能夠計(jì)算得到正確的值很簡單：每當(dāng)算法遇到一個(gè)被括號(hào)包圍并由一個(gè)運(yùn)算符和兩個(gè)操作數(shù)組成的子表達(dá)式時(shí)膳灶，它都將運(yùn)算符和操作室的計(jì)算結(jié)果壓入操作數(shù)棧咱士。這樣的結(jié)果就好像在輸入中用這個(gè)值代替了該子表達(dá)式，因此用這個(gè)值代替子表達(dá)式得到的結(jié)果和原表達(dá)式相同。我們可以反復(fù)應(yīng)用這個(gè)規(guī)律并得到一個(gè)最終值序厉。
算法表示
這段代碼是一個(gè)簡單的“解釋器”：一個(gè)能夠解釋給定字符串所表達(dá)的運(yùn)算并計(jì)算得到結(jié)果的程序锐膜。
算法的運(yùn)行軌跡圖
以式子（1+（（2+3）*（4+5）））為例，下面展示一下該算法運(yùn)行時(shí)的軌跡圖：
