LeetCode - #150 逆波蘭表達式求值

​

前言

我們社群陸續會将顧毅（Netflix 增長，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 算法題題解整理為文字版以友善大家學習與閱讀。

LeetCode 算法到目前我們已經更新到 150 期，我們會保持更新時間和進度（周一、周三、周五早上 9:00 釋出），每期的内容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千裡；不積小流，無以成江海，Swift社群 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水準：中等

1. 描述

根據 逆波蘭表示法，求表達式的值。

有效的算符包括 ​

​+​

​​、​

​-​

​​、​

​*​

​​、​

​/​

​ 。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。

注意 兩個整數之間的除法隻保留整數部分。

可以保證給定的逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。

2. 示例

示例 1

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

示例 2

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

示例 3

輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22
解釋：該算式轉化為常見的中綴算術表達式為：
  ((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      

限制條件：

• ​

  ​1 <= tokens.length <= 10^4​

  ​
• ​

  ​tokens[i]​

  ​​ 是一個算符（​

  ​"+"​

  ​​、​

  ​"-"​

  ​​、​

  ​"*"​

  ​​ 或​

  ​"/"​

  ​​），或是在範圍​

  ​[-200, 200]​

  ​ 内的一個整數

逆波蘭表達式：

逆波蘭表達式是一種字尾表達式，所謂字尾就是指算符寫在後面。

• 平常使用的算式則是一種中綴表達式，如​

  ​( 1 + 2 ) * ( 3 + 4 )​

  ​ 。
• 該算式的逆波蘭表達式寫法為​

  ​( ( 1 2 + ) ( 3 4 + ) * )​

  ​ 。

逆波蘭表達式主要有以下兩個優點：

• 去掉括号後表達式無歧義，上式即便寫成​

  ​1 2 + 3 4 + *​

  ​ 也可以依據次序計算出正确結果。
• 适合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，并将結果壓入棧中

3. 答案

class EvaluateReversePolishNotation {
    func evalRPN(_ tokens: [String]) -> Int {
        var stack = [Int]()

        for token in tokens {
            if let num = Int(token) {
                stack.append(num)
            } else {
                guard let postNum = stack.popLast(), let prevNum = stack.popLast() else {
                    fatalError("Invalid Input")
                }

                stack.append(operate(token, prevNum, postNum))
            }
        }

        if let last = stack.last {
            return last
        } else {
            fatalError("Invalid Input")
        }
    }

    private func operate(_ token: String, _ prevNum: Int, _ postNum: Int) -> Int {
        switch token {
            case "+":
                return prevNum + postNum
            case "-":
                return prevNum - postNum
            case "*":
                return prevNum * postNum
            case "/":
                return prevNum / postNum
            default:
                fatalError("Invalid Input")
        }
    }
}      

• 主要思想：當遇到運算符時，将數字壓入堆棧，并彈出2進行運算。
• 時間複雜度： O(n)
• 空間複雜度： O(n)

該算法題解的倉庫：LeetCode-Swift

關于我們