एक व्यंजक में संतुलित कोष्ठकों की जाँच करें O(1) अंतरिक्ष O(N^2) पायथन में समय जटिलता

मान लीजिए कि हमारे पास एक स्ट्रिंग स्ट्रिंग है जिसमें ये कोष्ठक '(', ')', '{', '}', '[' और ']' हैं, तो हमें यह जांचना होगा कि कोष्ठक संतुलित हैं या नहीं। हम कह सकते हैं कि ब्रैकेट संतुलित होते हैं जब ब्रैकेट प्रकार खोलना और बंद करना एक ही प्रकार का होता है। कोष्ठक सही क्रम में बंद हैं।

इसलिए, अगर इनपुट {([])} जैसा है, तो आउटपुट ट्रू होगा।

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

• सीएनटी:=0
• मैं :=0
• j :=-1
• एक फ़ंक्शन को हल करें() परिभाषित करें। इसमें s, अस्थायी लगेगा
• सीएनटी:=सीएनटी - 1
• s :=s से एक नई सूची
• अगर j> -1 और s[j] तापमान के समान है, तो
  • s[i] :='#'
  • s[j] :='#'
  • जबकि j>=0 और s[j] '#' के समान है, do
    • j :=j-1
  • i :=i + 1>
  • वापसी 1
• अन्यथा,
  • वापसी 0
• मुख्य विधि से, निम्न कार्य करें -
• यदि s का आकार 0 के समान है, तो
  • सही लौटें
• अन्यथा,
  • उत्तर:=असत्य
  • जबकि मैं
  • यदि s[i] '}' के समान है, तो
    • उत्तर:=हल करें(s, '{')
    • यदि उत्तर 0 के समान है, तो
      • झूठी वापसी
    • अन्यथा जब s[i] ')' के समान हो, तब
      • उत्तर:=हल करें(s, '(')
      • यदि उत्तर 0 के समान है, तो
        • झूठी वापसी
    • अन्यथा जब s[i] ']' के समान हो, तब
      • उत्तर:=हल करें(s, '[')
      • यदि उत्तर 0 के समान है, तो
        • झूठी वापसी
    • अन्यथा,
      • j :=i
      • i :=i + 1
      • सीएनटी:=सीएनटी + 1
• यदि cnt 0 के समान नहीं है, तो
  • झूठी वापसी
• सही लौटें

cnt = 0
i = 0
j = -1
def solve(s, temp):
   global i, j, cnt
   cnt -= 1
   s = list(s)
   if j > -1 and s[j] == temp:
      s[i] = '#'
      s[j] = '#'
      while j >= 0 and s[j] == '#':
         j -= 1
      i += 1
      return 1
   else:
      return 0
def bracketOrderCheck(s):
   global i, j, cnt
   if len(s) == 0:
      return True
   else:
      ans = False
      while i < len(s):
         if s[i] == '}':
            ans = solve(s, '{')
            if ans == 0:
               return False
         elif s[i] == ')':
            ans = solve(s, '(')
            if ans == 0:
               return False
         elif s[i] == ']':
            ans = solve(s, '[')
            if ans == 0:
               return False
         else:
            j = i
            i += 1
            cnt += 1
      if cnt != 0:
         return False
      return True
print(bracketOrderCheck("{([])}"))

"{(()[])}"

True