本篇推文共計2000個字，閱讀時間約3分鐘。

01

題目描述

題目描述：

根據(jù)逆波蘭表示法，求表達(dá)式的值。

有效的算符包括 +、-、*、/ 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達(dá)式。

說明：

1.整數(shù)除法只保留整數(shù)部分。

2.給定逆波蘭表達(dá)式總是有效的。換句話說，表達(dá)式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。

示例 1：

輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：
((2 + 1) * 3) = 9

示例 2：

輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：
(4 + (13 / 5)) = 6

示例 3：

輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22
解釋：
該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

02

思路和方法

對于此題我們可以想到用棧的方式來解決:

1.通過遍歷數(shù)組;

2.當(dāng)數(shù)組遍歷到的字符為數(shù)字時，將數(shù)字壓入棧;

3.當(dāng)遇到運算符號時候，再把棧頂?shù)膬蓚€數(shù)字拿出來進(jìn)行計算，計算的結(jié)果再壓入棧中;

4.以此類推直至遍歷完數(shù)組;

5.最后輸出棧中元素，即為最后的答案。

再注意題目的細(xì)節(jié)部分,整數(shù)除法只保留整數(shù)部分。

由上述分析，

我們利用圖解法結(jié)合案例再來直觀的分析地本題。

例如：

輸入tokens = ["2","1","+","3","*"]

圖解如下：

i=0時，

此時遍歷到的數(shù)組字符是數(shù)字2，將數(shù)字2壓入棧中。

i=1時，

此時遍歷到的數(shù)組字符是數(shù)字1，將數(shù)字1壓入棧中。

i=2時，

此時遍歷到的數(shù)組字符是運算符號/，此時將棧頂?shù)膬蓚€元素取出進(jìn)行整除操作。

2/1=2

將棧頂兩個元素的計算結(jié)果2壓入棧中。

i=3時，

此時遍歷到的數(shù)組字符是數(shù)字3，將數(shù)字3壓入棧中。

i=4時，

此時遍歷到的數(shù)組字符是運算符號*，此時將棧頂?shù)膬蓚€元素取出進(jìn)行乘法操作。

2*3=6，將棧頂兩個元素的計算結(jié)果6壓入棧中。

數(shù)組遍歷完畢，最后輸出棧中元素即為結(jié)果

我們用代碼表示為：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack=[]
        for t in tokens:
            if t not in "+-*/":
                stack.append(int(t))
            elif len(stack)>1:
                b,a=stack.pop(),stack.pop()
                if t=='+':
                    stack.append(a+b)
                if t=='-':
                    stack.append(a-b)
                if t=='*':
                    stack.append(a*b)
                if t=='/':
                    stack.append(int(a/b))
        return stack[-1]