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

สมมติว่าเรามีรายการสตริงชื่อ ops ที่แต่ละสมาชิกเป็นการดำเนินการหนึ่งในนี้:

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

เราต้องหาสมาชิกบนสุดของ stack หลังทำการดำเนินการทั้งหมด หากมีการดำเนินการไม่ถูกต้อง คืนค่า -1

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

ขั้นตอนการแก้ปัญหา

1. stack := สแต็กใหม่
2. สำหรับแต่ละ i ใน ops:
   • ถ้า i เป็นตัวเลข: push i เข้า stack
   • มิฉะนั้นถ้า ขนาด stack >= 1 และ i == "POP": pop ตัวบนสุด
   • มิฉะนั้นถ้า ขนาด stack >= 1 และ i == "DUP": pop ตัวบนสุดเก็บใน p แล้ว push p สองครั้ง
   • มิฉะนั้นถ้า ขนาด stack >= 2 และ i == "+": pop a, pop b, push a + b
   • มิฉะนั้นถ้า ขนาด stack >= 2 และ i == "-": pop a, pop b, push a - b
   • มิฉะนั้น: คืนค่า -1
3. คืนค่าตัวบนสุดจาก stack

ตัวอย่างการใช้งาน

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