從本節開始，刪除原版的英文，直接發譯后的文稿。

后綴表達式求值

棧的最一個應用例子，計算一個后綴表達式的值。這個例子中仍然用棧的數據結構。不過，當掃描表達式的時候，這次是操作數壓棧等待，不是轉換算法中那樣讓操作符等待。另一條思路是，無論何時看到輸入一個操作符，最近的兩個操作數就是操作對象。

為了說清楚一點，考慮表達式4 5 6 * +。從左到右掃描時，首先得到4和5，不過此時，并不知道怎樣處理這兩個數，直到看到后面的操作符。所以要把這兩個數先壓棧，得到操作符以后再出棧。

這個例子中，下一個符號仍然是操作數，所以照舊壓棧，并檢查下一個。現在看到操作符*，這意味著最近兩個操作數要用來做乘法。出棧兩次，得到兩個操作數并相乘(在本例中是結果是30)

這個計算結果要壓回到棧內，并作為下一個操作符的對象。當最后一個操作符工作結束，棧內應該只有一個數值，出棧并作為計算結果返回。圖10顯示了這個求值過程中，棧內容的變化。

圖11顯示了一個稍微復雜的表達式求值過程。7 8 + 3 2 + /。這個例子中有兩點要注意。第一，棧的大小，隨著子表達式的計算過程而膨脹，收縮，再膨脹。第二，除法操作符要小心處理，因為后綴表達式的操作數順序不變，但當兩個操作數出棧時，順序反了。因為除法不支持交換律，所以15/5與5/15不同，必須保證順序沒有交錯。

算法假定后綴表達式是一系列被空格分隔的字符，操作符是* /+ -，操作數假定是一位整數。最終結果也是整數。

1

建立一個空棧，operandStack

2

字符串使用split轉為列表

3

從左到右檢索列表

如果是操作數，字符轉為整數，壓棧

如果是操作符，出棧兩次。第一次出棧的是第二個操作數，第二次出棧的是第一個操作數。計算結果，并壓回棧。

4

檢索結束，出棧結果就是返回值。

完整的函數代碼如下，其中的doMath是算法輔助函數，定義為兩個操作數和一個操作符的計算。

from pythonds.basic.stack import Stack

def postfixEval(postfixExpr):

operandStack = Stack()

tokenList =postfixExpr.split()

for token in tokenList:

if token in"0123456789":

operandStack.push(int(token))

else:

operand2 =operandStack.pop()

operand1 =operandStack.pop()

result =doMath(token,operand1,operand2)

operandStack.push(result)

return operandStack.pop()

def doMath(op, op1, op2):

if op == "*":

return op1 * op2

elif op == "/":

return op1 / op2

elif op == "+":

return op1 + op2

else:

return op1 - op2

print(postfixEval(‘7 8 + 3 2 + /‘))

原文：http://blog.csdn.net/python2014/article/details/21342223

總結

以上是生活随笔為你收集整理的python前缀表达式求值_python数据结构与算法 11 后缀表达式求值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。