Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình kiểm tra câu trả lời cuối cùng bằng cách thực hiện các hoạt động ngăn xếp đã cho trong Python

Giả sử chúng ta có một danh sách các chuỗi được gọi là ops trong đó mỗi phần tử là bất kỳ một trong các thao tác này như bên dưới -

  • Một giá trị số nguyên không âm sẽ được đẩy vào một ngăn xếp
  • "POP" để xóa hầu hết phần tử trên cùng khỏi ngăn xếp
  • "DUP" để chèn lại phần tử trên cùng vào ngăn xếp, để làm cho nó trùng lặp
  • "+" để bật ra hai phần tử trên cùng và đẩy giá trị tổng ra
  • "-" để bật ra hai phần tử trên cùng và đẩy kết quả về (phần tử trên cùng - phần tử ngay dưới đầu)

Vì vậy, chúng ta phải tìm phần tử mot trên cùng trong ngăn xếp sau khi áp dụng tất cả các thao tác này. Nếu một số thao tác không hợp lệ thì trả về -1.

Vì vậy, nếu đầu vào là ops =["5", "2", "POP", "DUP", "3", "+", "15", "-"], thì đầu ra sẽ là 7 vì ban đầu sử dụng hai hoạt động đầu tiên, chèn 5 và 2 để ngăn xếp giống như [5, 2], sau đó bật một để ngăn xếp hiện tại giống như [5]. Sau đó đối với DUP, 5 sẽ được nhân đôi, vì vậy ngăn xếp giống như [5, 5], sau đó thêm 3 [5, 5, 3], sau đó đối với phép toán cộng nó sẽ là [5, 8], sau đó chèn 15, như vậy [5, 8, 15] sau đó đối với phép toán trừ, ngăn xếp sẽ là [5, (15-8)] =[5, 7]. Vì vậy, phần tử hàng đầu là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • ngăn xếp:=một ngăn xếp mới
  • đối với mỗi tôi trong hoạt động, hãy thực hiện
    • nếu tôi là một số, thì
      • đẩy tôi vào ngăn xếp
    • ngược lại khi kích thước của ngăn xếp> =1 và tôi là "POP", thì
      • phần tử bật lên trên cùng từ ngăn xếp
    • ngược lại khi kích thước của ngăn xếp> =1 và tôi giống như "DUP", thì
      • bật phần tử cao nhất từ ​​ngăn xếp vào p
      • và chèn p hai lần
    • ngược lại khi kích thước của ngăn xếp> =2 và tôi giống như "+", thì
      • bật phần tử cao nhất từ ​​ngăn xếp vào một
      • bật phần tử cao nhất từ ​​ngăn xếp vào b
      • đẩy (a + b) vào ngăn xếp
    • ngược lại khi kích thước của ngăn xếp> =2 và tôi giống như "-", thì
      • bật phần tử cao nhất từ ​​ngăn xếp vào một
      • bật phần tử cao nhất từ ​​ngăn xếp vào b
      • đẩy (a - b) vào ngăn xếp
    • nếu không,
      • trả về -1
  • trả về phần tử trên cùng từ ngăn xếp

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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))

Đầu vào 

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

Đầu ra 

7