Selesai kurung malas

17

Tanda kurung pada keyboard saya sudah usang, dan saya ingin menghindari menggunakannya sebanyak mungkin. Tantangan Anda adalah menyeimbangkan garis yang mengandung tanda kurung dengan menambahkannya sebelum dan sesudah setiap baris.

Ini mirip dengan kurung otomatis TI-Basic dan penutupan string (yaitu Output(1, 1, "Hello, World!). Ini juga menghemat byte berharga dari suatu program!

Input contoh:

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

Contoh (mungkin) keluaran:

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

Spesifikasi:

  • Untuk setiap jalur input,

    • Tambahkan sebanyak mungkin tanda kurung ke awal dan tutup tanda kurung ke akhir baris sesuai kebutuhan untuk menyeimbangkan tanda kurung di baris

      • Definisi "keseimbangan" adalah:

        • Jumlah yang sama (dan )sesuai

        • Untuk setiap substring mulai dari awal string, substring ini tidak boleh memiliki lebih banyak kurung tutup daripada membuka tanda kurung

          • Misalnya, (foo))(bartidak seimbang karena (foo))memiliki lebih banyak kurung tutup daripada membuka kurung
    • Anda dapat menambahkan tanda kurung tambahan yang tidak perlu jika Anda mau, jika itu membuat kode Anda lebih pendek

    • Anda tidak perlu khawatir tentang string literal atau semacamnya, asumsikan bahwa semua tanda kurung perlu diseimbangkan

  • Keluarkan setiap baris dengan tanda kurung seimbang

Ini adalah , jadi kode terpendek dalam byte akan menang!

Gagang pintu
sumber
Apakah Anda hanya peduli () parens, atau melakukan kurung lainnya {}, [], <>, dll perlu dipertimbangkan juga?
Trauma Digital
@DigitalTrauma Tidak, hanya (dan) .
Gagang Pintu
Apakah Anda memiliki test case?
Peter Taylor
1
@ Peter Ya, mereka ada di pos itu ...
Gagang Pintu

Jawaban:

21

GolfScript, 23 byte

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

Celah yang saya eksploitasi adalah aturan bahwa:

Anda dapat menambahkan tanda kurung tambahan yang tidak perlu jika Anda mau, jika itu membuat kode Anda lebih pendek

Pada dasarnya, untuk setiap baris, kode ini menghitung jumlah karakter pada baris yang tidak membuka tanda kurung, dan menambahkan banyak tanda kurung pembuka tambahan ke baris, dan kemudian melakukan hal yang sama untuk menutup tanda kurung. Ini sangat tidak efisien, tetapi memastikan bahwa semua tanda kurung pada garis keluaran seimbang.

Misalnya, diberi input:

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

program ini akan menampilkan:

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

Ps. Anda juga bisa menguji kode ini secara online .

Ilmari Karonen
sumber
4
Ini mengingatkan saya ketika saya dulu memprogram di Lisp ... Beberapa bit kode hilang dalam lautan tanda kurung.
Taconut
7

Perl, 32 = 31 + 1 atau 73 = 72 + 1 (kurung diminimalkan)

32 = 31 + 1: dengan kurung tambahan yang tidak perlu

Suntingan:

  • Perbaiki, tanda kurung sekarang dihitung dengan y/// .
  • Variabel yang tidak perlu $adihapus.
$_="("x y/)//.s|$|")"x y/(//|er

Ini digunakan dengan saklar run-time -p (+1 byte).

File uji input.txt:

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

Garis komando:

perl -p script.pl <input.txt

atau

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

Hasil:

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

Tidak Disatukan:

Algoritma ini sederhana, cukup tambahkan rekanan untuk setiap kurung yang ditemukan.

$_ =                     # $_ 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: menambah jumlah kurung minimum

Skrip ini hanya menambahkan jumlah tanda kurung minimum untuk mendapatkan hasil yang seimbang.

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

Ini digunakan dengan sakelar run-time-p (+1 byte).

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

Hasil:

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

Tidak Disatukan:

$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: menambahkan jumlah kurung minimum

Ini adalah metode yang lebih lama untuk menambahkan jumlah kurung minimum untuk hasil yang seimbang.

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

Ini menggunakan Perl 5.14 (karena pengubah substitusi non-destruktif) dan saklar run-time -p(+1 byte).

perl -p script.pl <input.txt

Hasil:

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

Tidak Disatukan:

# 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";
}
Heiko Oberdiek
sumber
2
Wow, itu hampir terlihat seperti skrip golf ;-)
Digital Trauma
@ HeikoOberdiek Apa perl yang Anda gunakan untuk versi pertama? Tampaknya tidak berfungsi pada 18.1 karena '('x/\)/gselalu sama dengan '(' ...
Mouq
@Mouq: Terima kasih, perbaiki sekarang menggunakan y///alih-alih m//guntuk menghitung tanda kurung.
Heiko Oberdiek
4

Python 2.7 3: 62 60 58 byte

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

Bukan super golf, tapi Anda tahu. Saya mungkin dapat memeras beberapa byte lagi jika saya benar-benar mencoba.

Untuk setiap baris, output (* jumlah )dalam baris, lalu baris, kemudian )* jumlah( di baris. Jika saya memahami aturan dengan benar, ini akan selalu memberikan hasil yang valid.

Keluar dengan melemparkan pengecualian, sebagai hasil dari cara saya melakukan input. (Input selalu merupakan bagian yang sulit dari masalah ini.) Jika ini tidak dapat diterima, saya akan perlu beberapa byte untuk memperbaikinya, meskipun saya belum yakin berapa banyak.

Contoh output:

This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
monmon bawah tanah
sumber
Ini tampaknya tidak mengambil input multiline, yaitu cetakan diselingi dengan garis input. Tapi ide algoritma yang bagus, saya tidak memikirkan itu;)
Gagang Pintu
python2 balanced_parenthesis.py < input.txt 2>/dev/nullmendapatkan output yang saya tulis tetapi jika Anda ingin input multiline saat melakukannya secara interaktif akan dikenakan biaya beberapa byte. Beri aku waktu sebentar, aku akan memikirkan sesuatu ...
undergroundmonorail
Ah, oke, sudahlah. Itu akan bekerja!
Gagang Pintu
Hemat 2 karakter:while 1:s=raw_input();c=s.count;print'('*c(')')+s+')'*c('(')
Justin
@qui Oh, wow. Saya hampir saja menemukan jawabannya, tetapi saya tidak sadar Anda bisa melakukannya c=s.count. Saya pikir Anda harus melakukan c=s, s.c(). Terima kasih!
undergroundmonorail
1

Bash Murni, 72 byte

Menggunakan algoritme yang sama dengan jawaban @ undergroundmonorail:

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

Keluaran:

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