Sprawdź, czy łańcuch jest zrównoważony w nawiasach

15

Grupę parens nazywamy otwartym parenem (, jego pasującym ścisłym parenem )i wszystkim, co się w nim znajduje.

Grupa lub ciąg znaków Parens nazywa się zrównoważonym w nawiasach, jeśli nie zawiera nic lub zawiera tylko dwie grupy zrównoważonych w nawiasach.

Na przykład:

The string   "(()())()"      is parenthesly balanced
              (    )()       Because it contains exactly 2 parenthesly balanced parens groups
               ()()          The left one is parenthesly balanced because it contains 2 parenthesly balanced parens groups (balanced because they are empty). The right one is parenthesly balanced because it contains nothing.

Również:

The string   "(()(()))()"    is not parenthesly balanced
              (      )()     Because it contains a parens group that is not parenthesly balanced: the left one
               ()(  )        The left one is not balanced because it contains a parens group that is not balanced: the right one
                  ()         The right one is not balanced because it only contains one balanced group.

Zatem nawiasowo zrównoważony ciąg lub grupa parens powinna:

  • Nic nie zawierają.
  • Lub zawierają tylko i dokładnie 2 nawiasowo zrównoważone grupy parens. Nie powinien zawierać nic więcej.

Zadanie:

Twoim zadaniem jest napisanie funkcji lub programu, który sprawdza, czy dany łańcuch jest nawiasowo zrównoważony, czy nie.

Wejście:

Dane wejściowe będą ciągiem znaków lub listą znaków lub czymś podobnym. Możesz założyć, że ciąg będzie składał się wyłącznie ze znaków '('i ')'. Możesz również założyć, że każdy otwarty paren (będzie miał pasujący ścisły paren ), więc nie martw się o ciągi takie jak "((("lub ")("lub "(())("...

Uwaga: Jak wspomniano w jego komentarz mieszka przez @DigitalTrauma, to jest ok, aby subtitute z ()combo za pomocą innych znaków (takich jak <>, []...), czy to powoduje dodatkową pracę jak ucieczka w niektórych językach

Wynik:

Wszystko, co sygnalizuje, czy łańcuch jest nawiasowo zbalansowany, czy nie (prawda czy fałsz, 1 lub 0, ...). Podaj w swojej odpowiedzi, co ma przynieść twoja funkcja / program.

Przykłady:

""                                        => True
"()()"                                    => True
"()(()())"                                => True
"(()(()(()())))(()())"                    => True
"(((((((()())())())())())())())()"        => True
"()"                                      => False
"()()()"                                  => False
"(())()"                                  => False
"()(()(())())"                            => False
"(()())(((((()())()))())())"              => False
"()(()()()())"                            => False
"()(()(()())()())"                        => False

Dwa ostatnie przykłady naprawdę zrobiły różnicę!

Powodzenia!

ibrahim mahrir
źródło
Coś, co zasygnalizuje, czy łańcuch jest nawiasowo zbalansowany, czy nie. Czy wymagana jest spójna moc wyjściowa, tj. Tylko dwie wartości?
Luis Mendo
@LuisMendo Mogą to być kategorie. tj. wartości prawdy, aby zasygnalizować prawdę i wartości fałszu, aby zasygnalizować inaczej. Tak więc może być ich więcej, ale i tak powinno być spójne.
ibrahim mahrir
1
Czy to w porządku, jeśli wezmę listę binarną jako dane wejściowe? Na przykład "(()())()"byłby reprezentowany jako [0, 0, 1, 0, 1, 1, 0, 1]. To wyeliminowałoby konieczność konwertowania danych wejściowych na kod znakowy, a następnie odejmowanie.
JungHwan Min
Powiązane pytanie: codegolf.stackexchange.com/questions/166457/…
Windmill Cookies
1
@WindmillCookies Nie widzę związku z tym. Zupełnie inne rzeczy. Nawet koncepcja jest inna.
ibrahim mahrir

Odpowiedzi:

8

Japt v2, 20 bajtów

V="()"V¥iU1 eViV²1 V

Przetestuj online!

Wszyscy początkowo źle zrozumieli wyzwanie i chociaż każda para nawiasów musiała zawierać parzystą liczbę podpar, podczas gdy w rzeczywistości wyzwanie wymaga 0 lub 2 podpar. Oto moja poprawiona odpowiedź, przy użyciu tej samej techniki, co poprzednio.

Nadal możemy rozwiązać wyzwanie za pomocą rekurencyjnej zamiany. Chodzi o to, że zamiast po prostu usunąć wszystkie wystąpienia ()(), musimy upewnić się, że nie ma nic innego w tym samym opakowaniu oprócz ()()(innymi słowy, nie ()()()()lub coś takiego). Możemy to zrobić poprzez zastąpienie rekurencyjnie (()())z ().

Nowy problem polega na tym, że samo wejście nie ma jednej pary nawiasów zewnętrznych (ponieważ w ten sposób nie byłby ciągiem nawiasowo zrównoważonym), co zmusiło nas do zawinięcia go w dodatkową parę, aby w pełni go zmniejszyć. Wreszcie, wynik końcowy dla zbalansowanych ciągów jest teraz() zamiast pustego łańcucha, więc sprawdzamy równość, a nie tylko logiczne NIE wyniku.

ETHprodukcje
źródło
7

sed 4.2.2, 30

:
s/(()())/()/
t
/^()()$\|^$/q1

Wypróbuj online .

Zwraca kod wyjścia powłoki 1 dla True i 0 dla False.

:               # label
s/(()())/()/    # replace "(()())" with "()"
t               # jump back to label if above replacement matched
/^()()$\|^$/q1  # exit code 1 if remaining buffer is exactly "()()" or empty
                # otherwise exit with code 0
Cyfrowa trauma
źródło
7

Perl 5- LP, 24 22 bajtów

$_=/^((<(?1)?>){2})?$/

Wypróbuj online! Link zawiera przypadki testowe. Edycja: Zapisano 2 bajty dzięki @JoKing. Objaśnienie: Po prostu rekursywne wyrażenie regularne. Zewnętrzna grupa przechwytująca reprezentuje zrównoważony ciąg, <po którym następuje opcjonalny zrównoważony ciąg, po którym następuje >dwukrotne. Zauważ, że większość innych odpowiedzi jest w stanie użyć ()s, ale kosztuje to dodatkowe dwa bajty:

$_=/^((\((?1)?\)){2})?$/

Wypróbuj online! Link zawiera przypadki testowe.

Neil
źródło
3
Ponieważ możesz użyć innych par nawiasów, możesz zaoszczędzić dwa bajty, używając<>
Jo King
1
@JoKing Prawie wszystkie inne odpowiedzi były w stanie użyć ()s, więc nie sądziłem, że to uczciwe porównanie, jednak widzę, że odpowiedź APL @ ngn również używa <>s, więc zaktualizowałem tę.
Neil,
6

Procedura kodu maszynowego 6502 , 48 bajtów

A0 00 84 FD A2 00 B1 FB F0 0E C8 C9 29 18 F0 06 8A 48 E6 FD 90 EE B0 0A E0 01
90 06 E0 02 38 D0 01 18 A5 FD F0 09 C6 FD 68 AA E8 B0 F5 90 D7 60

Oczekuje wskaźnika do łańcucha w $fb/, $fcktóry powinien zawierać tylko (i ). Czyści flagę C (Przenoszenie), jeśli łańcuch jest „zbalansowany nawiasowo”, ustawia go inaczej (co jest typowym idiomem w 6502, zestaw przenosi „na błąd”). Nie robi nic sensownego przy nieprawidłowym wprowadzeniu.

Chociaż algorytm jest rekurencyjny, nie wywołuje się sam (co wymagałoby więcej bajtów i uzależnia pozycję kodu), ale zachowuje samą głębokość rekurencji i używa „prostego” rozgałęzienia.

Skomentowano demontaż

; function to determine a string is "paranthesly balanced"
;
; input:
;   $fb/$fc: address of the string
; output:
;   C flag set if not balanced
; clobbers:
;   $fd:     recursion depth
;   A,X,Y

 .isparbal:
A0 00       LDY #$00            ; string index
84 FD       STY $FD             ; and recursion depth
 .isparbal_r:
A2 00       LDX #$00            ; set counter for parantheses pairs
 .next:
B1 FB       LDA ($FB),Y         ; load next character
F0 0E       BEQ .done           ; end of string -> to final checks
C8          INY                 ; increment string index
C9 29       CMP #$29            ; compare with ')'
18          CLC                 ; and reset carry
F0 06       BEQ .cont           ; if ')' do checks and unwind stack
8A          TXA                 ; save counter ...
48          PHA                 ; ... on stack
E6 FD       INC $FD             ; increment recursion depth
90 EE       BCC .isparbal_r     ; and recurse
 .cont:
B0 0A       BCS .unwind         ; on previous error, unwind directly
 .done:
E0 01       CPX #$01            ; less than one parantheses pair
90 06       BCC .unwind         ; -> ok and unwind
E0 02       CPX #$02            ; test for 2 parantheses pairs
38          SEC                 ; set error flag
D0 01       BNE .unwind         ; if not 2 -> is error and unwind
18          CLC                 ; clear error flag
 .unwind:
A5 FD       LDA $FD             ; check recursion depth
F0 09       BEQ .exit           ; 0 -> we're done
C6 FD       DEC $FD             ; otherwise decrement
68          PLA                 ; get "pair counter" ...
AA          TAX                 ; ... from stack
E8          INX                 ; and increment
B0 F5       BCS .unwind         ; continue unwinding on error
90 D7       BCC .next           ; otherwise continue reading string
 .exit:
60          RTS

Przykładowy program asemblerowy C64 wykorzystujący procedurę:

Demo online

screenshot

Kod w składni ca65 :

.import isparbal   ; link with routine above

.segment "BHDR" ; BASIC header
                .word   $0801           ; load address
                .word   $080b           ; pointer next BASIC line
                .word   2018            ; line number
                .byte   $9e             ; BASIC token "SYS"
                .byte   "2061",$0,$0,$0 ; 2061 ($080d) and terminating 0 bytes

.bss
linebuf:        .res    256

.data
prompt:         .byte   "> ", $0
truestr:        .byte   "true", $0
falsestr:       .byte   "false", $0

.code
inputloop:
                lda     #<prompt        ; display prompt
                ldy     #>prompt
                jsr     $ab1e

                lda     #<linebuf       ; read string into buffer
                ldy     #>linebuf
                ldx     #0              ; effectively 256
                jsr     readline

                lda     #<linebuf       ; address of string to $fb/fc
                sta     $fb
                lda     #>linebuf
                sta     $fc
                jsr     isparbal        ; call function

                bcs     isfalse
                lda     #<truestr
                ldy     #>truestr
                bne     printresult
isfalse:        lda     #<falsestr
                ldy     #>falsestr
printresult:    jmp     $ab1e           ; output true/false and exit

; read a line of input from keyboard, terminate it with 0
; expects pointer to input buffer in A/Y, buffer length in X
.proc readline
                dex
                stx     $fb
                sta     $fc
                sty     $fd
                ldy     #$0
                sty     $cc             ; enable cursor blinking
                sty     $fe             ; temporary for loop variable
getkey:         jsr     $f142           ; get character from keyboard
                beq     getkey
                sta     $2              ; save to temporary
                and     #$7f
                cmp     #$20            ; check for control character
                bcs     checkout        ; no -> check buffer size
                cmp     #$d             ; was it enter/return?
                beq     prepout         ; -> normal flow
                cmp     #$14            ; was it backspace/delete?
                bne     getkey          ; if not, get next char
                lda     $fe             ; check current index
                beq     getkey          ; zero -> backspace not possible
                bne     prepout         ; skip checking buffer size for bs
checkout:       lda     $fe             ; buffer index
                cmp     $fb             ; check against buffer size
                beq     getkey          ; if it would overflow, loop again
prepout:        sei                     ; no interrupts
                ldy     $d3             ; get current screen column
                lda     ($d1),y         ; and clear 
                and     #$7f            ;   cursor in
                sta     ($d1),y         ;   current row
output:         lda     $2              ; load character
                jsr     $e716           ;   and output
                ldx     $cf             ; check cursor phase
                beq     store           ; invisible -> to store
                ldy     $d3             ; get current screen column
                lda     ($d1),y         ; and show
                ora     #$80            ;   cursor in
                sta     ($d1),y         ;   current row
                lda     $2              ; load character
store:          cli                     ; enable interrupts
                cmp     #$14            ; was it backspace/delete?
                beq     backspace       ; to backspace handling code
                cmp     #$d             ; was it enter/return?
                beq     done            ; then we're done.
                ldy     $fe             ; load buffer index
                sta     ($fc),y         ; store character in buffer
                iny                     ; advance buffer index
                sty     $fe
                bne     getkey          ; not zero -> ok
done:           lda     #$0             ; terminate string in buffer with zero
                ldy     $fe             ; get buffer index
                sta     ($fc),y         ; store terminator in buffer
                sei                     ; no interrupts
                ldy     $d3             ; get current screen column
                lda     ($d1),y         ; and clear 
                and     #$7f            ;   cursor in
                sta     ($d1),y         ;   current row
                inc     $cc             ; disable cursor blinking
                cli                     ; enable interrupts
                rts                     ; return
backspace:      dec     $fe             ; decrement buffer index
                bcs     getkey          ; and get next key
.endproc
Felix Palmen
źródło
5

V , 21 , 20 bajtów

é(Á)òÓ(“()()…)òø^()$

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe!

é(                      " Insert '(' at the beginning of the line
  Á)                    " Append ')' at the end
    ò         ò         " Recursively...
     Ó                  "   Remove...
      (                 "     '('
       “    …           "     (Limit the part that is removed to this section of the match)
        ()()            "     '()()'
             )          "     ')'
                        " (effectively, this replaces '(()())' with '()', but it's one byte shorter than the straightforward approach
               ø        " Count...
                ^()$    "   Lines containing exactly '()' and nothing more

Hexdump:

00000000: e928 c129 f2d3 2893 2829 2829 8529 f2f8  .(.)..(.()().)..
00000010: 5e28 2924                                ^()$
James
źródło
Czy możesz wyjaśnić swój kod, abym mógł (mam nadzieję) znaleźć przypadek testowy , który nie działa, tak jak zrobiłem to z odpowiedzią @ Adàm .
ibrahim mahrir
@ibrahimmahrir Gotowe.
James
5

Brachylog , 28 bajtów

Ẹ|~c["(",A,")(",B,")"]∧A;B↰ᵐ

Wypróbuj online!

Wyjaśnienie

                                    --  The string perfectly balanced iff
Ẹ                                   --      the string is empty
 |                                  --  or
  ~c["(",A,")(",B,")"]              --      the string can be written id the format of "($A)($B)"
                      ∧             --          where
                       A;B ᵐ        --          both A and B
                          ↰         --          are perfectly balanced
Kroppeb
źródło
4

C (gcc) , 113 bajtów

p(a,r,e,n)char*a;{if(*a-40)return 1;for(r=1,e=0;e<2;r&=e++||*a==40)for(r*=n=p(++a);n+=*a++-40?~0:1;);r=r&&*a-40;}

Wypróbuj online!

Wyjaśnienie

p(a,r,e,n)char*a;{   // function and variable declaration
 if(*a-40)return 1;  // string does not start with '(', thus is empty
 for(r=1,e=0;e<2;    // r: return value, e: group id (look for exactly two groups)
 r&=e++||*a==40)     // after the first group, a second shall follow
  for(r*=n=p(++a);   // check that the group is itself balanced
  n+=*a++-40?~0:1;); // skip group
 r=r&&*a-40;}        // additionally, after those two groups there shall follow none

Wypróbuj online!

Jonathan Frech
źródło
3

MATL , 26 25 bajtów

oo~`tnw52B5LZttnb<]XB10X-

Wypróbuj online!

Dzięki odpowiedzi @ETHProductions na pomysł „zamień (() ()) na ()” i komentarzu @JungHwan Min do pomysłu postrzegania nawiasów jako cyfr binarnych.

Dane wyjściowe to pusta tablica dla prawdy, liczba dodatnia dla falsey - co, jak sądzę, jest dozwolone w komentarzu OP: „Mogą to być kategorie. Tj. Wartości prawdy, aby zasygnalizować prawdziwość, a wartości fałsz, aby zasygnalizować inaczej”. Jeśli nie, możemy dodać nna końcu +1 bajt, aby mieć 0 jako wyjście zgodne z prawdą i 1 jako wyjście falsey.

Z komentarzami:

o         % Convert the parantheses to their ASCII codes
          %  40 for '(', 41 for ')'
o         % Parity - 1 for odd, 0 for even
~         % Not - change 0 to 1 and vice versa, so '(' is now 1 and ')' 0
          % Input char array is now a binary array B
`         % Do-while loop
  tn          % Get the length of the array 
  w           % Bring the array B back on top
  52B         % Push the binary value of 52 on stack
              %  [1 1 0 1 0 0] (equivalent to '(()())')
  5L          % Push the constant [1 0] for '()'
  Zt          % Replace the sequence [1 1 0 1 0 0] in array B
              %  with [1 0]
  tn          % Get the length of the array after replacement 
  b<          % Has it decreased? If so, continue loop
  ]       % end loop
          % Final value for balanced input will be
          %  either [1 0 1 0] for the remaining outer '()()'
          %  or an empty array [] for empty '' input
XB        % Convert the final binary array back to decimal
10X-      % Set difference, remove 10 from that result 
          % Result is [] empty array for balanced input, otherwise 
          %  some decimal number ≠ 10 for unbalanced input
sundar - Przywróć Monikę
źródło
3

Haskell , 82 59 bajtów

all(`elem`[0,2]).foldl(#)[0]
b#'('=0:b
(x:y:z)#_=y+1:z++[x]

Wypróbuj online!

Zakładam, że można grać w golfa znacznie dalej, ponieważ po raz pierwszy grałem w Haskell, więc wszelkie sztuczki i komentarze są mile widziane.

EDYCJA - Dzięki @nimi za zaoszczędzenie 23 bajtów (ponad 28% oryginalnego zgłoszenia :)

Vincent
źródło
1
Kilka wskazówek: nie trzeba tego ()robić y+1. Ponieważ funkcje nienazwane są dozwolone, możesz upuścić f=, r[0]to właściwa funkcja. Połóż skrzynkę podstawową r b[]na końcu i przełącz na funkcję infix (powiedzmy #), wtedy możesz użyć b#_=. Możesz także nieznacznie zmienić algorytm, budując listę, aby sprawdzić krok po kroku 0s i 2s, zamiast przenosić ją wokół połączeń rw akumulatorze r(x:y:z) ... = x : r (...) az obudową podstawową r b [] = b. Sprawdź po pierwszym połączeniu r[0]. W sumie 73 bajty.
nimi
... Wypróbuj online! .
nimi
1
... lub nawet lepiej: zostań z akumulatorem i przełącz na foldl(59 bajtów): Wypróbuj online! .
nimi
@nimi Dziękuję bardzo, dokładnie tego rodzaju wskazówki, których szukałem :)
Vincent
3

JavaScript (ES6), 63 bajty

Pobiera dane wejściowe jako tablicę znaków. Zwraca false dla nawiasowo zrównoważony, true dla nie nawiasowo zrównoważony.

a=>[...a,k=0].some(c=>c<')'?!(a[k]=-~a[k++]):a[k]=~5>>a[k--]&1)

Wypróbuj online!

Skomentował

a =>                     // a[] = input array of characters; we are going to reuse it to
  [                      // store the number of parenthesis groups at each depth
    ...a,                // append all characters
    k = 0                // initialize k = current depth to 0 and append a value that will
  ]                      // be treated as a final closing parenthesis for the root level
  .some(c =>             // for each character c in this array:
    c < ')' ?            //   if c is an opening parenthesis:
      !(                 //     increment the number of groups at the current depth
        a[k] = -~a[k++]  //     increment the depth
      )                  //     yield false
    :                    //   else:
      a[k] = ~5          //     make sure that the current depth contains either 0 or 2
             >> a[k--]   //     groups, by shifting the 1-complement of 5 (101 in binary)
             & 1         //     and testing the least significant bit
                         //     it resets the number of groups to 0 if the bit is not set
                         //     otherwise, it forces some() to return true
                         //     decrement the depth
  )                      // end of some()

Rekurencyjny, 54 bajty

Używanie zamienników rekurencyjnych (jak w odpowiedzi Japt ETHproductions ) jest jednak znacznie krótsze.

Pobiera dane wejściowe jako ciąg. Zwraca 1 dla zrównoważenia w nawiasach, 0 dla niezrównoważenia w nawiasach.

f=s=>s==(s=s.split`(()())`.join`()`)?!s|s=='()()':f(s)

Wypróbuj online!


Rekurencyjny, 46 bajtów

Ten generuje błąd rekurencji dla niezrównoważonego w nawiasach:

f=s=>!s|s=='()()'||f(s.split`(()())`.join`()`)

Wypróbuj online!

Arnauld
źródło
Nie jestem zbyt dobry w JavaScript, ale czy x [k] = - ~ x [k ++] można zastąpić x [k] ++; k ++, a nawet ++ x [k ++]?
Андрей Ломакин
2
@ АндрейЛомакин Nie, ponieważ x[k]początkowo jest niezdefiniowany i x[k]++dałby NaN, a -~undefineddaje 1.
Arnauld
@ АндрейЛомакин Teraz ponownie używam tablicy wejściowej, więc a[k]początkowo zawiera znak. Ale ta sama logika dotyczy ciągów: zastosowanie ++na nich operatora daje NaN, ale operatory bitowe (takie jak ~) zmuszają je do 0wcześniejszego przymusu .
Arnauld
Przenosi javascript na zupełnie nowy poziom. : D
ibrahim mahrir
3

Perl 6 ,  43 41  37 bajtów

{my rule f{\([<&f>**2]?\)};?/^<&f>**2$|^$/}

Sprawdź to

{(my$f)=/\([<$f>**2]?\)/;?/^[<$f>**2]?$/}

Sprawdź to

{$!=/\([<$!>**2]?\)/;?/^[<$!>**2]?$/}

Sprawdź to

Rozszerzony:

{  # bare block lambda with implicit parameter $_

  $! = # store regex into $! (no need to declare it)
  /
    \(

      [
        <$!> ** 2 # recurse into regex twice
      ]?          # optionally

    \)
  /;


  ?      # boolify (causes it to be run against $_)

    /
      ^         # beginning of string

      <$!> ** 2 # match using regex twice

      $         # end of string

    |           # or

      ^ $       # empty string
    /
}
Brad Gilbert b2gills
źródło
3

R , 71 bajtów

f=function(s,r=sub('(()())','()',s,f=T))'if'(r==s,s==''|s=='()()',f(r))

Wypróbuj online!

  • przenoszenie rekurencyjnego rozwiązania Japt @ETHproductions
  • -2 bajty dzięki @JayCe

Kolejne - dłuższe - rozwiązanie, ale interesujące dla innego podejścia

R , 85 bajtów

g=gsub;!sum(eval(parse(t=g('\\)\\(',')-(',g('\\)','-1)',g('\\(','(2+',scan(,'')))))))

Wypróbuj online!

Objaśnienie:

Weź ciąg wejściowy i zamienia:

'('  with '(2+'
')'  with '-1)'
')(' with ')-('

następnie ocenia wynikowe wyrażenie. Jeśli jest równa zero, jest zrównoważony, w przeciwnym razie nie jest. Użycie komendy sumjest konieczne tylko do obsługi pustej wielkości ciągu, ponieważ zwraca ona swoją ocenę NULL.

na przykład

()(()()) => (2+-1)-(2+(2+-1)-(2+-1)-1) = 0
(()())   => (2+(2+-1)-(2+-1)-1)        = 1
digEmAll
źródło
Zaoszczędź dwa bajty:f=function(s,r=sub('(()())','()',s,f=T))'if'(r==s,s==''|s=='()()',f(r))
JayCe,
Na pierwszym miejscu powinno być krótsze rozwiązanie
tylko ASCII
@ Tylko ASCII: masz rację, ale ponieważ jest to w zasadzie przeniesienie innego rozwiązania, wydawało się, że to „kradzież”: P
digEmAll
3
@digEmAll Cóż, w wielu wyzwań tutaj większość wyzwań zrobić właśnie portowi innego rozwiązania
ASCII tylko
2

05AB1E , 18 16 13 bajtów

…(ÿ)…(()∞„()©:®Q

Port odpowiedzi Japt @ETHproductions, aby naprawić przypadek testowy ()(()()(()())(()())).
-2 bajty dzięki @Adnan .

Na podstawie tego komentarza OP używam teraz ()jako prawdziwej wartości, a wszystko inne jako falsey. Jeśli obie wartości muszą być spójne zamiast tylko jednej, byłaby to stara 16- bajtowa odpowiedź zamiast ( …(ÿ)…(()∞„()©:®Q), zwracająca się w 0przypadku prawdomównych i 1testowych falsey.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

…(ÿ)             # Take the input (implicitly) and surround it with "(" and ")"
            :    # Infinite replacement of:
    …(()∞        #  "(()())"    ("(()" mirrored)
         „()     #  with "()"
                 # After the infinite replacement: return the result
                 # ("()" for truthy; falsey otherwise)

(Stara 18-bajtowa odpowiedź, która nie powiodła się w przypadku testowym ()(()()(()())(()()))..):

ΔD„()∞©6∍å_i®õ.:]Ā

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Kevin Cruijssen
źródło
Myślę, że można użyć nieskończonej zastąpić metodę: „()∞õ:g_.
Adnan
nie czekaj, źle zrozumiałem wyzwanie
Adnan
@Adnan Na początku tak myślałem, ale nie udaje się to w przypadku przypadków testowych, (()()()())które powinny zwrócić falsey. Każda grupa w nawiasach powinna zawierać dokładnie 0 lub 2 grupy wewnętrzne.
Kevin Cruijssen
1
Można wymienić '(®')Jz …(ÿ).
Adnan
@Adnan Thanks! Wiedziałem ÿ, że istnieje, ale nigdy wcześniej go nie użyłem, więc zupełnie o nim zapomniałem.
Kevin Cruijssen
2

Prolog , 46 bajtów

a-->p,p.
a-->[].
p-->[l],a,[r].
f(X):-a(X,[]).

Wypróbuj online! lub Zweryfikuj wszystkie przypadki testowe!

Używa list li rjako danych wejściowych, np. "()()"Jest testowany jakof([l,r,l,r]). .

Pierwsze trzy wiersze to gramatyka prawidłowych ciągów w składni gramatyki Prologa. a(A,B).zwraca wartość, truegdy Alista jest zgodna z gramatyką i Bjest pusta. Tak więc główna funkcja fpobiera niektóre Xi sprawdza, czy jest a(X,[])wstrzymana.

Laikoni
źródło
2

Python 2 , 73 71 bajtów

f=lambda s,P='(()())':P in s and f(s.replace(P,'()'))or s in['()()','']

Wypróbuj online!

Chas Brown
źródło
1

pieprzenie mózgu, 50 bajtów

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

Sformatowany:

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

Oczekuje ciągu (i )bez znaku nowej linii oraz danych wyjściowych \x01dla wartości true i \x00false. (Dla czytelności możesz np. Dodać 48 +s przed finałem, .aby wydrukować 1i 0zamiast tego.)

Wypróbuj online

Utrzymuje to stos z liczbą grup na każdej głębokości, rozróżniając znaki według parzystości i sprawdzając, czy liczba grup jest w {0, 2} po każdym zamkniętym nawiasie; jeśli warunek nie jest spełniony, zużywa resztę danych wejściowych i ustawia flagę; następnie sprawdza warunek ponownie pod koniec programu.

Jeśli wolno nam zakończyć strumień wejściowy nieparzystym znakiem, możemy pominąć kontrolę końcową, <[--[>->]]aby zapisać 10 bajtów. (Gdyby\n nie było nawet niewygodnie, mógłbym zaproponować ten wariant jako główną odpowiedź).

(Możemy również zapisać niektóre bajty, zmieniając format wyjściowy \x00na true i non- \x00false, co wydaje się być dozwolone (być może przypadkowe) w opisie problemu w formie pisemnej, ale i tak nie byłoby to zbyt interesujące, a ja wolę nie wprowadzać tej zmiany).

Mitch Schwartz
źródło
1

Python2, 95 94 bajtów

f=lambda i:g(eval("(%s)"%i.replace(")","),")))
g=lambda i:len(i)in(0,2)and all(g(j)for j in i)

Wypróbuj online!

f () przekształca ciąg w zagnieżdżoną krotkę, którą przekazuje do g ().

g () rekurencyjnie nawiguje po krotce i zwraca False, jeśli jakikolwiek element nie ma dokładnie 0 lub 2 elementów potomnych.

Zapisano jeden bajt przy użyciu formatowania ciągów.

Triggernometria
źródło
1

Stax , 13 11 bajtów

₧aaS▐îî»Å·╢

Uruchom i debuguj

Zapisałem dwa bajty, kiedy zdałem sobie sprawę, że dane wejściowe można przypadkowo przywołać jako literały tablicowe. Usunięcie podwójnych cudzysłowów ułatwia wprowadzanie danych.

Ogólna idea polega na ewaluacji danych wejściowych jako literału tablicowego i rekurencyjnym mapowaniu elementów w celu sprawdzenia parethely balance. Jeśli ostateczne stwierdzenie kiedykolwiek się nie powiedzie, nastąpi kolejny pop na pustym stosie. W stax, opróżnianie pustych stosów natychmiast kończy program.

Rozpakowane, niepolowane i skomentowane, wygląda to tak.

        input is implicitly treated as array literals
L       wrap entire input stack in an array
G       jump to the trailing '}', and come back when done
}       terminate the program, the rest is a recursive call target
{Gm     map array on top of the stack by using the recursive call target
%       get the length of the mapped array
02\#    is the length one of [0, 2]?
|c      assert value is truthy, pop if not

Uruchom ten

rekurencyjny
źródło
1

Java 10, 99 96 95 83 bajtów

s->{s="("+s+")";for(var p="";!p.equals(s);s=s.replace("(()())","()"))p=s;return s;}

Port mojej odpowiedzi 05AB1E (więc zwraca również ()jako prawdę, a wszystko inne jako falsey).

Wypróbuj online.

Wyjaśnienie:

s->{                 // Method with String as both parameter and return-type
  s="("+s+")";       //  Surround the input-String between "(" and ")"
  for(var p="";      //  Previous-String, starting empty
      !p.equals(s)   //  Loop as long as the previous and current Strings differ
      ;              //    After every iteration:
       s=s.replace("(()())","()"))
                     //     Replace all "(()())" with "()"
    p=s;             //   Set the previous String with the current
  return s;}         //  Return the modified input-String
                     //  (if it's now "()" it's truthy; falsey otherwise)

return s;może być, return"()".equals(s);jeśli wymagany był rzeczywisty wynik logiczny.

Kevin Cruijssen
źródło
Możesz zaoszczędzić jeden bajt, jeśli tylko sprawdzisz!s.contains("()()(")
Charlie
@Charlie Dzięki, ale kod i tak zawierał błąd, więc musiałem go zmienić. Jest teraz naprawiony (dla ostatnio dodanego przypadku testowego falsey) i golfowany przez 4 bajty jednocześnie.
Kevin Cruijssen