DSA Factory
Free Stacks and queues lessonsStacks and queues · Stage 1 · Matching brackets · Step 4

Reverse inside the brackets

Reverse the text inside each pair of brackets, from the innermost outward, by keeping one piece of text per open level on a stack. About 16 minutes.

A piece of text per level

In (u(love)i), the text love is reversed to evolve, then u plus evolve plus i is reversed, giving iloveu. The inner group is dealt with before the outer one, and that is just what a stack gives you.

Keep the current piece of text. When an opener arrives, push the current piece onto the stack and begin a fresh, empty one.

Letter: add it to the current piece.
Opener: save the current piece and start a new one.
In code
if ch == "(":
    stack.append(cur)
    cur = []
else:
    cur.append(ch)
Reverse inside (u(love)i). Pieces of text are shown after each character.
(
0
u
1
(
2
l
3
o
4
v
5
e
6
)
7
i
8
)
9
i

The opener saved the empty text and started a new piece. Then u was added: u.

Move 1 of 6

Reverse and glue at a closer

A closer ends the innermost group, so the current piece is its finished text. Reverse it. Then take the saved piece off the stack and add the reversed text to its end, and make that the current piece again.

Neither kind of bracket is ever added to the output. When the string ends, the current piece is the answer.

Closer: reverse the piece, then glue it to the saved one.
Never add a bracket: to the output text.
In code
elif ch == ")":
    cur.reverse()
    prev = stack.pop()
    prev.extend(cur)
    cur = prev
Quick check

What does the text (ab(cd)) become after reversing inside each pair?

  1. Adcba
  2. Bcdba
  3. Cabcd
Show the answer

cdba. Inner: cd becomes dc, so the outer text is abdc. Reversing it gives cdba.

Your problem

Reverse substrings between brackets

You are given a string s of lowercase letters and round brackets, in which the brackets are balanced. Reverse the characters inside each pair of matching brackets, starting with the innermost pair, and return the result without any brackets.

Example
s = "(u(love)i)" → "iloveu"

0 ≤ length of s ≤ 2,000 · s has lowercase letters and balanced round brackets

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve