Turn a string inside out 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 other
Moving 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 (&lt;&gt;,[] 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

(()())     -&gt; ()(()), (())()
(()(())()) -&gt; (()(())())
((())())() -&gt; (()(()()))
Haskell, 124 120 119 117 113 110 109 106 105 104 101 98 bytes

4 bytes saved thanks to bartavelle!

3 bytes saved thanks to Zgarb

1 byte saved thanks to Peter Taylor

Here's a solution I worked out in Haskell.  Its ok right now pretty good thanks to some help I received, but I'm looking to make this shorter, so feedback/suggestions are appreciated.



until(!0)g.map d
_!1=1&lt;0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1&gt;0
g(a:b)=b++[a]
d '('=')'
d _='('


Try it online!

Explanation

This program defines 4 functions,  the first (!) determines if a string is balanced.  Its defined as follows:

_!1=1&lt;0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1&gt;0


This check assumes that the input has an equal number of open and close parens thanks to a suggestion from Peter Taylor.

The next g will rotate the string once.

g(a:b)=b++[a]


Then we have d which simply takes a paren and mirrors it

d '('=')'
d _='('


Finally we have the function we are concerned with. Here we use a pointfree representation of until(!0)g composed with map d, which maps d to the input and applies g until the result is balanced.  This is the exact process described in the question.

until(!0)g.map d