Una cadena equilibrada es una cadena de paréntesis ()para que cada paréntesis se pueda combinar con otro. Más rigurosamente son las cadenas que abarca esta gramática:

S → (S)S | ε

Podemos convertir una cadena "de adentro hacia afuera" de la siguiente manera:

• Cambio de todas las apariciones de (y )con los demás

• Mover caracteres desde el frente de la cadena hacia atrás hasta que la cadena se equilibre nuevamente.

Hagamos un ejemplo.

Comenzamos con la cadena equilibrada:

(()(())())

Luego cambiamos los parens para hacer

))())(()((

Luego mueva los caracteres desde el frente de la cadena hasta la parte posterior de la cadena hasta que la cadena esté equilibrada.

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

Ese es nuestro resultado!

Tenga en cuenta que algunas cadenas pueden invertirse de varias maneras, por ejemplo, la cadena

(()())

Cuando se da la vuelta al revés puede ser:

()(())

o

(())()

Sin embargo, cada cadena tiene al menos una solución .

Tarea

Escriba un programa para tomar una cadena equilibrada como entrada y salida de esa cadena al revés. En los casos en que puede haber múltiples salidas válidas, solo necesita una de ellas. Puede usar un tipo de llave diferente ( <>, []o {}) si lo desea.

Esta es una competencia de código de golf , por lo que debe intentar minimizar el tamaño de su código fuente, medido por bytes.

Casos de prueba

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

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

¡4 bytes guardados gracias a bartavelle!

3 bytes guardados gracias a Zgarb

1 byte guardado gracias a Peter Taylor

Aquí hay una solución que resolví en Haskell. Está bien en este momento bastante bien gracias a la ayuda que recibí, pero estoy tratando de acortar esto, por lo que agradecemos sus comentarios / sugerencias.

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

Pruébalo en línea!

Explicación

Este programa define 4 funciones, la primera (!)determina si una cadena está equilibrada. Se define de la siguiente manera:

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

Esta verificación asume que la entrada tiene el mismo número de pares abiertos y cerrados gracias a una sugerencia de Peter Taylor.

El siguiente grotará la cadena una vez.

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

Luego tenemos dque simplemente toma un par y lo refleja

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

Finalmente tenemos la función que nos preocupa. Aquí usamos una representación de until(!0)gcompuesto con punto libre map d, que se asigna da la entrada y se aplica ghasta que el resultado esté equilibrado. Este es el proceso exacto descrito en la pregunta.

until(!0)g.map d

SOGL V0.12 , 12 11 bytes

↔]»:l{Ƨ()øŗ

Pruébalo aquí!

Explicación:

↔            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

Nota: l{podría reemplazarse por ( para 10 bytes, pero, lamentablemente, no está implementado.

CJam (20 caracteres)

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

Demostración en línea

o por el mismo recuento de char

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

Demostración en línea

Disección

Las dos versiones tienen un encabezado y pie de página en común.

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

Luego, el bit en el medio obviamente calcula qué tan lejos es necesario rotar. Ambos utilizan la evaluación y confían en (ser el operador de decremento CJam y )ser el operador de incremento.

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

JavaScript (ES6), 111 bytes

(Ahorró 2 bytes gracias a @CraigAyre, 2 bytes gracias a @PeterTaylor, 2 bytes gracias a @Shaggy.)

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

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

Casos de prueba:

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

Retina , 46 38 bytes

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

Pruébalo en línea! El enlace incluye casos de prueba. Editar: guardado 8 bytes con ayuda de @MartinEnder. La primera etapa simplemente transpone los paréntesis, mientras que la segunda etapa busca el sufijo más largo que es un prefijo equilibrado válido, que aparentemente es una condición suficiente para que la rotación esté completamente equilibrada. El equilibrio se detecta mediante grupos de equilibrio. La construcción ((\()|(?<-4>\)))+coincide con cualquier número de (s más cualquier número de )s siempre que ya hayamos ( <-4>) visto tantos (s. Como solo estamos buscando un prefijo válido, no tenemos que coincidir con los )s restantes .

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;

Ejecutar como tubería con -nRo probarlo en línea .

Descompostura

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 bytes

-2 bytes gracias a @ Mr.Xcoder

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

Pruébalo en línea!

Octava, 62 bytes

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

Pruébalo en línea!

Una función que toma la cadena como entrada e imprime todos los resultados.

Explicación:

           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 bytes

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

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<')'?')':'(')

Funciona girando recursivamente la cadena de entrada hasta que su transposición esté equilibrada y luego transponiéndola.

APL (Dyalog Unicode) , 35 30 bytes

Golfed un nuevo enfoque gracias a @ Adám

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

Pruébalo en línea!

El golf está en progreso.

Explicación

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

Pruébalo en línea!

En forma de función para casos de prueba fáciles:

Python 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]

Pruébalo en línea!

Esto utiliza un enfoque ligeramente diferente: en lugar de rotar recursivamente la cadena, si consideramos que los elementos parentales aumentan y disminuyen algún contador de equilibrio, una cadena equilibrada nunca debe tener una suma total de incrementos, decrementos que son menores que 0.

Entonces tomamos

(()(())())

invertir los parens:

))())(()((

y conviértalo en una lista de sumas de incrementos / decrementos:

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

-3 es el mínimo en el índice 4 (basado en cero); entonces queremos cambiar por ese índice + 1. Esto garantiza que el incremento / decremento acumulativo nunca será menor que 0; y sumará a 0.

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

Devuelve una secuencia de caracteres, así que lo llamaría así:

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

Primero voltea los corchetes, luego realiza un bucle siempre que la suma acumulada del recuento de corchetes sea negativa en algún punto de la secuencia.

brainfuck , 82 bytes

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

Pruébalo en línea!

Explicación

Con cada carácter leído, un contador se modifica de la siguiente manera:

• El contador comienza en 0.
• Después de cada uno ), el contador aumenta en 1.
• Después de cada uno (, el contador disminuye en 1, a menos que el contador fuera 0, en cuyo caso el contador no cambia.

Cada prefijo es un sufijo válido de una cadena equilibrada (después de la inversión) si y solo si este contador es 0. Este código usa el prefijo más largo para formar la salida.

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