পাইথনে বৈধ বন্ধনী তৈরি করার জন্য প্রয়োজনীয় ন্যূনতম অপসারণের জন্য প্রোগ্রাম

ধরুন আমাদের বন্ধনী '(' , ')' এবং ছোট হাতের ইংরেজি অক্ষর সহ একটি স্ট্রিং s আছে। আমাদের ন্যূনতম সংখ্যক বন্ধনী ('(' বা ')', যেকোনো অবস্থান থেকে মুছে ফেলতে হবে যাতে ফলস্বরূপ বন্ধনী স্ট্রিংটি বৈধ হয় এবং অবশেষে কোনো বৈধ স্ট্রিং ফেরত দিতে হয়। এখানে বন্ধনী স্ট্রিংটি বৈধ যখন এই সমস্ত মানদণ্ড পূরণ হয় −

• স্ট্রিংটি খালি এবং এতে শুধুমাত্র ছোট হাতের অক্ষর রয়েছে, অথবা

• স্ট্রিংটিকে AB (B এর সাথে A যুক্ত) হিসাবে লেখা যেতে পারে, যেখানে A এবং B বৈধ স্ট্রিং, অথবা

• স্ট্রিংটি (A) এর ফর্ম হিসাবে লেখা যেতে পারে, যেখানে A একটি বৈধ স্ট্রিং।

সুতরাং, ইনপুট যদি s ="m)n(o)p এর মত হয়, তাহলে আউটপুট হবে "mn(o)p"

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্যাক :=একটি নতুন তালিকা

• indexes :=একটি নতুন সেট

• i :=0

• প্রতিটি c-এর জন্য s, do

  • যদি c '(' এর মত হয়, তাহলে

    • আমাকে স্ট্যাকের মধ্যে ঠেলে

  • অন্যথায় যখন c ')' এর মত হয়, তখন

    • যদি স্ট্যাকের আকার 0 এর মতো হয়, তাহলে

      • ইনডেক্সে i ঢোকান

    • অন্যথায়,

      • স্ট্যাক থেকে পপ

    • i :=i + 1

• ret :=ফাঁকা স্ট্রিং

• indexes :=সূচীতে সমস্ত উপাদান সংরক্ষণ করুন

• i এর জন্য 0 থেকে s - 1 এর আকারের মধ্যে, করুন

  • যদি আমি ইনডেক্সে না থাকি, তাহলে

    • ret :=ret + s[i]

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(s):
   stack = []
   indexes = set()
   i = 0

   for c in s:
      if c == '(':
         stack.append(i)
      elif c == ')':
         if len(stack) == 0:
            indexes.add(i)
         else:
            stack.pop()
      i += 1

   ret = ''
   indexes = indexes.union(stack)
   for i in range(len(s)):
      if i not in indexes:
         ret += s[i]

   return ret

s = "m)n(o)p"
print(solve(s))

ইনপুট

"m)n(o)p"

আউটপুট

mn(o)p