โปรแกรมเพื่อย้อนกลับสตริงย่อยที่อยู่ภายในวงเล็บใน Python

สมมติว่า เรามีสตริงตัวพิมพ์เล็ก s ที่มีตัวอักษรและวงเล็บ "(" และ ")" เราต้องย้อนกลับทุกสตริงที่อยู่ภายในวงเล็บในลักษณะวนซ้ำและส่งกลับสตริงที่เป็นผลลัพธ์

ดังนั้น หากอินพุตเป็น s ="back(aps)ce" เอาต์พุตจะเป็น "backspace"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน trav() สิ่งนี้จะใช้เวลา s, dir, start, close:=close, ans:=ans

  • end :="(" ถ้า dir เหมือนกับ -1 มิฉะนั้น ")"

  • อื่นๆ :="(" ถ้าสิ้นสุดเหมือนกับ ")" มิฉะนั้น ")"

  • ในขณะที่ start

    • ถ้า s[start] เหมือนกับตัวอื่นๆ แล้ว

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

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

    • มิฉะนั้น

      • ใส่ s[start] ต่อท้าย ans

      • start :=start + dir

• จากหน้าที่หลัก ให้ทำดังต่อไปนี้ -

• ans :=รายการใหม่

• ปิด :=แผนที่ใหม่ที่มีคีย์ ")" และ "(" ในขั้นต้น ค่าเป็นสองแผนที่ว่าง

• stack :=รายการใหม่

• สำหรับแต่ละดัชนี I และค่า c ใน s ทำ

  • ถ้า c เหมือนกับ "(" แล้ว

    • ดันฉันเข้ากอง

  • มิฉะนั้นเมื่อ c เหมือนกับ ")" แล้ว

    • o :=ด้านบนสุดของ stack แล้วป๊อปจาก stack

    • ปิด[")", i] :=o

    • ปิด["(", o] :=ฉัน

• 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