Đảo ngược chuỗi trong ngoặc – reverseInParentheses

reverse-a-string

Đảo ngược chuỗi là một bài toán cơ bản mà tất cả chúng ta đã từng làm qua khi học lập trình, hôm nay chúng ta sẽ nâng cấp bài toán này lên một xíu nha.

Như mô tả trong tiêu đề, chúng ta sẽ đảo ngược các chuỗi trong ngoặc. Để dễ hiểu hơn, chúng ta cùng nhìn qua các ví dụ input và output của bài toán:

  1. (bar) $\to$ rab
  2. foo(bar)baz $\to$ foorabbaz
  3. foo(bar)baz(blim) $\to$ foorabbazmilb
  4. foo(bar(baz))blim $\to$ foo(barzab)blim $\to$ foobazrabblim

Có thể dễ dàng thấy nhiệm vụ của chúng ta sẽ đảo ngược tất cả các chuỗi trong ngoặc cho đến khi chuỗi không còn ngoặc nữa. Một chuỗi nếu nằm trong nhiều ngoặc có thể sẽ bị đảo nhiều lần (như trong ví dụ 4).

Input: chuỗi đề bài

Output: chuỗi đã được xử lý (đảo nội dung trong ngoặc)

Bài tập này có 2 cách giải cơ bản:

  • Cách 1: Sử dụng đệ quy, tìm các chuỗi trong ngoặc để đảo ngược
  • Cách 2: Sử dụng vòng lặp thay cho đệ quy

Gợi ý 1: Các bạn có thể so trùng ký tự để tìm vị trí đóng mở ngoặc, nhưng nếu sử dụng regular expression (regex – thư viện re) thì việc xác định chuỗi trong ngoặc sẽ đơn giản hơn.

Gợi ý 2: Sử dụng tính năng slicing string của python để đơn giản việc cộng chuỗi cũng như việc đảo chuỗi.