โปรแกรมตรวจสอบคำตอบสุดท้ายโดยดำเนินการสแต็คที่กำหนดใน Python

สมมติว่าเรามีรายการสตริงที่เรียกว่า ops โดยที่แต่ละองค์ประกอบเป็นหนึ่งในการดำเนินการดังต่อไปนี้ -

• ค่าจำนวนเต็มที่ไม่ติดลบที่จะถูกผลักเข้าไปในสแต็ก
• "POP" เพื่อลบองค์ประกอบส่วนใหญ่บนสุดออกจากสแต็ก
• "DUP" เพื่อแทรกองค์ประกอบด้านบนอีกครั้งลงในสแต็กเพื่อให้ซ้ำกัน
• "+" เพื่อดึงสององค์ประกอบด้านบนออกมาแล้วดันค่าผลรวม
• "-" เพื่อแสดงองค์ประกอบสองอันดับแรกและผลักผลลัพธ์ของ (องค์ประกอบด้านบน - องค์ประกอบด้านล่างด้านบน)

ดังนั้นเราจึงต้องหาองค์ประกอบ mot อันดับต้น ๆ ในสแต็กหลังจากใช้การดำเนินการทั้งหมดเหล่านี้ หากการดำเนินการบางอย่างไม่ถูกต้อง ให้คืนค่า -1

ดังนั้นหากอินพุตเป็นเหมือน ops =["5", "2", "POP", "DUP", "3", "+", "15", "-"] ดังนั้นเอาต์พุตจะเป็น 7 เพราะ เริ่มแรกโดยใช้สองการดำเนินการแรก แทรก 5 และ 2 เพื่อให้สแต็กเป็นเหมือน [5, 2] จากนั้นป๊อปอันหนึ่งเพื่อให้สแต็กปัจจุบันเป็นเหมือน [5] หลังจากนั้นสำหรับ DUP 5 จะถูกทำซ้ำ ดังนั้น stack จะเป็นเช่น [5, 5] จากนั้นเพิ่ม 3 [5, 5, 3] จากนั้นสำหรับการดำเนินการเพิ่มเติมจะเป็น [5, 8] จากนั้นใส่ 15 ดังนั้น [5, 8, 15] หลังจากนั้นสำหรับการดำเนินการลบ สแต็กจะเป็น [5, (15-8)] =[5, 7] ดังนั้นองค์ประกอบที่สำคัญที่สุดคือ 7.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• stack :=สแต็คใหม่
• สำหรับแต่ละคนใน ops ทำ
  • ถ้าฉันเป็นตัวเลข
    • ผลักฉันเข้าไปในสแต็ก
  • มิฉะนั้นเมื่อขนาดของสแต็ก>=1 และฉันคือ "POP" แล้ว
    • ป๊อปองค์ประกอบด้านบนจากสแต็ก
  • มิฉะนั้นเมื่อขนาดของสแต็ก>=1 และฉันเหมือนกับ "DUP" แล้ว
    • ป๊อปองค์ประกอบบนสุดจากสแต็กเป็น p
    • และใส่ p สองครั้ง
  • มิฉะนั้นเมื่อขนาดของ stack>=2 และ i เท่ากับ "+" แล้ว
    • ป๊อปองค์ประกอบบนสุดจากสแต็กเป็น a
    • ป๊อปองค์ประกอบบนสุดจากสแต็กเป็น b
    • ดัน (a + b) ลงในสแต็ก
  • มิฉะนั้นเมื่อขนาดของ stack>=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