[Question]
  [
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](https://chat.stackexchange.com/transcript/message/38554888#38554888).
# 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](/questions/tagged/code-golf "show questions tagged 'code-golf'") competition so you should aim to minimize your size of your source code, as measured by bytes.
## Test Cases
```
(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
```
  
[Answer]
# [Haskell](https://www.haskell.org/), ~~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<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0
g(a:b)=b++[a]
d '('=')'
d _='('
```
[Try it online!](https://tio.run/##RYtBC4IwGIbv@xWbBvuGGO46@gKJkCDKS6eKMTFNmiJlIES/fU0v8T6H5zm8d/N63Kx1nzik@/SQndJsSzd5TsP4Syq8uHc3NBZYIupla3paEs0kylVCgANXRrARDYMxloKA/nfkWzONcp2QGowqBBZRdDZXUlJ/RC64N43eXWuaTqndEQSZFPtn0w2LKgAQE34zswTuBw "Haskell – Try It Online")
## Explanation
This program defines 4 functions, the first `(!)` determines if a string is balanced. Its defined as follows:
```
_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>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
```
[Answer]
# [SOGL V0.12](https://github.com/dzaima/SOGL), ~~12~~ 11 [bytes](https://github.com/dzaima/SOGL/blob/master/chartable.md)
```
↔]»:l{Ƨ()øŗ
```
[Try it Here!](https://dzaima.github.io/SOGLOnline/?code=JXUyMTk0JTVEJUJCJTNBbCU3QiV1MDFBNyUyOCUyOSVGOCV1MDE1Nw__,inputs=JTI4JTI4JTI5JTI4JTI4JTI5JTI5JTI4JTI5JTI5)
Explanation:
```
↔            mirror characters
 ]           do ... while the top of stack is truthy
  »            put the last letter at the start
   :           duplicate it
    l{         length times do
      Ƨ()        push "()"
         ø       push ""
          ŗ      replace ["()" with ""]
             if the string left on stack is empty (aka all matched parentheses could be removed), then stop the while loop
```
Note: `l{` could be replaced with [(](https://github.com/dzaima/SOGL/blob/master/P5ParserV0_12/data/charDefs.txt#L202) for 10 bytes, but, sadly, it isn't implemented.
[Answer]
## CJam (20 chars)
```
q1f^0X${~_}%_:e>#)m<
```
[Online demo](http://cjam.aditsu.net/#code=q1f%5E0X%24%7B~_%7D%25_%3Ae%3E%23)m%3C&input=(()(())()))
or for the same char count
```
q1f^_,,{0W$@<~}$W=m<
```
[Online demo](http://cjam.aditsu.net/#code=q1f%5E_%2C%2C%7B0W%24%40%3C~%7D%24W%3Dm%3C&input=(()(())()))
### Dissection
The two versions have a common header and footer
```
q1f^    e# Read input and toggle least significant bit of each character
        e# This effectively swaps ( and )
m<      e# Stack: swapped_string index
        e# Rotates the string to the left index characters
```
Then the bit in the middle obviously calculates how far it's necessary to rotate. Both of them use evaluation and rely on `(` being the CJam decrement operator and `)` being the increment operator.
```
0X$     e# Push 0 and a copy of the swapped string
{~_}%   e# Map: evaluate one character and duplicate top of stack
        e# The result is an array of the negated nesting depth after each character
_:e>    e# Copy that array and find its maximum value
#       e# Find the first index at which that value occurs
)       e# Increment
```
vs
```
_,,     e# Create array [0 1 ... len(swapped_string)-1]
{       e# Sort with mapping function:
  0W$@  e#   Rearrange stack to 0 swapped_string index
  <~    e#   Take first index chars of swapped_string and evaluate
}$      e# The result is an array of indices sorted by the negated nesting depth
W=      e# Take the last one
```
[Answer]
# JavaScript (ES6), ~~111~~ 105 bytes
(Saved 2 bytes thanks to @CraigAyre, 2 bytes thanks to @PeterTaylor, 2 bytes thanks to @Shaggy.)
```
s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``
```
**Ungolfed:**
```
s=>(
  r=[...s].map(c=>'()'[c<')'|0]),  //switch "(" and ")"
  r.some(_=>(
    r.push(r.shift(i=0)),          //move last element to beginning of array, initialize i
    !r.some(c=>(i+=c<')'||-1)<0)   //check if balanced (i should never be less than 0)
  )),
  r.join``
)
```
**Test cases:**
```
let f=
s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``
console.log(f('(()())'));      // ()(())
console.log(f('(()(())())'));  // (()(())())
console.log(f('((())())()'));  // (()(()()))
```
[Answer]
# [Retina](https://github.com/m-ender/retina), ~~46~~ 38 bytes
```
T`()`)(
(.*?)(((\()|(?<-4>\)))+)$
$2$1
```
[Try it online!](https://tio.run/##K0otycxL/K@q4Z7wPyRBQzNBU4NLQ0/LXlNDQyNGQ7NGw95G18QuRlNTU1tThUvFSMXw/38NDU0NTU0uEAWkIUwIQ0MTAA "Retina – Try It Online") Link includes test cases. Edit: Saved 8 bytes with help from @MartinEnder. The first stage simply transposes the parentheses, while the second stage looks for longest suffix that's a valid balanced prefix, which apparently is a sufficient condition for the rotation to be fully balanced. The balancing is detected using balancing groups. The construct `((\()|(?<-4>\)))+` matches any number of `(`s plus any number of `)`s as long as we have already (`<-4>`) seen as many `(`s. Since we're only looking for a valid prefix we don't have to match the remaining `)`s.
[Answer]
# PHP, ~~110~~ 108 bytes
```
for($s=$argn;;$p?die(strtr($s,"()",")(")):$s=substr($s,1).$s[$i=0])for($p=1;$p&&$c=$s[$i++];)$p-=$c<")"?:-1;
```
Run as pipe with `-nR` or [test it online](http://sandbox.onlinephpfunctions.com/code/64042062d19ae3ce2651f9b367ee6e084aa1dda7).
**breakdown**
```
for($s=$argn;               # import input
    ;                       # infinite loop
    $p?die(strtr($s,"()",")(")) # 2. if balanced: invert, print and exit
    :$s=substr($s,1).$s[$i=0]   #    else: rotate string, reset $i to 0
)                               # 1. test balance:
    for($p=1;                   # init $p to 1
        $p&&$c=$s[$i++];)       # loop through string while $p is >0
        $p-=$c<")"?:-1;             # increment $p for ")", decrement else
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~112~~ ~~103~~ 101 bytes
*-2 bytes thanks to @Mr.Xcoder*
```
k=y=input().translate(' '*40+')(')
while k:
 k=y=y[1:]+y[0]
 for _ in y:k=k.replace('()','')
print(y)
```
[Try it online!](https://tio.run/##LY7BCsIwEETv@Yqll@xaKRU9FfIX3kqRElcaEtIQUzRfH1PqaeYwb2ZCTsvqr0WvT1ZN0xSrsjI@bAmpS3H2bzcnRgnydOtbSShJfBbjGOwgYA/n8TJMbR77ScBrjfAA4yEPVtkucnCzrjSSPMtKhmh8wkylLv1r7nHj2gT8ZY37CyqIhERil6qHPQzSDw "Python 3 – Try It Online")
[Answer]
# Octave, 62 bytes
```
@(s)")("(x=hankel(s,shift(s,1))-39)(all(cumsum(2*x'-3)>=0)',:)
```
[Try it online!](https://tio.run/##DcxBDkAwFEXRvZj0PakEHZFUbOVHCFE1@Cp2Xx3d0bn38si75jxDWREVPr9LPNcAtbof21PakY0bCAkBS7o0XejrzzSOk29p7MgsUYsFwXLJPw "Octave – Try It Online")
A function that takes the string as input and prints all results.
**Explanation:**
```
           hankel(a,shift(a,1))                                % generate a matrix of n*n where n= length(s) and its rows contain incresing circulraly shifted s
         x=...                 -39                             % convert matrix of "(" and ")" to a mtrix of 1 and 2
    ")("(x                        )                            % switch the parens
                                               2*x'-3          % convert [1 2] to [-1 1]
                                        cumsum(      )         % cumulative sum along the rows
                                    all(              >=0)'    % if all >=0
                                   (                       ,:) % extract the desired rows
```
[Answer]
# Mathematica, 78 bytes
```
""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&
```
[Answer]
## JavaScript (ES6), 97 bytes
```
f=(s,t=s,u=t.replace(')(',''))=>u?t==u?f(s.slice(1)+s[0]):f(s,u):s.replace(/./g,c=>c<')'?')':'(')
```
Works by recursively rotating the input string until its transpose is balanced, then transposing it.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~35~~ 30 bytes
*Golfed a new approach thanks to @Adám*
```
1⌽⍣{2::0⋄1∊⍎⍕1,¨⍺}')('['()'⍳⎕]
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qKPd8b/ho569j3oXVxtZWRk86m4xfNTR9ai371HvVEOdQyse9e6qVdfUUI9W19BUf9S7@VHf1FiQtv@OXOoaGpoamprqXFAmkI3gQjhAPQA "APL (Dyalog Unicode) – Try It Online")
Golfing is in progress.
### Explanation
```
'()'⍳⎕              Find the index of each character of the input in the string '()'
                    (this is 1-indexed, so an input of '(())()' would give 1 1 2 2 1 2)
')('[...]           Find the index of the vector in the string ')('
                    This essentially swaps ')'s with '('s and vice versa
⍣                   On this new string, do:
 1⌽                   rotate it one to the left
                    Until this results in 1:
 1,¨⍺                 Concatenate each element of the argument with a 1
                      This inserts 1 one before each parenthesis
 ⍕                    Stringify it
 ⍎                    And evaluate it, if the parentheses are balanced, this produces no errors
 1∊                   Check if 1 belongs to evaluated value
                      If the parentheses were not matches during ⍎, this causes a syntax error
 2::0                 This catches a syntax error and returns 0
                      Essentially this code checks if the brackets are balanced or not
```
[Answer]
# [Python 2](https://docs.python.org/2/), 99 bytes
```
r=[0];S=''
for c in input():b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
n=r.index(min(r))
print S[n:]+S[:n]
```
[Try it online!](https://tio.run/##DcWxCgIxDADQvV/RLYlF0Rtb4k90DF16KnYwV0IP9OvrwYPXf@O96TKnsVxLygzgXpv51Tc99H0gxcrrHRCSBRaT862E5VSPUg4MhCC1OGW7NH08v/hpikbkujUdPovGErJELXMCIiER/AE "Python 2 – Try It Online")
## In function form for easy test cases:
## [Python 2](https://docs.python.org/2/), 108 bytes
```
def f(s):
 r=[0];S=''
 for c in s:b=c>'(';r+=[r[-1]+2*b-1];S+=')('[b]
 n=r.index(min(r))
 return S[n:]+S[:n]
```
[Try it online!](https://tio.run/##TY69DoJAEIT7e4rtdlfQKOWRo@QFrrxcw1@8woUsmOjTI0hMrGa@Zr6Z3st9lGJdu36AgWa2BtSFayy9QzQwjAotJIHZNq6tkLDUzAUN51vMilOzRekzh0wYmmhAnF6SdP2LHklImbe5fnmqgA9iY@aDlfiV1Yds0iQLzDm6CvP9gDE1IRETM/Kvb/DHB9HO6wc "Python 2 – Try It Online")
This uses a slightly different approach - instead of recursively rotating the string, if we think of the parens as incrementing and decrementing some balance counter, then a balanced string must never have a total sum of increments - decrements that is less than 0.
So we take
```
(()(())())
```
invert the parens:
```
))())(()((
```
and convert it to a list of sums of increments/decrements:
```
[-1,-2,-1,-2,-3,-2,-1,-2,-1,0]
```
-3 is the minimum at index 4 (zero based); so we want to shift by that index+1. This guarantees that the cumulative increment/decrement will never be less than 0; and will sum to 0.
[Answer]
## Clojure, 118 bytes
```
#(loop[s(map{\(\)\)\(}%)](let[s(conj(vec(rest s))(first s))](if(some neg?(reductions +(map{\( 1\) -1}s)))(recur s)s)))
```
Returns a sequence of characters, so I'd call it like this:
```
(apply str (f "(()(())())"))
; "(()(())())"
```
First flips brackets, then loops as long as the cumulative sum of bracket count goes negative at some point of the sequence.
[Answer]
# [brainfuck](https://github.com/TryItOnline/tio-transpilers), 82 bytes
```
,[++[->->++<<]-[--->+>-<<]>-->+[-[-<<+>>>>+<<]],]+[<<]>>>[.[-]>>]<[<<]<[<<]>>[.>>]
```
[Try it online!](https://tio.run/##JYlBCoBADAO/s0s3@4LSj4QeVBBE8CD4/tpqKGQ6We/luPZnOyMGRQiDiag6CCQakq2IaVTFMrX7cGFtZpxEtmv9@kvOFBGttd6/ewE "brainfuck – Try It Online")
### Explanation
With each character read, a counter is modified as follows:
* The counter starts at 0.
* After each `)`, the counter increases by 1.
* After each `(`, the counter decreases by 1, unless the counter was 0, in which case the counter is unchanged.
Each prefix is a valid suffix of a balanced string (after inversion) if and only if this counter is 0. This code uses the longest such prefix to form the output.
```
,[                   Take input and start main loop
                     The cell one space right is the output cell (0 at this point),
                     and two spaces right is a copy of the previous counter value
  ++                 Add 2 to input
  [->->++<<]         Negate into output cell, and add twice to counter
  -[--->+>-<<]       Add 85 to output cell, and subtract 85 from counter
  >-->+              Subtract 2 from output cell and add 1 to counter
                     The output cell now has (81-input), and the counter has been increased by (2*input-80)
  [-[-<<+>>>>+<<]]   If the counter is nonzero, decrement and copy
,]
+[<<]                Go to the last position at which the counter is zero
>>>                  Go to following output character
[.[-]>>]             Output from here to end, clearing everything on the way
                     (Only the first one needs to be cleared, but this way takes fewer bytes)
<[<<]                Return to the same zero
<[<<]>>              Go to beginning of string
[.>>]                Output remaining characters
```
]