Chương trình đếm dấu ngoặc không hợp lệ tối thiểu cần được xóa để làm cho chuỗi chính xác trong Python

Giả sử chúng ta có một chuỗi các dấu ngoặc đơn; chúng ta phải viết một hàm để tính toán số lượng tối thiểu các dấu ngoặc đơn được loại bỏ để làm cho chuỗi chính xác (mỗi dấu ngoặc mở cuối cùng được đóng lại).

Vì vậy, nếu đầu vào là "(())) (", thì đầu ra sẽ là 2, vì chuỗi đúng là "(())", loại bỏ ") (".

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

• tổng số:=0, tạm thời:=0
• đối với mỗi p trong s, thực hiện
  • nếu p giống như "(", thì
    • tổng số:=tổng số + 1
  • ngược lại khi p giống với ")" và tổng không phải là 0, thì
    • tổng số:=tổng số - 1
  • nếu không,
    • temp:=temp + 1
• tổng trở lại + nhiệt độ

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

Ví dụ

class Solution:
   def solve(self, s):
      total = 0
      temp = 0
      for p in s:
         if p == "(":
            total += 1
         elif p == ")" and total:
            total -= 1
         else:
            temp += 1
      return total + temp
ob1 = Solution()
string = "(()))("
print(ob1.solve(string))

Đầu vào

"(()))("

Đầu ra

2