Balikkan string ke dalam

21

String seimbang adalah string tanda kurung ()sehingga setiap tanda kurung dapat dicocokkan dengan yang lain. Lebih tepatnya mereka adalah string yang direntang oleh tata bahasa ini:

S → (S)S | ε

Kita dapat mengubah string "dalam ke luar" dengan:

  • Mengganti semua kejadian dari (dan )dengan satu sama lain

  • Memindahkan karakter dari depan string ke belakang hingga string seimbang kembali.


Mari kita lakukan sebuah contoh.

Kami mulai dengan string seimbang:

(()(())())

Kami kemudian beralih ke parens untuk membuat

))())(()((

Kemudian pindahkan karakter dari depan string ke belakang string sampai string seimbang.

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

Itulah hasil kami!


Perhatikan bahwa beberapa string dapat dibalik keluar dengan berbagai cara, misalnya string

(()())

Ketika dibalik-balik bisa berupa:

()(())

atau

(())()

Namun setiap string memiliki setidaknya satu solusi .

Tugas

Tulis sebuah program untuk mengambil string seimbang sebagai input dan output string yang terbalik. Dalam kasus di mana mungkin ada beberapa output yang valid, Anda hanya perlu menampilkan salah satu dari mereka. Anda dapat menggunakan jenis kurung yang berbeda ( <>, []atau {}) jika diinginkan.

Ini adalah kompetisi sehingga Anda harus berusaha meminimalkan ukuran kode sumber Anda, yang diukur dengan byte.

Uji Kasus

(()())     -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
Wisaya Gandum
sumber
Apakah dijamin selalu ada solusinya?
Luis Mendo
@LuisMendo Ya, saya telah membuktikan ini. Jika Anda ingin melihat buktinya, silakan ping saya di obrolan.
Wheat Wizard
Terima kasih. Cukup bagi saya untuk mengetahui hal itu. Mungkin Anda harus menuliskannya dalam tantangan, jika tidak, Anda harus menentukan apa yang akan dihasilkan jika tidak ada solusi
Luis Mendo
terkait
officialaimm

Jawaban:

9

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

4 byte disimpan berkat bartavelle!

3 byte disimpan berkat Zgarb

1 byte disimpan berkat Peter Taylor

Inilah solusi yang saya kerjakan di Haskell. Tidak apa-apa sekarang cukup baik berkat bantuan yang saya terima, tapi saya ingin membuat ini lebih pendek, jadi umpan balik / saran sangat dihargai.

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

Cobalah online!

Penjelasan

Program ini mendefinisikan 4 fungsi, yang pertama (!)menentukan apakah string seimbang. Yang didefinisikan sebagai berikut:

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

Pemeriksaan ini mengasumsikan bahwa input memiliki jumlah paren buka dan tutup yang sama berkat saran dari Peter Taylor.

Selanjutnya gakan memutar string sekali.

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

Kemudian kita memiliki dyang hanya mengambil paren dan mencerminkannya

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

Akhirnya kita memiliki fungsi yang menjadi perhatian kita. Di sini kami menggunakan representasi pointfree yang until(!0)gdibuat dengan map d, yang memetakan dke input dan berlaku ghingga hasilnya seimbang. Ini adalah proses persis yang dijelaskan dalam pertanyaan.

until(!0)g.map d
Wisaya Gandum
sumber
1
Anda dapat memo beberapa byte dengan g x@(a:b)|x!0=x|1>0=g$b++[a]dan menghapus parens untuk d '('=')'.
bartavelle
@ Bartavelle Menghapus parens untuk dmenyebabkan kesalahan kompiler, percayalah, saya sudah mencoba. Tapi saran pertama diterima. Terima kasih!
Wheat Wizard
1
Anda dapat menyimpan byte lain di dalam !karena Anda tidak perlu menangani case di mana string memiliki jumlah tanda kurung buka dan tutup yang tidak sama, sehingga Anda dapat menukar dua case pertama dan memilikinya_!1=1<0 []!_=0<1
Peter Taylor
1
Gunakan untiluntuk mempersingkat g: TIO
Zgarb
2
Saya pikir harus ada penghematan yang layak dengan membuat dpeta '('ke (-1)dan apa pun yang lain 1, dan kemudian dua kasus terpanjang !dapat digabungkan (i:a)!x=a!(x+i). Struktur tingkat atas kemudian perlu dikerjakan ulang untuk mendorong map dke dalam untilkondisi, dan saya harus berlari sehingga saya tidak punya waktu sekarang untuk mencari tahu apa yang diperlukan kombinator untuk merekatkan semuanya.
Peter Taylor
7

SOGL V0.12 , 12 11 byte

↔]»:l{Ƨ()øŗ

Coba Di Sini!

Penjelasan:

↔            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

Catatan: l{dapat diganti dengan ( untuk 10 byte, tetapi, sayangnya, itu tidak diterapkan.

dzaima
sumber
Apakah Anda yakin bahwa mirroring karakter berfungsi? Saya tidak tahu persis apa artinya itu, tetapi intuisi saya mengatakan bahwa itu juga membalik urutan karakter yang, saya pikir tidak akan berhasil.
Wheat Wizard
1
@Olmman Hal itu dimaksudkan untuk membalikkan karakter, tetapi tidak (yang menyimpan byte di sini!). Ada pada line-up V0.13 untuk mengubah palung. Contoh
dzaima
5

CJam (20 karakter)

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

Demo online

atau untuk jumlah char yang sama

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

Demo online

Pembedahan

Kedua versi memiliki header dan footer yang sama

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

Kemudian bit di tengah jelas menghitung seberapa jauh perlu diputar. Keduanya menggunakan evaluasi dan mengandalkan (menjadi operator penurunan CJam dan )menjadi operator kenaikan.

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
Peter Taylor
sumber
3

JavaScript (ES6), 111 105 byte

(Disimpan 2 byte berkat @CraigAyre, 2 byte terima kasih kepada @PeterTaylor, 2 byte terima kasih kepada @Shaggy.)

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

Tidak Disatukan:

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

Kasus uji:

Rick Hitchcock
sumber
3

Retina , 46 38 byte

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

Cobalah online! Tautan termasuk kasus uji. Sunting: Disimpan 8 byte dengan bantuan dari @MartinEnder. Tahap pertama hanya mentranspos kurung, sedangkan tahap kedua mencari sufiks terpanjang yang merupakan awalan seimbang yang valid, yang tampaknya merupakan kondisi yang cukup untuk rotasi agar sepenuhnya seimbang. Penyeimbangan terdeteksi menggunakan kelompok penyeimbang. Konstruk ((\()|(?<-4>\)))+cocok dengan sejumlah (s ditambah jumlah )s selama kita sudah ( <-4>) melihat banyak (s. Karena kami hanya mencari awalan yang valid, kami tidak harus mencocokkan sisanya ).

Neil
sumber
Biasanya, alih-alih mengulangi kedua tanda kurung, Anda hanya menempatkan mereka dalam satu pergantian, yang menghemat satu byte ((\()|(?<-2>\))). Tapi upaya Anda hanya mengilhami saya untuk menemukan pendekatan yang sama sekali baru yang menyimpan dua lain: (?<-1>(\()*\))+. Ini tentu akan berguna di masa depan, jadi terima kasih. :)
Martin Ender
Ini bahkan lebih pendek untuk menentukan rotasi dengan mencocokkan akhiran pertama yang melaluinya Anda dapat mencapai akhir string tanpa mendapatkan kedalaman tumpukan negatif: tio.run/…
Martin Ender
@ MartinEnder Saya awalnya mencoba pergantian tetapi saya tidak bisa membuatnya bekerja pada saat itu, tetapi saya gagal melihat bagaimana (?<-1>(\()*\))+bahkan bekerja, karena tampaknya ingin muncul dari 1tumpukan sebelum benar-benar cocok dengan apa pun ...
Neil
@ MartinEnder Seperti yang terjadi, versi pergantian tampaknya menjadi pegolf dalam hal mencocokkan awalan seimbang.
Neil
1
Popping aktual terjadi pada akhir grup, bukan awal. Poin bagus dengan pergantian untuk menghindari duplikat \(*sekalipun.
Martin Ender
2

PHP, 110 108 byte

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

Jalankan sebagai pipa dengan -nRatau uji secara online .

kerusakan

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
Titus
sumber
2

Python 3 , 112 103 101 byte

-2 byte terima kasih kepada @ Mr.Xcoder

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

Cobalah online!

ovs
sumber
101 byte ? Tidak yakin itu berfungsi
Tn. Xcoder
2

Oktaf, 62 byte

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

Cobalah online!

Fungsi yang mengambil string sebagai input dan mencetak semua hasil.

Penjelasan:

           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
rahnema1
sumber
2

Mathematica, 78 byte

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

JavaScript (ES6), 97 byte

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

Bekerja dengan memutar string input secara rekursif hingga transposnya seimbang, lalu mentransposasinya.

Neil
sumber
Cantik sederhana.
Rick Hitchcock
1

APL (Dyalog Unicode) , 35 30 byte

Golf pendekatan baru berkat @ Adám

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

Cobalah online!

Golf sedang berlangsung.

Penjelasan

'()'⍳⎕              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
Kritixi Lithos
sumber
0

Python 2 , 99 byte

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]

Cobalah online!

Dalam bentuk fungsi untuk kasus uji mudah:

Python 2 , 108 byte

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]

Cobalah online!

Ini menggunakan pendekatan yang sedikit berbeda - alih-alih memutar string secara rekursif, jika kita menganggap parens sebagai penambahan dan penurunan beberapa penghitung keseimbangan, maka string yang seimbang tidak boleh memiliki jumlah total penambahan - pengurangan yang kurang dari 0.

Jadi kami ambil

(()(())())

membalikkan parens:

))())(()((

dan mengonversinya menjadi daftar jumlah kenaikan / penurunan:

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

-3 adalah minimum pada indeks 4 (berbasis nol); jadi kami ingin beralih dengan indeks itu +1. Ini menjamin bahwa kenaikan / penurunan kumulatif tidak akan pernah kurang dari 0; dan akan berjumlah 0.

Chas Brown
sumber
Pada telepon saya jadi saya tidak dapat menguji, tapi Anda bisa melakukan r=0,bukan r=[0]?
Cyoce
Jika Anda akan dengan @ saran Cyoce, Anda akan perlu mengganti r+=[r[-1]+2*b-1]dengan r+=r[-1]+2*b-1,serta
ovs
0

Clojure, 118 byte

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

Mengembalikan urutan karakter, jadi saya akan menyebutnya seperti ini:

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

Pertama-tama membalik kurung, kemudian loop selama jumlah kumulatif jumlah braket menjadi negatif di beberapa titik urutan.

NikoNyrh
sumber
0

brainfuck , 82 byte

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

Cobalah online!

Penjelasan

Dengan setiap karakter dibaca, penghitung diubah sebagai berikut:

  • Penghitung dimulai dari 0.
  • Setelah masing-masing ), penghitung meningkat sebesar 1.
  • Setelah masing-masing (, penghitung berkurang sebesar 1, kecuali penghitung adalah 0, dalam hal ini penghitung tidak berubah.

Setiap awalan adalah akhiran valid dari string seimbang (setelah inversi) jika dan hanya jika penghitung ini adalah 0. Kode ini menggunakan awalan terlama untuk membentuk output.

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