21
1
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
(()()) -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
Is it guaranteed that there is always a solution? – Luis Mendo – 2017-07-04T14:45:54.863
@LuisMendo Yes, I have proven this. If you would like to see the proof, feel free to ping me in chat. – Post Rock Garf Hunter – 2017-07-04T14:48:47.337
Thanks. It is sufficient for me to know that. Maybe you should write it into the challenge, otherwise you would need to define what to output if no solution – Luis Mendo – 2017-07-04T15:00:18.537
related – officialaimm – 2017-07-04T15:01:10.110