पायथन में अभिव्यक्ति में संतुलित पैरेंथेसिस की जांच O(1) स्पेस और O(N²) समय जटिलता के साथ

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

• ओपनिंग और क्लोजिंग ब्रैकेट का प्रकार समान हो।
• ब्रैकेट सही क्रम में बंद हों।

इसलिए, यदि इनपुट {([])} है, तो आउटपुट True होगा।

समाधान दृष्टिकोण

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

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

उदाहरण

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

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