在某些情況下，我們需要對輸入字符串表達式進行計算栈妆，例如一個字符串為：“1 + 2 * 3”胁编，我們需要計算出它的結(jié)果，在這里鳞尔，我提供李春葆老師書中所寫的《數(shù)據(jù)結(jié)構(gòu)教程》里的算法嬉橙，這種算法精密之處讓我驚嘆，特此分享寥假。
首先這個表達式只允許存在加減乘除和括號市框，但這也足夠復(fù)雜了。
計算機是無法識別加減乘除的優(yōu)先計算順序的糕韧，更何況還有括號枫振，這是更難以解決的。這時候必須修改這個表達式萤彩，使計算機能夠明白它的計算順序粪滤，其實很簡單，提供一個后綴表達式就行雀扶，什么是后綴表達式额衙，把上面“1 + 2 * 3”改為后綴表達式就是“2 3 * 1 +”，這樣可以利用一個簡單的算法就可以算出結(jié)果，這也就是把先需要計算的數(shù)據(jù)和運算符排在前面窍侧，后需要計算的數(shù)據(jù)和運算符排在后面县踢。
怎么實現(xiàn)這個后綴表達式呢？這就是需要棧的應(yīng)用伟件。
我們首先創(chuàng)建一個棧硼啤，稱這個棧為“運算棧”吧斧账，壓棧一個“=”谴返，我們?nèi)∵@個“=”為0優(yōu)先級（也就是最低優(yōu)先級）。從字符串表達式中提取數(shù)據(jù)咧织，如果是計算數(shù)據(jù)嗓袱，則放在另一個表達式中（用來構(gòu)成后綴表達式），每當(dāng)遇到運算符的時候习绢，就和左運算棧的棧頂運算符的優(yōu)先級進行比較渠抹，如果外運算符（為了分別運算棧里的運算符，我稱外面的運算符為外運算符）的優(yōu)先級較高闪萄，這樣就把這個外運算符壓進運算棧中梧却，相反如果外運算符的優(yōu)先級較低，這樣就把內(nèi)運算符出棧败去，并將添加在上面說的后綴表達式中放航，最后，如果遍歷完字符串表達式后圆裕，將運算棧的所有運算符出棧广鳍，添加在后綴表達式中，當(dāng)然吓妆，“=”是不添加的赊时。利用棧后進先出的特性，這樣就把低優(yōu)先級的運算符排在后面啦耿战。
這里有兩個問題：
1.如果遇到相等運算優(yōu)先級的怎么辦蛋叼，如“+”遇到“+"或者“+”遇到“-”；
2.括號的優(yōu)先級怎么處理剂陡。
首先解決第一個問題狈涮，遇到相等優(yōu)先級的怎么辦。我們知到鸭栖，在現(xiàn)實中歌馍，相等優(yōu)先級的運算符，誰在前面就誰先算晕鹊，而在這里表現(xiàn)的是在運算棧里的運算符要先算松却，也就是暴浦，遇到相同優(yōu)先級的運算符要將棧內(nèi)運算符出棧添加在后綴表達式中，然后再將外運算符對棧頂?shù)倪\算符進行優(yōu)先級比較晓锻。這樣也就解決了第一個問題歌焦。
第二個問題為括號的優(yōu)先級要怎么處理。在現(xiàn)實計算中砚哆，括號里面的運算符都是要首先計算独撇，這應(yīng)該怎么處理呢，在李老師的書中提出了一個解決方法躁锁，讓括號的優(yōu)先級變化纷铣，讓它在外運算符的優(yōu)先級和在棧內(nèi)的優(yōu)先級不一樣。我在這里詳細的說一下战转，括號有左括號和右括號搜立。當(dāng)左括號在外運算符時，它的優(yōu)先級必須最高槐秧，因為括號內(nèi)的數(shù)據(jù)計算要隔離開外面的啄踊，這樣，左括號在外運算符的優(yōu)先級最高時色鸳，它就將會壓棧社痛，這樣就和外面的運算符隔離開了见转。而左括號進入運算符后命雀，它的優(yōu)先級必須最低，這是因為如果保持最高優(yōu)先級斩箫，這樣另外的運算符跟它比較時吏砂，就無法入棧，只有最低優(yōu)先級乘客，才能保證括號內(nèi)的運算符都能經(jīng)過運算棧的處理狐血。當(dāng)右括號在外運算符的時候，它的優(yōu)先級必須最低易核，這樣就可以把經(jīng)過運算棧處理過的運算符都能添加到后綴表達式中匈织，當(dāng)它跟運算棧內(nèi)的左括號比較時，兩個運算符都是最低優(yōu)先級牡直，這就尷尬了缀匕。我們在這里的處理應(yīng)該是將左括號和右括號都拋棄掉，讓它不存在在棧內(nèi)和后綴表達式中碰逸，這樣就和第一個問題的解決方法沖突了乡小，因為在第一個問題解決方法中，相同優(yōu)先級的運算符是應(yīng)該講運算棧內(nèi)的運算符添加進后綴表達式饵史，而外運算符和運算棧內(nèi)的棧頂運算符比較满钟。在這里胜榔，為了合理解決兩個問題的方法，只有降低某些外運算符的優(yōu)先級湃番，這樣外運算符的優(yōu)先級低于運算棧內(nèi)的運算符夭织，可以使運算棧內(nèi)的運算符添加進后綴表達式，但運算棧內(nèi)左括號運算優(yōu)先級應(yīng)該和外運算符中的右括號優(yōu)先級一樣吠撮，這樣就可以使兩個優(yōu)先級相同的左括號和右括號被拋棄摔癣。下面是李老師書中提供的運算符優(yōu)先級：
運算符 ? ? ? ? ? ? ? = ? ? ? ? ? ? （ ? ? ? ? ? ? ? + ? ? ? ? ? - ? ? ? ? ?* ? ? ? ? / ? ? ? ? ?）
內(nèi)運算符 ? ? ? ? ? ?0 ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? 3 ? ? ? ? ? ?3 ? ? ? ? 5 ? ? ? ? 5 ? ? ? ? 6
外運算符 ? ? ? ? ? ?0 ? ? ? ? ? ? ? 6 ? ? ? ? ? ? ? ?2 ? ? ? ? ? ?2 ? ? ? ? 4 ? ? ? ? ?4 ? ? ? ?1
提供一個偽算法：
ch為字符串表達式中的字符。
while（ch != 0）
{
? ? ? ?if(ch為運算數(shù)據(jù))
? ? ? {
? ? ? ? ? ? ? ? ?while ( ch為運算數(shù)據(jù))
? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? 將ch添加進后綴表達式纬向；?
? ? ? ? ? ? ? ? ? ? ? ? ?ch++择浊；
? ? ? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ? ? else
? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? switch(ch和運算棧的棧頂運算符優(yōu)先級)
? ? ? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? ? case ?小 ：將ch壓進運算棧中；
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ch++逾条；
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? break琢岩；
? ? ? ? ? ? ? ? ? ? ? ? ? case 相等：將外運算符和棧頂運算符都拋棄掉；
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ch++师脂；
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?break担孔；
? ? ? ? ? ? ? ? ? ? ? ? ? ?case ?大：棧頂運算符添加進后綴表達式；
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?break吃警；
? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
}最后將棧中的所有運算符出棧添加在后綴表達式中糕篇，‘=’不用添加。
這篇文章的Demo ?
