(*･∀-)b
嗨，我是wec，今天是DAY 28。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個表示逆波蘭表示法的數字和運算符的列表，請計算並返回其值。有效的運算符包括 +、-、* 和 /，並且運算符的兩個操作數總是出現在其前面。使用整數除法時，結果應該向零取整。

🔎 解題思路＆程式碼

1️⃣ 堆疊

第1步： 創建一個空的堆疊stack來儲存數字。
第2步： 遍歷給定的tokens數組，檢查每個元素，如果是數字，將其轉換為整數並推入堆疊。
第3步： 如果遇到運算符：
1.從堆疊中彈出兩個數字 b 和 a（要注意先彈出的是第二個數字!）。
2.根據運算符執行相應的運算，然後將結果推回堆疊中。
第4步： 遍歷結束後，堆疊中的最後一個元素即計算結果，彈出並返回它。
程式碼：

def eval_rpn(tokens)
  stack = []

  tokens.each do |token|
    if token =~ /^-?\d+$/
      stack.push(token.to_i)
    else
      b = stack.pop
      a = stack.pop
      case token
      when '+'
        stack.push(a + b)
      when '-'
        stack.push(a - b)
      when '*'
        stack.push(a * b)
      when '/'
        stack.push((a / b.to_f).floor) 
      end
    end
  end

  stack.pop 
end

🔎 總結

時間複雜度

堆疊： O(n)，n是tokens的長度
➡️ 來到最後一個演算法主題啦!堆疊出場!!堆疊最重要的特點就是後進先出，擺越上面越先被拿出來，類似河內塔的概念。正因為LIFO的特性，我們可以很好的按照順序處理運算符，每處理一個運算符，計算出的結果就可以馬上推回堆疊中，而邏輯也算簡單直觀ヾ(^▽^ヾ)!

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃好市多牛肉捲。
明天要說：Ruby精選刷題！Medium路跑D-21(>∀･)⌒☆