Balanceamento de suporte

20

Você receberá uma string (possivelmente vazia) contendo colchetes ( [{()}]) e quaisquer outros caracteres ( A- Z, a- z, 0- 9, pontuação). Você precisa verificar se ele cumpre as seguintes regras:

  • Caracteres sem colchetes são ignorados.
  • Todo suporte aberto [{(possui um suporte de fechamento )}]. Então [](não é permitido.
  • Os colchetes estão aninhados corretamente. [(])não é permitido.
  • Os colchetes não podem conter colchetes dentro deles. Os colchetes simples não podem conter colchetes encaracolados ou quadrados. Então [({})], [{[]}]e ({})não é permitido. Os colchetes podem ser aninhados com colchetes semelhantes, portanto, [[{((()))}{{(())}}]()]{()}é permitido.

A saída é um valor único de verdade / falsey, conforme sua escolha.

O menor código vence.


Casos de teste

b[[a{(/)}(())+={{}-}],] -> Válido

([h][e][l][l][o]) -> Inválido

[///[{(\/(arg()))}1{{((-)-2)}}]()]{()} -> Válido

hi -> Válido

ghosts_in_the_code
fonte
2
Possível duplicata de Corrigir colchetes desequilibrados
FUZxxl 2/15/15
9
@FUZxxl Isso parece um desafio muito mais difícil. Eu sinto que há outro idiota em algum lugar embora.
Martin Ender
@ MartinBüttner Sim, pode. Eu adicionei alguns casos de teste. E você encontrou a duplicata que estava procurando?
ghosts_in_the_code
1
@ MartinBüttner: Esse desafio pode ser o que você estava pensando.
Ilmari Karonen
1
Eu acho que deveríamos fechar a outra pergunta como uma duplicata disso; isso é melhor porque tem menos bônus.
lirtosiast

Respostas:

5

Retina , 84 bytes

^([^][}{)(]|()\(|(?<-2>)\)|(?!\2)((){|(?<-4>)}|(?!\4)(()\[|(?<-6>)])))*$(?!\2|\4|\6)

Experimente online.

Esta é uma extensão bastante direta (mas em golf) da regex .NET básica de verificação de parênteses .

Embora isso seja bem possível com grupos de balanceamento, a recursão de Perl definitivamente tem vantagem aqui . No entanto, qualquer abordagem é derrotada ao abandonar a elegância de uma única correspondência de regex em favor da redução gradual da entrada por meio de substituições repetidas, como faz a resposta sed do Digital Trauma . Isso pode ser implementado em 34 bytes na Retina, mas hesito em postar o código pessoalmente, pois não tive a ideia.

Martin Ender
fonte
5

Retina, 34

Em primeiro lugar, crédito onde o crédito é devido:

Independentemente (mais tarde), criei a mesma abordagem no sed , portanto, espero não estar pisando nos pés ( grande ou não) ao postar isso:

[^][(){}]

+`\(\)

+`{}

+`\[]

^$

Então agora com a sudo apt-get install mono-completee git clone https://github.com/mbuettner/retina.giteu tenho uma retina funcional na minha VM do Ubuntu. Aqui está o resultado do teste:

$ while read; do echo "Input: \"$REPLY\", Ouput: $( mono Retina.exe -s brbal.ret <<< "$REPLY" )" ; done < ../brbal.txt 
Input: "[[{((()))}{{(())}}]()]{()}", Ouput: 1
Input: "b[[a{(/)}(())+={{}-}],]", Ouput: 1
Input: "[///[{(/(arg()))}1{{((-)-2)}}]()]{()}", Ouput: 1
Input: "hi", Ouput: 1
Input: "", Ouput: 1
Input: "", Ouput: 1
Input: "([h][e][l][l][o])", Ouput: 0
Input: "[](", Ouput: 0
Input: "[(])", Ouput: 0
Input: "[({})]", Ouput: 0
Input: "[{[]}]", Ouput: 0
Input: "({})", Ouput: 0
$ 
Trauma Digital
fonte
@ThomasKwa Veja a saída de teste. Eu acredito que o código está correto e todos os casos de teste estão passando. Houve um problema específico que você vê no código ou um caso de teste específico que você acha que falhará?
Digital Trauma
@ThomasKwa Não portei o código deles, porque não faço ideia do que qualquer parte do ESMIN faz. Acabei de escrever esse código com base no que parecia fazer, então não acho que exista qualquer razão para que isso ocorra com o mesmo bug.
Martin Ender
Uau, @ MartinBüttner, você acertou! Sim, pensei que substituir recursivamente os parênteses de dentro para fora era mais lógico. Um rápido ajuste para ajustar as especificações de código fez com que funcionasse.
Mama Fun Roll
3

Sed, 53

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc

Aqui estou afirmando que, uma vez sedque realmente não tem um conceito de verdade / falsey, estou definindo a string vazia para significar truthy e todas as outras strings para significar falsey.

Se isso não for aceitável, podemos adicionar algumas linhas, assim:

Sed, 66

s/[^][(){}]//g
:;s/()//;t
:b;s/{}//;tb
:c;s/\[\]//;tc
/./c0
/^$/c1

Isso gera 0 para falso e 1 para verdadeiro.

Trauma Digital
fonte
Veja meu comentário sobre a resposta de molarmanful para a versão Retina da mesma solução exata (em 34 bytes; impressão 0ou 1). Não sei dizer quem deve publicá-lo, mas provavelmente deve ser um de vocês dois.
Martin Ender
3

CJam, 27 26 bytes

"(){}[]"q1$f&_,@2/e*{/s}/!

Imprime 1 (verdadeiro) ou 0 (falso). Experimente online! ou verifique todos os casos de teste.

Como funciona

"(){}[]"                    Push that string.
        q                   Read all input and push it on the stack.
         1$                 Copy the bracket string.
           f&               Intersect each input character with the bracket string.
                            This pushes an array of singleton and empty strings.
             _,             Get the length of the array (L), i.e., the number of
                            characters in the original input.
               @            Rotate the bracket string on top of the stack.
                2/          Split it into ["()" "{}" "[]"].
                  e*        Repeat each character pair L times.
                    {  }/   For each character pair.
                     /      Split the string on the stack at occurrences of that
                            character pair. This dosn't work properly the first
                            time, since there's a string array on the stack.
                      s     Flatten the resulting array of strings.
                         !  Apply logical NOT.
Dennis
fonte
3

43, 43 caracteres / 62 bytes

!Մ(Մ(Մ(ïċ/⁅⬮[\]{}]⌿),`⬮`,⬯),`{}`,⬯),`[]`,⬯)

Try it here (Firefox only).

Não.


No entanto, se eu usar os recursos implementados recentemente, eu posso chegar a 28 caracteres / 47 bytes:

!ïċ/⁅⬮[\]{}]⌿)ė`⬮”ė`{}”ė`[]”
Mama Fun Roll
fonte
Ohhh, você está removendo os parênteses correspondentes de dentro para fora? Isso seria meros 34 bytes na Retina: pastebin.com/bU77LzbR
Martin Ender
2

Japt , 42 37 bytes

Salvei 5 bytes com um recurso que eu não sabia que meu próprio idioma tinha ... Obrigado por adicioná-lo, @Downgoat!

O Japt realmente precisa de um melhor suporte ao RegExp ...

!Uo"()[\\]\{}" e"\\(\\)" e"\{}" e"\\[]

Experimente online!

Como funciona

               // Implicit: U = input string
Uo"()[\\]\{}"  // Remove all non-bracket.
e"\\(\\)"      // Recursively remove all pairs of simple brackets.
e"\{}"         // Recursively remove all pairs of curly brackets.
e"\\[]         // Recursively remove all pairs of square brackets.
!              // Return the Boolean NOT of the result.
               // (true for empty string, false for anything else)
               // Implicit: output last expression
ETHproductions
fonte
2

C99, 226 208 207 Bytes

Esta é a minha primeira vez tentando jogar algo

#define S s[i]
t(s,i)char*s;{int a[]={['[']=0,['{']=0,['(']=0};for(i=0;S*!(S=='{'&a['(']|S=='['&(a['(']|a['{'])|S==']'&(a['(']|a['{'])|S=='}'&a['(']);i++)a[S]++,a[S-S/90-1]--;return !(a['[']+a['{']+a['(']);}

Legível:

int t(char* s){
    int a[265]={['[']=0,['{']=0,['(']=0};
    for(int i=0;s[i]&&!((s[i]=='{'&a['(']>0)|(s[i]=='['&(a['(']>0|a['{']>0))|(s[i]==']'&(a['(']>0|a['{']>0))|(s[i]=='}'&a['(']>0));i++){
        a[s[i]]++;
        a[s[i]-(s[i]/90+1)]--;
    }
    return !(a['[']+a['{']+a['(']);
}

Há um estouro de buffer, mas parece não afetar nada - acredito que isso se deva ao alinhamento.

dj0wns
fonte
1
Você pode omitir o espaço emchar* s
Cyoce 23/02
Não sabia disso - obrigado
dj0wns 28/02
1

Perl, 50 + 1 = 51 bytes

$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/

Requer a -pbandeira e as impressões 1para a verdade e nada para resultados falsos. Estou contando -pcomo um, porque pode ser combinado com -e:

> perl -pe '$_=/^((([^][)(}{]|\((?3)*\))|{(?2)*})|\[(?1)*])*$/'

O código é basicamente apenas uma correspondência de regex simples com a entrada, usando o recurso de regex recursivo bacana do Perl.

Agradeço ao Dennis por me ajudar a testar isso e jogar golfe no padrão Perl.

Martin Ender
fonte
1

Python 3: 120 bytes

Com base na resposta de @ Adnan , ficou mais curto o uso:

import re
x=re.sub('[^[\](){}]','',input())  
for i in('()','{}','[]'):  
 while x.find(i)>=0:x=x.replace(i,'')  
print(x=='')
karhell
fonte
1

Python 3, 196 170 160 154 bytes

Desajeitadamente, obrigado ao Mego por salvar 6 bytes:

d=y=""
for C in input():
 for a in "[](){}":y+=C*(C==a)
 y=y.replace("()",d)
x=y
for r in y:x=x.replace("{}",d)
for s in y:x=x.replace("[]",d)
print(x==d)
Adnan
fonte