পাইথনে বন্ধনীর মধ্যে আবদ্ধ একটি সাবস্ট্রিংকে বিপরীত করার জন্য প্রোগ্রাম

ধরুন, আমাদের একটি ছোট হাতের স্ট্রিং s আছে যাতে অক্ষর এবং বন্ধনী "(" এবং ")" রয়েছে। আমাদের বন্ধনীর মধ্যে আবদ্ধ প্রতিটি স্ট্রিংকে পুনরাবৃত্ত পদ্ধতিতে উল্টাতে হবে এবং ফলস্বরূপ স্ট্রিংটি ফিরিয়ে দিতে হবে।

সুতরাং, যদি ইনপুট s ="back(aps)ce" এর মত হয়, তাহলে আউটপুট হবে "ব্যাকস্পেস"।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন trav() সংজ্ঞায়িত করুন। এটি s, dir, start, close:=close, ans:=ans

  লাগবে

  • end :="(" যদি dir −1 এর মত হয়, অন্যথায় ")"

  • other :="(" যদি শেষ হয় ")", অন্যথায় ")"

  • যখন শুরু

    • যদি s[start] অন্যের মতো হয়, তাহলে

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

      • শুরু :=বন্ধ [অন্য, শুরু] + dir

    • অন্যথায়,

      • উত্তরের শেষে s[start] ঢোকান

      • start :=start + dir

• প্রধান ফাংশন থেকে, নিম্নলিখিতগুলি করুন -

• উত্তর :=একটি নতুন তালিকা

• বন্ধ করুন :=")" এবং "(" কী সমন্বিত একটি নতুন মানচিত্র প্রাথমিকভাবে দুটি খালি মানচিত্র

• স্ট্যাক :=একটি নতুন তালিকা

• প্রতিটি সূচকের জন্য I এবং s তে c মান, করুন

  • যদি c "(" এর মত হয়, তাহলে

    • আমাকে স্ট্যাকের মধ্যে ঠেলে

  • অন্যথায় যখন c ")" এর মত হয়, তখন

    • o :=স্ট্যাকের উপরে, তারপর স্ট্যাক থেকে পপ করুন

    • বন্ধ করুন[")", i] :=o

    • বন্ধ করুন["(", o] :=i

• trav(s, 1, 0)

• ফাঁকা স্ট্রিং দিয়ে উত্তর যোগ করুন

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