पायथन में ब्रैकेट के भीतर संलग्न सबस्ट्रिंग को रिवर्स करने का प्रोग्राम

मान लीजिए, हमारे पास एक लोअरकेस स्ट्रिंग s है जिसमें अक्षर और पैरेंथेसिस "(" और ")" हैं। हमें पैरेंथेसिस के भीतर संलग्न हर स्ट्रिंग को रिकर्सिव तरीके से रिवर्स करना है और परिणामी स्ट्रिंग वापस करनी है।

इसलिए, यदि इनपुट s = "back(aps)ce" है, तो आउटपुट "backspace" होगा।

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

• trav() नामक एक फ़ंक्शन परिभाषित करें। यह s, dir, start, close:= close, ans:= ans लेगा

  • end := "(" यदि dir -1 के समान है, अन्यथा ")"

  • other := "(" यदि end ")" के समान है, अन्यथा ")"

  • जब तक start < s का आकार, और s[start] end के समान नहीं है, करें:

    • यदि s[start] other के समान है, तो:

      • trav(s, -dir, close[other, start] - dir)

      • start := close[other, start] + dir

    • अन्यथा,

      • ans के अंत में s[start] डालें

      • start := start + dir

• मुख्य फ़ंक्शन से, निम्नलिखित करें:

• ans := एक नई सूची

• close := एक नया मैप जिसमें कुंजी ")" और "(" हैं, प्रारंभ में मान दो खाली मैप हैं

• stack := एक नई सूची

• स्ट्रिंग s में प्रत्येक इंडेक्स I और मान c के लिए, करें:

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

    • i को stack में पुश करें

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

    • o := stack का शीर्ष, फिर stack से पॉप करें

    • close[")", i] := o

    • close["(", o] := i

• trav(s, 1, 0)

• खाली स्ट्रिंग के साथ जुड़े ans को वापस करें

उदाहरण

class Solution:
    def solve(self, s):
        ans = []
        close = {")": {}, "(": {}}
        stack = []
        for i, c in enumerate(s):
            if c == "(":
                stack.append(i)
            elif c == ")":
                o = stack.pop()
                close[")"][i] = o
                close["("][o] = i
        def trav(s, dir, start, close=close, ans=ans):
            end = "(" if dir == -1 else ")"
            other = "(" if end == ")" else ")"
            while start < len(s) and s[start] != end:
                if s[start] == other:
                    trav(s, -dir, close[other][start] - dir)
                    start = close[other][start] + dir
                else:
                    ans.append(s[start])
                    start += dir
        trav(s, 1, 0)
        return "".join(ans)

ob = Solution()
print(ob.solve("back(aps)ce"))

इनपुट

"back(aps)ce"

आउटपुट

backspace