Une chaîne équilibrée est une chaîne de parenthèses ()afin que chaque parenthèse puisse être mise en correspondance avec une autre. Plus rigoureusement, ce sont les chaînes couvertes par cette grammaire:

S → (S)S | ε

Nous pouvons transformer une chaîne "à l'envers" en:

• Commutation de toutes les occurrences de (et )entre elles

• Déplacement des caractères de l'avant de la chaîne vers l'arrière jusqu'à ce que la chaîne soit à nouveau équilibrée.

Faisons un exemple.

Nous commençons par la chaîne équilibrée:

(()(())())

On change ensuite les parens pour faire

))())(()((

Déplacez ensuite les caractères de l'avant de la chaîne vers l'arrière de la chaîne jusqu'à ce que la chaîne soit équilibrée.

))())(()((
)())(()(()
())(()(())
))(()(())(
)(()(())()
(()(())())

C'est notre résultat!

Notez que certaines chaînes peuvent être retournées de plusieurs manières, par exemple la chaîne

(()())

Lorsqu'elle est retournée, elle peut être:

()(())

ou

(())()

Cependant, chaque chaîne a au moins une solution .

Tâche

Écrivez un programme pour prendre une chaîne équilibrée comme entrée et sortie de cette chaîne retournée. Dans les cas où il peut y avoir plusieurs sorties valides, vous n'avez besoin que d'en sortir une seule. Vous pouvez utiliser un autre type d'accolade ( <>, []ou {}) si vous le souhaitez.

Il s'agit d'une compétition de code-golf , vous devez donc viser à minimiser la taille de votre code source, mesurée en octets.

Cas de test

(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))

Haskell , 124 120 119 117 113 110 109 106 105 104 101 98 bytes

4 octets économisés grâce à Bartavelle!

3 octets économisés grâce à Zgarb

1 octet sauvé grâce à Peter Taylor

Voici une solution que j'ai élaborée à Haskell. C'est ok en ce moment assez bien grâce à l'aide que j'ai reçue, mais je cherche à raccourcir ce point, donc les commentaires / suggestions sont appréciés.

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 _='('

Essayez-le en ligne!

Explication

Ce programme définit 4 fonctions, la première (!)détermine si une chaîne est équilibrée. Il est défini comme suit:

_!1=1<0
('(':a)!x=a!(x-1)
(_:a)!x=a!(x+1)
_!_=1>0

Cette vérification suppose que l'entrée a un nombre égal de parens ouverts et fermés grâce à une suggestion de Peter Taylor.

Le suivant gfera tourner la chaîne une fois.

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

Ensuite, nous avons dqui prend simplement un paren et le reflète

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

Enfin, nous avons la fonction qui nous intéresse. Ici, nous utilisons une représentation sans point de until(!0)gcomposée avec map d, qui correspond dà l'entrée et s'applique gjusqu'à ce que le résultat soit équilibré. C'est le processus exact décrit dans la question.

until(!0)g.map d

SOGL V0.12 , 12 11 octets

↔]»:l{Ƨ()øŗ

Essayez-le ici!

Explication:

↔            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

Remarque: l{pourrait être remplacé par ( pour 10 octets, mais, malheureusement, il n'est pas implémenté.

CJam (20 caractères)

q1f^0X${~_}%_:e>#)m<

Démo en ligne

ou pour le même nombre de caractères

q1f^_,,{0W$@<~}$W=m<

Démo en ligne

Dissection

Les deux versions ont un en-tête et un pied de page communs

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

Ensuite, le bit au milieu calcule évidemment jusqu'à quel point il est nécessaire de tourner. Les deux utilisent l'évaluation et dépendent de (l'opérateur de décrémentation CJam et de )l'opérateur d'incrémentation.

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

contre

_,,     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

JavaScript (ES6), 111 105 octets

(Enregistré 2 octets grâce à @CraigAyre, 2 octets grâce à @PeterTaylor, 2 octets grâce à @Shaggy.)

s=>(r=[...s].map(c=>'()'[c<')'|0])).some(_=>r.push(r.shift(i=0))&&!r.some(c=>(i+=c<')'||-1)<0))&&r.join``

Non golfé:

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``
)

Cas de test:

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('((())())()'));  // (()(()()))

Rétine , 46 38 octets

T`()`)(
(.*?)(((\()|(?<-4>\)))+)$
$2$1

Essayez-le en ligne! Le lien inclut des cas de test. Edit: 8 octets enregistrés avec l'aide de @MartinEnder. La première étape transpose simplement les parenthèses, tandis que la deuxième étape recherche le suffixe le plus long qui est un préfixe équilibré valide, ce qui est apparemment une condition suffisante pour que la rotation soit entièrement équilibrée. L'équilibrage est détecté à l'aide de groupes d'équilibrage. La construction ((\()|(?<-4>\)))+correspond à n'importe quel nombre de (s plus n'importe quel nombre de )s tant que nous avons déjà <-4>vu ( ) autant de (s. Puisque nous ne recherchons qu'un préfixe valide, nous n'avons pas à faire correspondre les )s restants .

PHP, 110 108 octets

for($s=$argn;;$p?die(strtr($s,"()",")(")):$s=substr($s,1).$s[$i=0])for($p=1;$p&&$c=$s[$i++];)$p-=$c<")"?:-1;

Exécuter en tant que pipe avec -nRou tester en ligne .

panne

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

Python 3 , 112 103 101 101 octets

-2 octets grâce à @ Mr.Xcoder

k=y=input().translate(' '*40+')(')
while k:
 k=y=y[1:]+y[0]
 for _ in y:k=k.replace('()','')
print(y)

Essayez-le en ligne!

Octave, 62 octets

@(s)")("(x=hankel(s,shift(s,1))-39)(all(cumsum(2*x'-3)>=0)',:)

Essayez-le en ligne!

Une fonction qui prend la chaîne en entrée et imprime tous les résultats.

Explication:

           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

Mathematica, 78 octets

""<>{"(",")"}[[2ToCharacterCode@#-81//.x_/;Min@Accumulate@x<0:>RotateLeft@x]]&

JavaScript (ES6), 97 octets

f=(s,t=s,u=t.replace(')(',''))=>u?t==u?f(s.slice(1)+s[0]):f(s,u):s.replace(/./g,c=>c<')'?')':'(')

Fonctionne en tournant récursivement la chaîne d'entrée jusqu'à ce que sa transposition soit équilibrée, puis en la transposant.

APL (Dyalog Unicode) , 35 30 octets

Golfé une nouvelle approche grâce à @ Adám

1⌽⍣{2::0⋄1∊⍎⍕1,¨⍺}')('['()'⍳⎕]

Essayez-le en ligne!

Le golf est en cours.

Explication

'()'⍳⎕              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

Python 2 , 99 octets

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]

Essayez-le en ligne!

Sous forme de fonction pour des cas de test faciles:

Python 2 , 108 octets

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]

Essayez-le en ligne!

Cela utilise une approche légèrement différente - au lieu de tourner récursivement la chaîne, si nous considérons les parens comme incrémentant et décrémentant un compteur d'équilibre, une chaîne équilibrée ne doit jamais avoir une somme totale d'incréments - des décréments inférieurs à 0.

Nous prenons donc

(()(())())

inverser les parens:

))())(()((

et le convertir en une liste de sommes d'incréments / décréments:

[-1,-2,-1,-2,-3,-2,-1,-2,-1,0]

-3 est le minimum à l'indice 4 (basé sur zéro); nous voulons donc décaler par cet indice + 1. Cela garantit que l'incrément / décrément cumulatif ne sera jamais inférieur à 0; et sera égal à 0.

Clojure, 118 octets

#(loop[s(map{\(\)\)\(}%)](let[s(conj(vec(rest s))(first s))](if(some neg?(reductions +(map{\( 1\) -1}s)))(recur s)s)))

Renvoie une séquence de caractères, donc je l'appellerais comme ceci:

(apply str (f "(()(())())"))
; "(()(())())"

Retourne d'abord les crochets, puis boucle tant que la somme cumulée du nombre de crochets devient négative à un certain point de la séquence.

brainfuck , 82 octets

,[++[->->++<<]-[--->+>-<<]>-->+[-[-<<+>>>>+<<]],]+[<<]>>>[.[-]>>]<[<<]<[<<]>>[.>>]

Essayez-le en ligne!

Explication

A chaque lecture de caractère, un compteur est modifié comme suit:

• Le compteur démarre à 0.
• Après chacun ), le compteur augmente de 1.
• Après chacun (, le compteur diminue de 1, sauf s'il était égal à 0, auquel cas le compteur est inchangé.

Chaque préfixe est un suffixe valide d'une chaîne équilibrée (après inversion) si et seulement si ce compteur est 0. Ce code utilise le préfixe le plus long pour former la sortie.

,[                   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