Os parênteses no meu teclado estão todos gastos e eu quero evitar usá-los o máximo possível. Seu desafio é equilibrar uma linha contendo parênteses, adicionando-os antes e depois de cada linha.

Isso é semelhante aos parênteses automáticos do TI-Basic e ao fechamento de cadeias (ou seja Output(1, 1, "Hello, World!). Ele também salva bytes preciosos de um programa!

Exemplo de entrada:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

Exemplo de saída (possível):

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()

Especificação:

• Para cada linha de entrada,

  • Adicione tantos parênteses abertos ao começo e feche parênteses ao final da linha conforme necessário para equilibrar os parênteses na linha

    • A definição de "saldo" é:

      • Mesma quantidade de (e )na linha

      • Para cada substring começando no início da string, esse substring não deve ter mais parênteses de fechamento do que parênteses de abertura

        • Por exemplo, (foo))(barnão é equilibrado porque (foo))tem mais parênteses de fechamento do que parênteses de abertura

  • Você pode adicionar parênteses extras desnecessários, se desejar, se o código for mais curto

  • Você não precisa se preocupar com literais de seqüência de caracteres ou algo assim, suponha que todos os parênteses precisem ser balanceados

• Saída de cada linha com parênteses balanceados

Isso é código-golfe , então o código mais curto em bytes vencerá!

GolfScript, 23 bytes

n/{"()"1/{.2$\-,*}%*n}/

A brecha que estou explorando é a decisão de que:

Você pode adicionar parênteses extras desnecessários, se desejar, se o código for mais curto

Basicamente, para cada linha, esse código conta o número de caracteres na linha que não estão abrindo parênteses e precede muitos parênteses de abertura extras à linha e, em seguida, faz o mesmo para fechar parênteses. Isso é incrivelmente ineficiente, mas garante que todos os parênteses na linha de saída estejam equilibrados.

Por exemplo, dada a entrada:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

este programa produzirá:

((((((((((((((((((((((((((((This line has no parentheses))))))))))))))))))))))))))))
(((((((((((((((((alert(Math.max(1, 2)))))))))))))))))))
(((((((((((((((((1+1)*2).toString())))))))))))))))
(((((((((((((((((((((((((((((((((((((function() { alert('Hello, World!'); })()))))))))))))))))))))))))))))))))))))

Ps. Você também pode testar esse código online .

Perl, 32 = 31 + 1 ou 73 = 72 + 1 (parênteses minimizados)

32 = 31 + 1: com parênteses desnecessários extras

Editar% s:

• Correção, parênteses agora contados y///.
• Variável desnecessária $aremovida.

$_="("x y/)//.s|$|")"x y/(//|er

É usado com a opção de tempo de execução -p(+1 byte).

Arquivo de teste input.txt:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(
(foo))(bar
)))(((
((
))

Linha de comando:

perl -p script.pl <input.txt

ou

perl -pe '$_="("x y/)//.s|$|")"x y/(//|er' <input.txt

Resultado:

This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
(((foo))(bar))
((()))((()))
(())
(())

Ungolfed:

O algoritmo é simples, basta adicionar a contrapartida para cada parêntese encontrado.

$_ =                     # $_ is provided as input by switch `-p` and
                         # it is printed afterwards as output.
                         # y/X// is used to count the character 'X' in $_
    '(' x y/)//          # add opening parentheses for each closing parentheses
    . s|$|')' x y/(//|er # go right before the end of line and insert
                         # closing parentheses for each opening parentheses
                         # in the original string

73 = 72 + 1: adicionando número mínimo de parênteses

Este script adiciona apenas o número mínimo de parênteses para obter uma saída equilibrada.

$a=y/()//cdr;1while$a=~s/\(\)//g;$_=$a=~y/)(/(/dr.$_;s|$|$a=~y/()/)/dr|e

É usado com a opção de tempo de execução -p(+1 byte).

perl -pe "$a=y/()//cdr;1while$a=~s/\(\)//g;$_=$a=~y/)(/(/dr.$_;s|$|$a=~y/()/)/dr|e" <input.txt

Resultado:

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()
((foo))(bar)
((()))((()))
(())
(())

Ungolfed:

$a = y/()//cdr;            # filter parentheses and store in $a
1 while $a =~ s/\(\)//g;   # remove matching parentheses
$_ = $a =~ y/)(/(/dr . $_; # add missing opening parentheses at start of string
s|$|$a=~y/()/)/dr|e        # insert missing closing parentheses at end of string

81 = 80 + 1: adicionando número mínimo de parênteses

Este é um método mais antigo para adicionar o número mínimo de parênteses para uma saída balanceada.

my($l,$r);s/[()]/($&eq")"&&($r&&$r--||++$l))||$r++/ger;$_="("x$l.$_;s/$/")"x$r/e

Ele usa Perl 5.14 (por causa do modificador de substituição não destrutivo) e o comutador de tempo de execução -p(+1 byte).

perl -p script.pl <input.txt

Resultado:

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()
((foo))(bar)
((()))((()))
(())
(())

Ungolfed:

# The while loop is added by option "-p".
LINE:
while (<>) {

    # $_ contains the current line
    my ($l, $r); # initializes $l and $r (to undef/kind of indirect 0)
    # Modifiers for the following substitution of $_:
    # /g: process all parentheses
    # /e: evaluate code
    # /r: does not change the original input string $_ (Perl 5.14)
    s/[()]/
        # $& contains the matched parentheses
        # $r is a balance level counter; at the end $r contains
        #    the number of needed closing parentheses
        # $l is the number of needed opening parentheses;
        #    if $r would go negative, then an opening parentheses
        #    is missing and $l is increases and $r remains zero.
        (  
            $& eq ")" &&   # case ")"
            ($r && $r--    # close a parentheses group and update balance counter
                || ++$l)   # or update $l if an opening parentheses is needed
        )
        || $r++            # case "(": increase balance counter
    /ger;
    $_ = "(" x $l . $_;    # add opening parentheses at the begin of line
    s/$/")" x $r/e         # add closing parentheses before the line end

# the remainder is added by run-time switch "-p"
} continue {
    print or die "-p destination: $!\n";
}

Python 2.7 3: 62 60 58 bytes

while 1:s=input();c=s.count;print('('*c(')')+s+')'*c('('))

Não é super golfista, mas você sabe. Talvez eu consiga extrair mais bytes se realmente tentei.

Para cada linha, gera (* o número de )na linha, depois a linha, e )* o número de (na linha. Se eu entender as regras corretamente, isso sempre fornecerá uma saída válida.

Sai lançando uma exceção, como resultado da maneira como inseri. (A entrada é sempre uma parte difícil desses problemas.) Se isso não for aceitável, custará alguns bytes para corrigir, embora ainda não tenha certeza de quantos.

Exemplo de saída:

This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))

Pure Bash, 72 bytes

Usa o mesmo algoritmo da resposta do @ undergroundmonorail:

while read a;do
o=${a//[!(]}
c=${a//[!)]}
echo ${c//)/(}$a${o//(/)}
done

Resultado:

$ ./lazyparens.sh < input.txt
This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
$