??write in front??
??大家好，我是Aileen??.希望你看完之后，能對你有所幫助，不足請指正！共同學(xué)習(xí)交流.
??本文由Aileen_0v0?? 原創(chuàng) CSDN首發(fā)?? 如需轉(zhuǎn)載還請通知??
??個人主頁：Aileen_0v0??—CSDN博客
??歡迎各位→點贊?? + 收藏?? + 留言???
??系列專欄：Aileen_0v0??的PYTHON學(xué)習(xí)系列專欄——CSDN博客
??我的格言:"沒有羅馬,那就自己創(chuàng)造羅馬~"?

目錄

?回顧

后綴表達(dá)式運算過程

后綴表達(dá)式求值思路及代碼流程

?回顧??

之前我們學(xué)習(xí)了棧的應(yīng)用之前,后綴表達(dá)式的轉(zhuǎn)換,如有遺忘,點擊????

今天我們來學(xué)習(xí)-后綴表達(dá)式求值 問題

跟中綴轉(zhuǎn)換為后綴問題不同

對后綴表達(dá)式來說 ,從左到右掃描的過程中,

由于操作符在操作數(shù)后面,

所以要暫存操作數(shù),在碰到操作符時,再將兩個暫存操作數(shù)進(jìn)行實際計算

這個過程利用的就是棧的特性:操作符只作用于離他最近的兩個操作數(shù).

后綴表達(dá)式運算過程??

后綴表達(dá)式，又稱逆波蘭式，不包含括號，運算符放在兩個運算對象的后面，所有的計算按運算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行（不再考慮運算符的優(yōu)先規(guī)則），非常方便計算機(jī)的計算。

后綴表達(dá)式的計算過程如下：
1??從左至右掃描表達(dá)式，遇到數(shù)字時，將數(shù)字壓入堆棧，遇到運算符時，彈出棧頂?shù)膬蓚€數(shù)，用運算符對它們做相應(yīng)的計算，并將結(jié)果入棧
2??重復(fù)上述過程直到表達(dá)式最右端，最后運算得出的值即為表達(dá)式的結(jié)果

計算后綴表達(dá)式的動態(tài)流程如下,以1+2-3*2的后綴表達(dá)式為例:

最后得到的結(jié)果 - 3 還要 push 回棧頂

后綴表達(dá)式求值思路及代碼流程??

1.首先創(chuàng)建空棧operandStack 用于 暫存操作數(shù)

2.將后綴表達(dá)式 用split方法解析為單詞(token) 的列表

3.從左到右掃描單詞列表

? ?如果單詞是一個操作數(shù),將單詞轉(zhuǎn)換為整型int,壓入operandStack 棧頂

? ?如果單詞是一個操作符 (* / + - ) , 就開始求值, 從 棧頂彈出2個操作數(shù),先彈出的是右操作數(shù),? ? ?后彈出的是左操作數(shù),計算后將值重新壓入棧頂.

4.單詞列表掃描結(jié)束后,表達(dá)式的值就在棧頂

5.彈出棧頂?shù)闹?返回.

class Stack:#Stack---->ADT
    def __init__(self):
        self.items =[]

    def isEmpty(self):
        return self.items == []

# 滿足這些屬性(行為)的是棧
    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    #
    def size(self):
        return len(self.items)

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

通過調(diào)用得到的運行結(jié)果:?

文章來源地址http://www.zghlxwxcb.cn/news/detail-727693.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法-(7)---棧的應(yīng)用-(4)后綴表達(dá)式求值的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！