A balanced string is a string of parentheses ()
so that every parenthesis is can be matched with another one. More rigorously they are the strings spanned by this grammar:
S → (S)S | ε
We can turn a string "inside out" by:
Switching all occurrences of
(
and)
with each otherMoving characters from the front of the string to the back until the string is balanced again.
Lets do an example.
We start with the balanced string:
(()(())())
We then switch the parens to make
))())(()((
Then move characters from the front of the string to the back of the string until the string is balanced.
))())(()((
)())(()(()
())(()(())
))(()(())(
)(()(())()
(()(())())
Thats our result!
Note that some strings can be turned inside out in multiple ways, for example the string
(()())
When turned inside out can be either:
()(())
or
(())()
However every string has at least one solution.
Task
Write a program to take a balanced string as input and output that string turned inside out. In cases where there may be multiple valid outputs you need only output one of them. You may use a different brace type (<>
,[]
or {}
) if you so wish.
This is a code-golf competition so you should aim to minimize your size of your source code, as measured by bytes.
Test Cases
(()()) -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))