我們知道在計算的時候，運算符的優先級是很關鍵的，如乘除法的優先級要高于加減法，而括號里面的優先級要高于括號外面的優先級。為了表示運算符的優先級，我們先定一個哈希表來表示運算符和其優先級
# value越大 優先級越高symbolDict = {"+":0,"-":0,"*":1,"/":1,"^":2,"(":3,")":3}如果我們要實現一個簡單的計算器，我們就需要正確的處理運算符的優先級。其基本思想就是先完成優先級高的運算，再完成優先級較低的運算。由于優先級較低的運算可能出現在優先級高的運算之前，所以我們用一個棧來保存運算符，當它的優先級大于等于下一個運算符時，將其離棧進行計算。下面介紹中綴表達式和后綴表達式兩種表達式。
中綴表達式就是我們生活中最常用的表達式，運算符在兩個操作數的中間，如result=a+b。對于一個復合的中綴表達式result=a+b*c，通常分步先計算d=b*c，再計算result=a+b。
顧名思義，后綴表達式表示運算符在兩個操作數的后面，如：ab+對應的中綴表達式為a+b。對于復合的后綴表達式abc*+來說，對應的中綴表達式為a+b*c。后綴表達式的優點在于不用考慮運算符的優先級，直接根據表達式就可以從左到右計算出結果。 后綴表達式的求解代碼為：
def cal(back): ''' back 是一個保存后綴表達式的list 如：[1,2,"+",3,"*"] 對應12+3* 即(1+2)*3 ''' # 操作數的棧 numsStack = [] for i in back: # 遍歷到操作數時 將操作數push進棧 if i not in symbolDict.keys(): numsStack.append(i) # 遍歷到運算符時 進行計算 并將計算結果push進棧 else: # 從棧中取出對應兩個操作數 a,b = numsStack.pop(),numsStack.pop() # 進行計算 并將結果push進棧 # 需要注意的是在這里b是第一個操作數而a是第二個操作數 numsStack.append(baseCal(a,b,i)) # 返回結果 return numsStack.pop() 運行結果如下：In [2]: backOut[2]: [1.0, 5.0, 10.0, 8.0, 4.0, 2.0, '-', '/', '-', '*', '+']對應的：1+5*(10-8/(4-2))In [3]: result = cal(back)In [4]: resultOut[4]: 31.0In [5]: 1+5*(10-8/(4-2))Out[5]: 31所以將輸入的中綴表達式轉換成后綴表達式，就可以從左到右計算出結果了。通過比較python自帶的計算器可以看出，我們的程序的結果是正確的。
中綴表達式轉后綴表達式最主要的就是確定表達式的計算過程。后綴表達式和中綴表達式中的操作數的順序是不變的，而運算符則根據優先級進行重新排列，所以當我們在進行轉化的過程中，對于操作數就直接輸出。而對于運算符的操作，我們也需要一個棧來進行保存（因為運算符在兩個操作后面，所以每個運算符都需要進棧進行保存），而棧頂元素出棧的判斷條件就是它的優先級是否比下一個運算符高或與之相等（判斷表達式運算執行的先后順序）。對于括號的操作，遇到”(“時將其push進棧，遇到”)”時，對棧進行輸出，直到輸出為”(“時停止（注：”(“和”)”不輸出）。 具體程序如下：
def midToBack(equation): ''' str equation 輸入的中綴表達式的字符串 ''' # 運算符棧 symbolStack = [] # 操作數 nums = "" # 返回的后綴表達式(list) retval = [] # 從左到右便利equation i = 0 while i<len(equation): # 判斷當前是否為運算符 若不是 繼續讀取操作數 if not symbolDict.has_key(equation[i]): nums+=equation[i] else: # 判斷是否讀取了操作數，主要是帶括號的表達式會連續出現多個運算符 if nums: # 直接輸出操作數 retval.append(float(nums)) nums = "" # 處理當前的運算符 # 如果棧為空，將運算符push進棧 if not symbolStack: symbolStack.append(equation[i]) else: # 處理")"的情況 if equation[i] == ")": while symbolStack and symbolStack[-1]!="(": retval.append(symbolStack.pop()) symbolStack.pop() # 判斷哪些棧中的運算符可以出棧 else: while symbolStack and symbolDict[equation[i]]<=symbolDict[symbolStack[-1]]: if symbolStack[-1] == "(": break retval.append(symbolStack.pop()) symbolStack.append(equation[i]) i += 1 # 將剩余的操作數和運算符輸出 if nums: retval.append(float(nums)) while symbolStack: retval.append(symbolStack.pop()) return retval運行結果如下：
In [1]: back = midToBack("1+5*(10-8/(4-2))")1+5*(10-8/(4-2))In [2]: backOut[2]: [1.0, 5.0, 10.0, 8.0, 4.0, 2.0, '-', '/', '-', '*', '+']新聞熱點
疑難解答
