पायथन में वैध कोष्ठक बनाने के लिए आवश्यक न्यूनतम निष्कासन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास कोष्ठक '(' , ')' और लोअरकेस अंग्रेजी वर्णों के साथ एक स्ट्रिंग है। हमें कोष्ठकों की न्यूनतम संख्या ('(' या ')', किसी भी स्थिति से) को हटाना होगा ताकि परिणामी कोष्ठक स्ट्रिंग मान्य हो और अंत में किसी भी वैध स्ट्रिंग को वापस करना पड़े। यहां कोष्ठक स्ट्रिंग तब मान्य होती है जब ये सभी मानदंड पूरे हो जाते हैं -

• स्ट्रिंग खाली है और इसमें केवल लोअरकेस वर्ण हैं, या

• स्ट्रिंग को एबी (बी के साथ संयोजित ए) के रूप में लिखा जा सकता है, जहां ए और बी वैध स्ट्रिंग हैं, या

• स्ट्रिंग को (ए) के रूप में लिखा जा सकता है, जहां ए एक वैध स्ट्रिंग है।

इसलिए, यदि इनपुट s ="m)n(o)p" जैसा है, तो आउटपुट "mn(o)p"

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• स्टैक :=एक नई सूची

• अनुक्रमणिका :=एक नया सेट

• मैं :=0

• प्रत्येक सी इन एस के लिए, करें

  • यदि c '(' के समान है, तो

    • मुझे स्टैक में पुश करें

  • अन्यथा जब c ')' के समान हो, तब

    • यदि स्टैक का आकार 0 के समान है, तो

      • इंडेक्स में i डालें

    • अन्यथा,

      • स्टैक से पॉप करें

    • मैं :=मैं + 1

• रिट:=खाली स्ट्रिंग

• अनुक्रमणिका :=सभी तत्वों को अनुक्रमणिका में संग्रहीत करें

• मैं के लिए 0 से s-1 के आकार की सीमा में, करो

  • अगर मैं इंडेक्स में नहीं हूं, तो

    • रिट:=रिट + एस[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