Uma cadeia equilibrada é uma cadeia de parênteses ()para que todos os parênteses sejam encontrados com outro. Mais rigorosamente, são as cadeias abrangidas por esta gramática:

S → (S)S | ε

Podemos transformar uma string "de dentro para fora":

• Alternando todas as ocorrências (e )entre si

• Movendo caracteres da frente da string para trás até que a string seja equilibrada novamente.

Vamos fazer um exemplo.

Começamos com a string balanceada:

(()(())())

Em seguida, trocamos os parênteses para fazer

))())(()((

Em seguida, mova os caracteres da frente da cadeia para a parte de trás da cadeia até que ela esteja equilibrada.

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

Esse é o nosso resultado!

Observe que algumas seqüências de caracteres podem ser viradas do avesso de várias maneiras, por exemplo, a sequência

(()())

Quando virado do avesso, pode ser:

()(())

ou

(())()

No entanto, cada string tem pelo menos uma solução .

Tarefa

Escreva um programa para pegar uma string equilibrada como entrada e saída dessa string virada do avesso. Nos casos em que pode haver várias saídas válidas, você precisa apenas produzir uma delas. Você pode usar um tipo de chave diferente ( <>, []ou {}) se desejar.

Como é uma competição de código-golfe , você deve minimizar o tamanho do seu código-fonte, medido por bytes.

Casos de teste

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

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

4 bytes salvos graças ao bartavelle!

3 bytes salvos graças ao Zgarb

1 byte salvo graças a Peter Taylor

Aqui está uma solução que eu trabalhei em Haskell. Está tudo bem no momento, muito bom, graças a alguma ajuda que recebi, mas estou procurando diminuir isso, para que comentários / sugestões sejam apreciados.

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

Experimente online!

Explicação

Este programa define 4 funções, a primeira (!)determina se uma string é balanceada. É definido da seguinte forma:

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

Essa verificação pressupõe que a entrada tenha um número igual de parênteses de abertura e fechamento, graças a uma sugestão de Peter Taylor.

O próximo ggirará a corda uma vez.

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

Então nós temos o dque simplesmente pega um parênteses e o espelha

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

Finalmente, temos a função com a qual estamos preocupados. Aqui, usamos uma representação sem ponto de until(!0)gcomposta com map d, que mapeia da entrada e se aplica gaté que o resultado seja equilibrado. Este é o processo exato descrito na pergunta.

until(!0)g.map d

SOGL V0.12 , 12 11 bytes

↔]»:l{Ƨ()øŗ

Experimente aqui!

Explicação:

↔            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{pode ser substituído por ( por 10 bytes, mas, infelizmente, não é implementado.

CJam (20 caracteres)

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

Demonstração online

ou para a mesma contagem de caracteres

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

Demonstração online

Dissecação

As duas versões têm um cabeçalho e rodapé comuns

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

Então, o bit no meio obviamente calcula até onde é necessário girar. Ambos usam avaliação e dependem de (ser o operador de decremento do CJam e de )serem o 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 105 bytes

(Economizou 2 bytes graças a @CraigAyre, 2 bytes graças a @PeterTaylor, 2 bytes graças 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``

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

Casos de teste:

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

Experimente online! O link inclui casos de teste. Editar: salvou 8 bytes com a ajuda de @MartinEnder. O primeiro estágio simplesmente transpõe os parênteses, enquanto o segundo estágio procura o sufixo mais longo, que é um prefixo balanceado válido, o que aparentemente é uma condição suficiente para que a rotação seja totalmente balanceada. O balanceamento é detectado usando grupos de balanceamento. A construção ((\()|(?<-4>\)))+corresponde a qualquer número de (s mais qualquer número de )s, desde que já tenhamos <-4>visto ( ) tantos (s. Como procuramos apenas um prefixo válido, não precisamos corresponder ao restante) s .

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;

Executar como tubo com -nRou teste-o online .

demolir

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 graças a @ Mr.Xcoder

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

Experimente online!

Oitava, 62 bytes

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

Experimente online!

Uma função que recebe a string como entrada e imprime todos os resultados.

Explicação:

           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 a sequência de entrada até que sua transposição seja equilibrada e depois a transponha.

APL (Dyalog Unicode) , 35 30 bytes

Golfou uma nova abordagem graças a @ Adám

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

Experimente online!

O golfe está em andamento.

Explicação

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

Experimente online!

Em formato de função para casos de teste fáceis:

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]

Experimente online!

Isso usa uma abordagem um pouco diferente - em vez de girar recursivamente a string, se considerarmos os parênteses como incrementando e diminuindo algum contador de balança, uma string balanceada nunca deve ter uma soma total de incrementos - decrementos menores que 0.

Então pegamos

(()(())())

inverter as parênteses:

))())(()((

e converta-o em uma lista de somas de incrementos / decrementos:

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

-3 é o mínimo no índice 4 (baseado em zero); então queremos mudar por esse índice + 1. Isso garante que o incremento / decremento acumulado nunca será menor que 0; e será somado 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)))

Retorna uma sequência de caracteres, então eu chamaria assim:

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

Primeiro vira colchetes e depois faz um loop enquanto a soma acumulada da contagem de colchetes for negativa em algum ponto da sequência.

brainfuck , 82 bytes

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

Experimente online!

Explicação

Com cada caractere lido, um contador é modificado da seguinte maneira:

• O contador começa em 0.
• Após cada um ), o contador aumenta em 1.
• Após cada um (, o contador diminui em 1, a menos que o contador seja 0; nesse caso, o contador permanece inalterado.

Cada prefixo é um sufixo válido de uma string balanceada (após inversão) se e somente se esse contador for 0. Esse código usa o prefixo mais longo para formar a saída.

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