LeetCode 150：逆波蘭表達(dá)式求值

今天來做逆波蘭表達(dá)式求值，可能臭寶們一看“逆波蘭表達(dá)式”這個(gè)洋氣的名字，下意識(shí)的會(huì)覺得難搞。

其實(shí)這個(gè)詞只是看著唬人，就是紙老虎。

逆波蘭表達(dá)式又叫后綴表達(dá)式，是將運(yùn)算符寫在操作數(shù)之后。

像我們平時(shí)寫的是類似 a + b 這種表達(dá)式，這叫中綴表達(dá)式，符合我們作為人的思維方式，而后波蘭表達(dá)式則是寫成 ab+。

簡(jiǎn)單說下為啥要弄個(gè)逆波蘭表達(dá)式這個(gè)玩意。

原因就是從我們?nèi)说慕嵌葋砜矗?jiǎn)單的一批的中綴表達(dá)式，在計(jì)算機(jī)看來，簡(jiǎn)直是復(fù)雜的無與倫比，因?yàn)橛?jì)算機(jī)普遍采用的是棧式結(jié)構(gòu)，執(zhí)行的是先入后出的操作，所以逆波蘭式在它眼里才是個(gè)正常的娃兒。

???LeetCode 150：逆波蘭表達(dá)式求值

題意

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

有效算符包括?+?-?* /。運(yùn)算對(duì)象可以是整數(shù)，可以是其他逆波蘭表達(dá)式。

示例

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

輸出：9

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

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

提示

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

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

1 <= tokens.length <= 104

tokens[i] 要么是一個(gè)算符（"+"、"-"、"*" 或 "/"），要么是一個(gè)在范圍 [-200, 200] 內(nèi)的整數(shù)。

題目解析

水題，難度中等，感覺難度都堆在“逆波蘭表達(dá)式”這幾個(gè)字上。

逆波蘭表達(dá)式主要有以下兩個(gè)優(yōu)點(diǎn)：

• 去掉括號(hào)后表達(dá)式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據(jù)次序計(jì)算出正確結(jié)果。

• 適合用棧操作運(yùn)算：遇到數(shù)字則入棧；遇到算符則取出棧頂兩個(gè)數(shù)字進(jìn)行計(jì)算，并將結(jié)果壓入棧中。

在前面說了，逆波蘭表達(dá)式為計(jì)算機(jī)這種思維而生，那這個(gè)逆波蘭表達(dá)式求值顯然也是用棧來解決。

逆波蘭表達(dá)式嚴(yán)格遵守從左到右的運(yùn)算，所以解法也很簡(jiǎn)單，其實(shí)就是維護(hù)一個(gè)棧，從左到右掃描 tokens：

• 如果遇到數(shù)，數(shù)入棧。

• 如果遇到操作符，棧頂兩個(gè)元素出棧，先出棧的數(shù)在運(yùn)算符右側(cè)，后出棧的在運(yùn)算符左側(cè)，運(yùn)算完后，將運(yùn)算值入棧。

等全部掃描完以后，棧內(nèi)剩下的那個(gè)數(shù)，就是最后的結(jié)果。

圖解

假設(shè) tokens =??["2", "1", "+", "3", "*"]。

首先維護(hù)一個(gè)棧，根據(jù)“題目解析”中說的，碰到數(shù)先入棧，那第 1 步和第 2 步，數(shù)字 2 和數(shù)字 1 入棧。

# 初始化棧stack?=?[]for c in tokens:    # 如果當(dāng)前字符不是操作符，入棧    if c not in ['+', '-', '*', '/']:        stack.append(int(c))

接下來第 3 步，當(dāng)前元素為操作符，所以棧頂兩個(gè)元素出棧，先出棧的在操作符右側(cè)，后出棧的在操作符左側(cè)，運(yùn)算完，新值入棧。

# 先出棧的數(shù)在操作符右側(cè)right = stack.pop()# 后出棧的數(shù)在操作符左側(cè)left?=?stack.pop()# 進(jìn)行相應(yīng)運(yùn)算，運(yùn)算完的數(shù)值入棧if c == '+':    stack.append(left + right)

往下第 4 步，是數(shù)字，入棧。

最后第 5 步，碰到操作符，出棧，相乘，入棧。

# 進(jìn)行相應(yīng)運(yùn)算，運(yùn)算完的數(shù)值入棧if c == '+':    stack.append(left + right)elif c == '-':    stack.append(left - right)elif c == '*':    stack.append(left * right)else:    # 除法這注意一下    stack.append(int(left / right))

至此，結(jié)束，返回棧中的值即可。

# 最后只剩下一個(gè)數(shù)值，就是最終結(jié)果return stack[0]

因?yàn)檫@個(gè)只需要從左到右遍歷 tokens 數(shù)組一次，所以時(shí)間復(fù)雜度為 O(N)。

做的過程中維護(hù)了一個(gè)棧存儲(chǔ)計(jì)算過程中的數(shù)，所以空間復(fù)雜度為 O(N)。

代碼實(shí)現(xiàn)

Python 代碼實(shí)現(xiàn)

class Solution:    def evalRPN(self, tokens: List[str]) -> int:        # 初始化棧        stack = []
        for c in tokens:            # 如果當(dāng)前字符不是操作符，入棧            if c not in ['+', '-', '*', '/']:                stack.append(int(c))            # 如果當(dāng)前字符是操作符            else:                # 先出棧的數(shù)在操作符右側(cè)                right = stack.pop()                # 后出棧的數(shù)在操作符左側(cè)                left = stack.pop()
                # 進(jìn)行相應(yīng)運(yùn)算，運(yùn)算完的數(shù)值入棧                if c == '+':                    stack.append(left + right)                elif c == '-':                    stack.append(left - right)                elif c == '*':                    stack.append(left * right)                else:                    # 除法這注意一下                    stack.append(int(left / right))        # 最后只剩下一個(gè)數(shù)值，就是最終結(jié)果        return stack[0]

Java 代碼實(shí)現(xiàn)

class Solution {    public int evalRPN(String[] tokens) {        Deque stack = new LinkedList();        int n = tokens.length;        for (int i = 0; i < n; i++) {            String token = tokens[i];            if (isNumber(token)) {                stack.push(Integer.parseInt(token));            } else {                int num2 = stack.pop();                int num1 = stack.pop();                switch (token) {                    case "+":                        stack.push(num1 + num2);                        break;                    case "-":                        stack.push(num1 - num2);                        break;                    case "*":                        stack.push(num1 * num2);                        break;                    case "/":                        stack.push(num1 / num2);                        break;                    default:                }            }        }        return stack.pop();????}

好啦，圖解逆波蘭表達(dá)式的值到這就結(jié)束啦。

這道題就是多學(xué)了一個(gè)概念，解題方法和代碼沒什么難度。

最后也歡迎大家加入帥地的知識(shí)星球。帥地會(huì)在星球知無不言，無論是 offer 選擇，職業(yè)規(guī)劃還是學(xué)習(xí)路線，帥地都會(huì)在 48 小時(shí)以內(nèi)答復(fù)你的問題，并且根據(jù)你自身的情況，為你量身定制學(xué)習(xí)路線。

你有任何的疑惑，帥地都會(huì)答復(fù)你，并且星球里也有一群和你相同年齡的小伙伴在奮斗，都是未來的卷王

星球還提供了超全學(xué)習(xí)攻略，小白只需要跟著我提供的攻略學(xué)習(xí)就可以了

帥地會(huì)在星球會(huì)提供如下服務(wù)

1、【一對(duì)一咨詢服務(wù)】48 小時(shí)以內(nèi)超詳細(xì)回答你的任何問題，包括寫作等等，這是知識(shí)星球最重要的功能。最近一周就回答了十幾個(gè) offer 選擇，校招等學(xué)習(xí)路線問題。

2、【學(xué)習(xí)攻略】校招這方面比較有經(jīng)驗(yàn)，帥地會(huì)提供完整的學(xué)習(xí)攻略，小白跟著帥地說的學(xué)習(xí)就行，。

3、簡(jiǎn)歷修改，項(xiàng)目等學(xué)習(xí)資源，offer 收割機(jī)嘉賓分享等等。

目前星球是專注于校招，在校生學(xué)習(xí)指導(dǎo)這塊，一定可以讓你少走彎路，已經(jīng)有 590+ 位小伙伴加入，這里還有一些 20 元的優(yōu)惠卷，如果你信的過帥地，那么歡迎你的加入。

點(diǎn)擊閱讀原文可以了解詳情