十二、Python簡單數據結構應用（之… · 高中生學編程--Python學習

## 十、Python語言中簡單數據結構的應用（之二） ----From a high schoolstudent's view to learn Python 關鍵字： python 列表堆棧數據結構遞歸調用函數組合問題后綴表達式前綴表達式逆波蘭表達式運算符優先級四、利用堆棧編程實現復雜的四則運算本部分使用堆棧將表達式轉換為后綴表達式，并計算表達式的值，表達式為四則運算表達式。 ***Postfix notation***is an unambiguous way of writing an arithmetic expres- sion withoutparentheses. It is defined so that if“(*exp*1)**op**(*exp*2)”is a normal, fully parenthesized expression whose operation is**op**, the postfix version of this is“*pexp*1*pexp*2**op**”, where*pexp*1is the postfix version of*exp*1and*pexp*2is the postfix version of*exp*2.The postfix version of a sin- gle number or variable is just thatnumber or variable. For example, the postfix version of“((5+2)?(8?3))/4”is “5 2 + 8 3 ??4 /”. Describe a nonrecursiveway of evaluating an expression in postfix notation. 這是《Data Structures andAlgorithms in Python》書中堆棧的一道練習P252. 以下關于后綴表達式的詳細說明(參考baidu) 1、概述不包含括號，[運算符](http://baike.baidu.com/view/425996.htm)放在兩個運算對象的后面，所有的計算按運算符出現的順序，嚴格從左向右進行（不再考慮運算符的優先規則，如：(2+ 1) * 3 ，即2 1 + 3 * 2、計算運用后綴表達式進行計算的具體做法：建立一個棧S 。從左到右讀后綴表達式，如果讀到[操作數](http://baike.baidu.com/view/420846.htm)就將它壓入棧S中，如果讀到n元運算符(即需要參數個數為n的運算符)則取出由棧頂向下的n項按操作符運算，再將運算的結果代替原棧頂的n項，壓入棧S中。如果后綴表達式未讀完，則重復上面過程，最后輸出棧頂的數值則為結束。 3、轉換計算機實現轉換：將中綴表達式轉換為后綴表達式的算法思想： ·開始掃描； ·數字時，加入后綴表達式； ·運算符： 1. 若為 '('，入棧； 1. 若為')'，則依次把棧中的的運算符加入后綴表達式中，直到出現'('，從棧中刪除'(' ； 1. 若為除括號外的其他[運算符](http://baike.baidu.com/view/425996.htm)，當其優先級高于棧頂運算符時，直接入棧。否則從棧頂開始，依次彈出比當前處理的[運算符優先級](http://baike.baidu.com/view/262524.htm)高和優先級相等的運算符，直到一個比它優先級低的或者遇到了一個左括號為止。 ·當掃描的中綴表達式結束時，棧中的的所有運算符[出棧](http://baike.baidu.com/view/346791.htm)； 4、人工實現轉換這里給出一個中綴表達式：a+b*c-(d+e) 第一步：按照[運算符](http://baike.baidu.com/view/425996.htm)的優先級對所有的運算單位加括號：式子變成了：((a+(b*c))-(d+e)) 第二步：轉換前綴與后綴表達式 - 前綴：把運算符號移動到對應的括號前面則變成了：-( +(a *(bc))+(de)) 把括號去掉：-+a*bc+de前綴式子出現 - 后綴：把運算符號移動到對應的括號后面則變成了：((a(bc)* )+ (de)+)- 把括號去掉：abc*+de+-后綴式子出現發現沒有，前綴式，[后綴式](http://baike.baidu.com/view/2973716.htm)是不需要用括號來進行優先級的確定的。如表達式：3+(2-5)*6/3 5、計算機轉換過程詳細說明后綴表達式 ?? ? 棧 3_________________+ 3 ________________+( 3 2_______________+(- 3 2 5 -_____________+ 3 2 5 -_____________+* 3 2 5 - 6 *___________+/ 3 2 5 - 6 *3__________+/ 3 2 5 - 6 *3/+________ ("_____"用于隔開后綴表達式與棧) 遍歷中綴表達式的每個節點，如果： 1）、該節點為[操作數](http://baike.baidu.com/view/420846.htm)：直接拷貝進入后綴表達式 2）、該節點是運算符，分以下幾種情況： A、為“（”[運算符](http://baike.baidu.com/view/425996.htm)：壓入臨時堆棧中 B、為“）”[運算符](http://baike.baidu.com/view/425996.htm)：不斷地彈出臨時堆棧頂部[運算符](http://baike.baidu.com/view/425996.htm)直到頂部的運算符是“（”為止。并把彈出的[運算符](http://baike.baidu.com/view/425996.htm)都添加到后綴表達式中 C、為其他運算符，有以下步驟進行：比較該運算符與臨時棧棧頂指針的運算符的優先級，如果臨時棧棧頂指針的優先級高于該運算符的優先級，彈出并添加到后綴表達式中，反復執行前面的比較工作，直到遇到一個棧頂指針的優先級低于該運算符的優先級，停止彈出添加并把該運算符壓入棧中。此時的比較過程如果出現棧頂的[指針](http://baike.baidu.com/view/159417.htm)為‘（’，則停止循環并把該運算符壓入棧中，注意：‘（’不要彈出來。遍歷完中綴表達式之后，檢查臨時棧，如果還有[運算符](http://baike.baidu.com/view/425996.htm)，則全部彈出，并添加到后綴表達式中。以上描述的部分來自于網上的資料，寫的非常詳細，人工轉換的例子也有。五、使用Python的程序實現。要把下面的仔細看完，還是需要一些耐心的。首先是一些預處理的函數：目的是檢查（）使用是否匹配，有無不合法的字符出現在表達式中： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 32.1px; height: 363.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">123456789101112131415161718192021222324252627282930313233</td><td valign="top" style="width: 375.3px; height: 363.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299"># -*- coding=utf-8 -*- def is_matched(expr):? ? """ReturnTrue if all delimiters are properlymatch;?? ? Falseotherwise."""? ? lefty ='({['? ? righty =')}]'? ? S =[]?? ? for c inexpr:? ?? ? if c inlefty:?? ?? ? ?? S.append(c)? ?? ? elif c inrighty:? ?? ? ?? if len(S) ==0:?? ?? ? ?? ? ? returnFalse? ?? ? ?? if righty.index(c) !=lefty.index(S.pop()):? ?? ? ?? ? ? returnFalse? ? returnlen(S) == 0 def validate (instr):? ? """檢查輸入的表達式，將不合法的字符去掉 """? ? """對于-()以及(-())這樣形式的字符串處理很麻煩，統一轉換為(0-1)* """? ? op ='+-*/()' ? ? ?? ? #合法的運算符? ? digital ='1234567890.'? ? x1 =""? ? for i inrange(len(instr)):? ?? ? if instr[i] in op or instr[i]in digital:? ?? ? ?? x1 = x1 + instr[i]? ? x1 =x1.replace('(-', '((0-1)*')? ? ifx1[0]=='-':? ?? ? x1 = x1.replace('-','(0-1)*', 1)?? ? returnx1 </td></tr></tbody></table> 這個程序本身沒有太多需要解釋的，唯一需要注意的是： line1：# -*- coding=utf-8-*- 這可不是注釋，雖然以#開頭，如果想讓.py文件中使用中文的注釋，而解釋器不報錯的話，必須在文件開頭加入這么一句。同時，如果想print語句顯示中文字符串，必須注意些： print u”中文顯示舉例” 在檢查了表達式字符串的合法行之后，我們就將表達式中的數與運算符分離，按照各自的類型，逐個按照表達式的順序存儲在一個List中，如’123+234’，字符串123、234會被作為兩個整型數保存。程序如下： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 384.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">1234567891011121314151617181920212223242526272829303132</td><td valign="top" style="width: 376.9px; height: 384.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">def separation (x):?? """?? 將表達式進行拆分，拆分的結果存放到一個list中?? 由于list中的元素可以為各種類型，這給我們提供了極大的便利?? 將數字串轉換為int或float型，運算符按字符串存儲?? """?? op = '+-*/()' ?? ? ?? #合法的運算符?? digital = '1234567890.'?? alist = []?? ifrom = 999?? for i in range(len(x)):?? ? ? if x[i] inop:?? ? ?? ? if ifrom ==999:??? ? ?? ? ?? alist.append(x[i])?? ? ?? ? else:?? ? ?? ? ?? if x[i - 1] in digital:?? ? ?? ? ?? ? ? if '.' inx[ifrom:i]:?? ? ?? ? ?? ? ?? ? alist.append( float(x[ifrom:i] ) )?? ? ?? ? ?? ? ?else:?? ? ?? ? ?? ? ?? ? alist.append( int( x[ifrom:i]) )?? ? ?? ? ?? alist.append(x[i])?? ? ?? ? ?? ifrom = 999??? ? ?else:?? ? ?? ? if ifrom==999:?? ? ?? ? ?? ifrom=i??? if ifrom != 999:?? ? ? if '.' inx[ifrom:len(x)]:?? ? ?? ? alist.append( float(x[ifrom:len(x)] ) )?? ? ?else:?? ? ?? ? alist.append( int(x[ifrom:len(x)] ) )?? return alist </td></tr></tbody></table> 最后就是后綴表達式轉換的函數了： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 742.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152</td><td valign="top" style="width: 376.9px; height: 742.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">defsuffix_expression_r(exprinlist):?? alist=[]?? blist=[]?? for i in exprinlist:?? ? ? if type(i)== float or type(i) == int:?? ? ?? ?alist.append(i)? ???? ? ? if type(i)== str:?? ? ?? ? if i=='(':?? ? ?? ? ?? blist.append(i)?? ? ?? ? if i=='+' ori=='-':?? ? ?? ? ?? if len(blist)==0:?? ? ?? ? ?? ? ?blist.append(i)?? ? ?? ? ?? else:?? ? ?? ? ?? ? ? whileTrue:?? ? ?? ? ?? ? ?? ? x=blist.pop()?? ? ?? ? ?? ? ?? ? if x=='+' or x=='-' or x=='*'or x=='/':?? ? ?? ? ?? ? ?? ? ?? alist.append(x)?? ? ?? ? ?? ? ?? ? if x=='(':?? ? ?? ? ?? ? ?? ? ?? blist.append(x)?? ? ?? ? ?? ? ?? ? ?? blist.append(i)?? ? ?? ? ?? ? ?? ? ?? break?? ? ?? ? ?? ? ?? ? if len(blist)==0:?? ? ?? ? ?? ? ?? ? ?? blist.append(i)?? ? ?? ? ?? ? ?? ? ?? break?? ? ?? ? if i=='*' ori=='/':?? ? ?? ? ?? if len(blist)==0:?? ? ?? ? ?? ? ?blist.append(i)?? ? ?? ? ?? else:?? ? ?? ? ?? ? ? whilelen(blist)>0:?? ? ?? ? ?? ? ?? ? x=blist.pop()?? ? ?? ? ?? ? ?? ? if x=='*' orx=='/':?? ? ?? ? ?? ? ?? ? ?? alist.append(x)?? ? ?? ? ?? ? ?? ? ?? blist.append(i)?? ? ?? ? ?? ? ?? ? ?? break?? ? ?? ? ?? ? ?? ? if x=='+' orx=='-':?? ? ?? ? ?? ? ?? ? ?? blist.append(x)?? ? ?? ? ?? ? ?? ? ?? blist.append(i)?? ? ?? ? ?? ? ?? ? ?? break?? ? ?? ? ?? ? ?? ? if x=='(':?? ? ?? ? ?? ? ?? ? ?? blist.append(x)?? ? ?? ? ?? ? ?? ? ?? blist.append(i)?? ? ?? ? ?? ? ?? ? ?? break?? ? ?? ? if i==')':?? ? ?? ? ?? while len(blist)>0:?? ? ?? ? ?? ? ?x=blist.pop()?? ? ?? ? ?? ? ? ifx!='(':?? ? ?? ? ?? ? ?? ? alist.append(x)?? ? ?? ? ?? ? ? ifx=='(':?? ? ?? ? ?? ? ?? ? break??? while len(blist)>0:?? ? ?alist.append(blist.pop())???? return alist </td></tr></tbody></table> 函數的輸入參數是一個使用separation()函數將字符串表達式轉換后的list blist用來模擬存放運算符的堆棧，alist用來存放結果最后要做的是進行計算，前面所有這些都是為了讓計算機知道，哪些是數，哪些是運算操作符，并且將運算符的優先級順序區分出來，等所有這些都做好，其實計算反而是最簡單的事情了，看函數的實現： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 336.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">1234567891011121314151617181920 </td><td valign="top" style="width: 377.4px; height: 336.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">defcalculation(expression):?? list_a=[]??? for i in expression:?? ? ? iftype(i)==float or type(i)==int:?? ? ?? ? list_a.append(i)?? ? ? eliftype(i)==str:?? ? ?? ? x=list_a.pop()?? ? ?? ? y=list_a.pop()?? ? ?? ? if i=='+':?? ? ?? ? ?? result=x+y?? ? ?? ? if i=='-':?? ? ?? ? ?? result=y-x?? ? ?? ? if i=='*':?? ? ?? ? ?? result=x*y?? ? ?? ? if i=='/' andabs(x)>1E-9:?? ? ?? ? ?? result=y/x?? ? ?? ?list_a.append(result)?? ? ?else:?? ? ?? ? return 'Error'?? return result </td></tr></tbody></table> 函數調用方法： <table cellspacing="0" cellpadding="0" style="border-collapse: collapse"><tbody><tr><td valign="top" style="width: 25.1px; height: 156.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 2.2px 1.0px 1.0px; border-color: #000000 #50a299 #000000 #000000">12345678910111213</td><td valign="top" style="width: 377.4px; height: 156.0px; background-color: #ffffff; border-style: solid; border-width: 1.0px 1.0px 1.0px 2.2px; border-color: #000000 #000000 #000000 #50a299">expr ="3+(2-5)*6.0/3"if notis_matched(expr):?? print u"錯誤的表達式！"else:?? temp_x1=validate(expr)?? print(temp_x1)?? expr_list = separation(temp_x1)?? print expr_list?? print suffix_expression_r(expr_list)?? s_expr =suffix_expression_r(expr_list)?? print s_expr?? print expr, ' = ',calculation(s_expr) </td></tr></tbody></table> 顯示的運行結果如下： 3+(2-5)*6.0/3 [3, '+', '(', 2, '-', 5, ')','*', 6.0, '/', 3] [3, 2, 5, '-', 6.0, '*', 3,'/', '+'] 3+(2-5)*6.0/3?= ?-3.0 六、結束語看著、想著都很簡單的事，為什么讓計算機做起來這么復雜呢？甚至都會覺得計算機一點也沒有我之前很智能的感覺了。但是在把這個程序做好之后，你輸入任一的四則運算表達式，不管多長，它都能瞬間的檢查你的表達式是否正確，如果正確的話它也能夠瞬間的給你答案，似乎又智能了。所以，我們應該這么認為：計算機的計算能力是很強大的，關鍵在于我們能夠讓它做什么，這個讓計算機做什么的過程就是編程的過程。我的更多文章： - [Python程序調試的一些體會](http://blog.sina.com.cn/s/blog_d6cca93e0101ewc9.html)(2013-10-06 22:57:35) - [十四、Python編程計算24點（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euxx.html)(2013-10-03 22:18:28) - [十三、Python編程計算24點（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101eukc.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含圖片") (2013-10-02 22:15:46) - [十一、Python簡單數據結構應用（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ep9z.html)(2013-09-23 23:31:49) - [十、Python編程解決組合問題（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101entc.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含圖片") (2013-09-21 23:37:27) - [九、Python編程解決組合問題（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ent7.html)(2013-09-21 23:32:54) - [八、Python的函數編程（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwj.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含視頻") (2013-09-20 23:09:39) - [七、Python的函數編程（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwg.html)![](https://box.kancloud.cn/2015-10-30_5632e1cc04fc3.gif "此博文包含視頻") (2013-09-20 23:09:10) - [六、Python的程序流程](http://blog.sina.com.cn/s/blog_d6cca93e0101ejeg.html)(2013-09-19 16:53:58) - [高中生如何學編程](http://blog.sina.com.cn/s/blog_d6cca93e0101e8fn.html)(2013-09-02 19:26:01)