Pythonで特定のスタック操作を実行して最終的な答えを確認するプログラム

opsという文字列のリストがあり、各要素が以下のようなこれらの操作のいずれかであるとします-

• スタックにプッシュされる負でない整数値
• 「POP」を使用して、スタックから最上位の要素を削除します
• 「DUP」を使用すると、最上位の要素がスタックに再度挿入され、複製されます
。
• "+"を使用して、上位2つの要素をポップアウトし、合計値をプッシュします
• "-"を使用して、上位2つの要素をポップアウトし、（top element-topのすぐ下の要素）の結果をプッシュします

したがって、これらの操作をすべて適用した後、スタックの最上位のmot要素を見つける必要があります。一部の操作が無効な場合は、-1を返します。

したがって、入力がops =["5"、 "2"、 "POP"、 "DUP"、 "3"、 "+"、 "15"、 "-"]の場合、出力は7になります。最初に最初の2つの操作を使用して、スタックが[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です。

これを解決するには、次の手順に従います-

• スタック：=新しいスタック
• opsの各iについて、
  • iが数字の場合、
    • iをスタックにプッシュします
  • それ以外の場合、スタックのサイズ> =1で、iが「POP」の場合
    • スタックから最上位の要素をポップ
  • それ以外の場合、スタックのサイズ> =1で、iが「DUP」と同じである場合、
    • 一番上の要素をスタックからpにポップします
    • そしてpを2回挿入します
  • それ以外の場合、スタックのサイズ> =2で、iが "+"と同じ場合、
    • 一番上の要素をスタックから
    ポップします
    • 一番上の要素をスタックからbにポップします
    • （a + b）をスタックにプッシュします
  • それ以外の場合、スタックのサイズ> =2で、iが "-"と同じ場合、
    • 一番上の要素をスタックから
    ポップします
    • 一番上の要素をスタックから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