Python程式：透過執行給定的棧操作檢查最終答案

假設我們有一個名為 ops 的字串列表，其中每個元素都是以下操作之一：

  • 一個非負整數，將被壓入棧中。
  • "POP" 用於刪除棧頂元素。
  • "DUP" 用於將棧頂元素再次插入棧中，使其複製。
  • "+" 用於彈出棧頂兩個元素並壓入它們的和。
  • "-" 用於彈出棧頂兩個元素並壓入結果（棧頂元素減去其下方元素）。

因此，我們需要找到應用所有這些操作後棧頂的元素。如果某些操作無效，則返回 -1。

例如，如果輸入為 ops = ["5", "2", "POP", "DUP", "3", "+", "15", "-"]，則輸出將為 7，因為最初使用前兩個操作，插入 5 和 2，所以棧為 [5, 2]，然後彈出 1 個，所以當前棧為 [5]。之後對於 DUP，5 將被複制，所以棧為 [5, 5]，然後新增 3 [5, 5, 3]，然後對於加法操作，它將變為 [5, 8]，然後插入 15，所以 [5, 8, 15]，然後對於減法操作，棧將變為 [5, (15-8)] = [5, 7]。因此，棧頂元素為 7。

為了解決這個問題，我們將遵循以下步驟：

  • stack := 一個新的棧
  • 對於 ops 中的每個 i，執行：
    • 如果 i 是一個數字，則：
      • 將 i 壓入棧中。
    • 否則，當棧的大小 >= 1 且 i 等於 "POP" 時，則：
      • 從棧中彈出棧頂元素。
    • 否則，當棧的大小 >= 1 且 i 等於 "DUP" 時，則：
      • 從棧中彈出棧頂元素到 p。
      • 並將 p 插入兩次。
    • 否則，當棧的大小 >= 2 且 i 等於 "+" 時，則：
      • 從棧中彈出棧頂元素到 a。
      • 從棧中彈出棧頂元素到 b。
      • 將 (a + b) 壓入棧中。
    • 否則，當棧的大小 >= 2 且 i 等於 "-" 時，則：
      • 從棧中彈出棧頂元素到 a。
      • 從棧中彈出棧頂元素到 b。
      • 將 (a - b) 壓入棧中。
    • 否則：
      • 返回 -1。
  • 返回棧頂元素。

示例

讓我們看下面的實現以更好地理解：

def solve(ops):
   stack = []
   for i in ops:
      if i.isnumeric() == True:
         stack.append(int(i))
      elif len(stack) >= 1 and i == "POP":
         stack.pop()
      elif len(stack) >= 1 and i == "DUP":
         p = stack.pop()
         stack.append(p)
         stack.append(p)
      elif len(stack) >= 2 and i == "+":
         a = stack.pop()
         b = stack.pop()
         stack.append(a + b)
      elif len(stack) >= 2 and i == "-":
         a = stack.pop()
         b = stack.pop()
         stack.append(a - b)
      else:
         return -1
   return stack.pop()

ops = ["5", "2", "POP", "DUP", "3", "+", "15", "-"]
print(solve(ops))

輸入

["5", "2", "POP", "DUP", "3", "+", "15", "-"]

輸出

7

更新於: 2021-10-14

736 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告