पायथन में वैध पैरेंथेसिस बनाने के लिए न्यूनतम हटाने का प्रोग्राम

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

• स्ट्रिंग खाली है और केवल लोअरकेस वर्ण रखती है, या
• स्ट्रिंग को AB (A को B के साथ जोड़कर) के रूप में लिखा जा सकता है, जहां A और B वैध स्ट्रिंग्स हैं, या
• स्ट्रिंग को (A) के रूप में लिखा जा सकता है, जहां A एक वैध स्ट्रिंग है।

उदाहरण के लिए, यदि इनपुट s = "m)n(o)p" है, तो आउटपुट "mn(o)p" होगा।

हल करने के चरण

1. stack := एक नई सूची
2. indexes := एक नया सेट
3. i := 0
4. s में प्रत्येक c के लिए:
   • यदि c == '(', तो i को stack में पुश करें।
   • अन्यथा यदि c == ')', तो:
     • यदि stack का आकार 0 है, तो i को indexes में डालें।
     • अन्यथा, stack से पॉप करें।
   • i := i + 1
5. ret := खाली स्ट्रिंग
6. indexes := indexes के साथ stack के सभी तत्वों को यूनियन करें।
7. i को 0 से len(s) - 1 तक लूप चलाएं:
   • यदि i indexes में नहीं है, तो ret := ret + s[i]
8. ret वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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