1.引子

最近做項目的時候抬纸，遇到了一個需求，就是隨機給出一個數(shù)學(xué)公式唐瀑，公式中包含變量隆夯，讓求出公式最終的結(jié)果。譬如這樣的：

NSDictionary *dic = @{@"s1":@"3",@"s2":@"6",@"s3":@"2"};
NSString *description = @"s1 + s1 * (s2 + s1 ) * 2 + (s2 / s3)";{

讓求出 description = 3 + 3(6+3)2+(6/2) = 60

剛開始一頭霧水昂芜，計算機怎么去識別計算公式呢莹规，對著公式發(fā)呆，越看越熟悉泌神，想起來 原來前段時間在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時候見到過良漱，就翻開了書，一切問題都迎刃而解了欢际。不得不佩服前輩們的機智母市。

項目地址在這里 好厲害，可惜不是我寫的,借鑒這位仁兄的傳送門??????

2.解讀

數(shù)學(xué)表達式求值是借助于棧的實現(xiàn)的损趋，俗稱后綴表示法定義患久，也被稱為逆波蘭表示。（因為是20世紀(jì)50年代 波蘭的邏輯學(xué)家想到的 一種不需要括號的后綴表達法 所有的符號都是在要運算數(shù)字的后面出現(xiàn)） 以下為倒推浑槽，皆出自《大話數(shù)據(jù)結(jié)構(gòu)》墙杯，感覺這本書寫的太好了

2.1 后綴表達式計算結(jié)果

對于9+(3-1)*3+10/2,用后綴表示法 應(yīng)該是

9 3 1 - 3 * + 10 2 / +

計算規(guī)則：從左到有遍歷表達式的每個數(shù)字和符號，遇到是數(shù)字就進棧括荡，遇到是符號高镐，就將處于棧頂?shù)膬蓚€數(shù)字出棧，進行計算畸冲，再將運算結(jié)果進棧嫉髓，一直到最終獲得結(jié)果。

• 1. 初始化一個空棧邑闲。此棧用來對要運算的數(shù)字進出使用算行。
• 2. 后綴表達式中前三個都是數(shù)字，所以9苫耸、3州邢、1進棧
     
• 3. 接下來是 - 所以將占中的1出棧作為減數(shù)，3作為被減數(shù)褪子，并將運算3-1得到的2 再進棧
• 4. 接下來是數(shù)字3 進棧
     
• 5. 后面是 * 也就意味著棧中的3和2出棧量淌， 2*3 = 6骗村，將6進棧
• 6. 下面是 + 所以6和9出棧 9+6=15，將15進棧
     
• 7. 接下來是10與2兩個數(shù)字進棧
• 8. 接下來是符號/ 棧頂?shù)?與10出棧呀枢，10/2 = 5,再進棧
     
• 9. 最后一個是符號+ 所以15與5出棧 5+15 = 20
• 10. 結(jié)果是20出棧胚股，棧變?yōu)榭?br>
      
      利用后綴表達法可以很順利解決計算的問題，那么問題來了
      9+(3-1)*3+10/2 是如何轉(zhuǎn)化為 9 3 1 - 3 * + 10 2 / + ,請往下看

2.2 中綴表達式轉(zhuǎn)后綴表達式

我們把平時所用的標(biāo)準(zhǔn)四則運算表達式裙秋，即9+(3-1)*3+10/2叫做中綴表達式琅拌。因為所有的運算符號都在兩數(shù)字的中間，現(xiàn)在的問題就是中綴轉(zhuǎn)后綴了

中綴表達式 `9+(3-1)*3+10/2` 轉(zhuǎn)化為后綴表達式 `9 3 1 - 3 * + 10 2 / + ` 

從左到右遍歷中綴表達式的每個數(shù)字和符號摘刑，若是數(shù)字就輸出进宝，即成為后綴表達式的一部分；若是符號枷恕，則判斷其與棧頂符號的優(yōu)先級党晋，是右括號或優(yōu)先級低于棧頂符號（乘除優(yōu)于加減）則棧頂元素依次出棧并輸出，并將當(dāng)前符號進棧活尊，一直到最終輸出后綴表達式為止

• 1. 初始化一空棧隶校，用來對符號進出棧使用
• 2. 第一個字符是數(shù)字9， 輸出9蛹锰，后面是符號 + 深胳，進棧
     
• 3. 第三個是字符 ( ,依然是符號，因其只是左括號铜犬，還未配對舞终，故進棧
• 4. 第四個是數(shù)字3, 輸出， 表達式為 9 3 ,接著是 -,進棧
     
• 5. 接下來是數(shù)字1癣猾，輸出敛劝，表達式為 9 3 1,后面是符號),此時，我們需要去匹配此前的(,所以棧頂依次出棧纷宇，并輸出夸盟，直到( 出棧為止。
     此時括號上方只有-,因此輸出像捶，表達式變?yōu)?9 3 1 -
• 6. 接著是數(shù)字3,輸出上陕，總的表達式為9 3 1 - 3. 緊接著是符號*，因為此時的棧頂符號為+,優(yōu)先級低于*,所以不輸出拓春，*進棧
     
• 7. 之后是符號+ 此時當(dāng)前棧頂元素*比這個+的優(yōu)先級高释簿，因此棧中元素出棧并輸出（沒有比 '+' 號更低的優(yōu)先級，所以全部出棧）硼莽，總表達式為9 3 1 - 3 * +. 然后將當(dāng)前這個符號+進棧庶溶。 請注意此處的+是中綴式子中的最后一個+。因為此前的都清空了
• 8. 緊接著是數(shù)字10,輸出。 表達式變?yōu)?9 3 1 - 3 * + 10偏螺，后是符號/,所以進棧
     
• 9. 最后一個是數(shù)字2行疏，輸出，總的表達式為9 3 1 - 3 * + 10 2
• 10. 因已到最后砖茸，所以將占中符號全部出棧并輸出最終輸出的結(jié)果為 9 3 1 - 3 * + 10 2 / +
      

3 總結(jié)

從剛才的推導(dǎo)中你會發(fā)現(xiàn)隘擎，要想計算機具有我們常規(guī)的處理邏輯
最重要的就兩步：

1. 將中綴表達式轉(zhuǎn)化為后綴表達式（棧用來進出運算的符號）
2. 將后綴表達式進行運算得出結(jié)果（棧用來進出運算的數(shù)字)