पायथन का उपयोग करके कोष्ठक स्ट्रिंग को संतुलित करने के लिए न्यूनतम सम्मिलन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास कोष्ठक '(' और ')' खोलने और बंद करने के साथ एक स्ट्रिंग है। हम कह सकते हैं कि एक कोष्ठक स्ट्रिंग संतुलित होती है जब -

कोई भी बायां कोष्ठक '(' में दो लगातार दाएं कोष्ठक होते हैं '))'।
एक बायां कोष्ठक '(' दो क्रमागत दायें कोष्ठक से पहले जाना चाहिए))'।

तो उदाहरण के लिए, "())", "())(())))" संतुलित हैं लेकिन ")()", "()))" नहीं हैं। यदि हमारे पास ऐसी स्ट्रिंग है, तो हमें स्ट्रिंग को संतुलित करने के लिए कोष्ठकों की संख्या (खोलना या बंद करना) गिनना होगा।

इसलिए, यदि इनपुट s ="(()))))" जैसा है, तो आउटपुट 1 होगा क्योंकि यदि हम इसे विभाजित करते हैं, तो हम "(())))) प्राप्त कर सकते हैं, इसलिए हमें आवश्यकता है स्ट्रिंग को संतुलित करने के लिए "( ()) ())))" बनाने के लिए एक बायां कोष्ठक।

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

:=0, n:=s का आकार
रिट:=0, मैं :=0
जबकि मैं
- अगर s[i] '(' के समान है, तो
:=ओ + 1
- अन्यथा,
  - अगर i + 1
    - अगर o 0 है, तो
      - रिट:=रिट + 1
    - अन्यथा,
:=ओ - 1
- मैं :=मैं + 1
- अन्यथा,
  - रिट:=रिट + 1
  - अगर o 0 है, तो
    - रिट:=रिट + 1
  - अन्यथा,
:=ओ - 1
- मैं :=मैं + 1
रिटर्न रिट + 2 * ओ

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

उदाहरण

def solve(s):
   o = 0
   n = len(s)
   ret = 0
   i = 0
   while i < n:
      if s[i] == '(':
         o += 1
      else:
         if i + 1 < n and s[i + 1] == ')':
            if not o:
               ret += 1
            else:
               o -= 1
               i += 1
         else:
            ret += 1
            if not o:
               ret += 1
            else:
               o -= 1
      i += 1
   return ret + 2 * o
s = "(())))))"
print(solve(s))

इनपुट

"(())))))"