Mais um problema de análise de Brainfuck, mas desta vez ... diferente.

Você está trabalhando na Infinite Monkeys Incorporated, a empresa que faz os programas Brainfuck, para resolver vários problemas interessantes (por acidente, nada menos - afinal, a empresa faz programas aleatórios). No entanto, parece que suas máquinas rápidas de Turing que executam apenas o Brainfuck têm um problema pequeno e caro com erros de sintaxe - crie uma e o computador exploda. Provavelmente é uma falha de design, mas ninguém se deu ao trabalho de descobrir por que isso acontece.

Como as máquinas de Turing (especialmente as mais rápidas) são caras (afinal de contas, elas têm RAM infinita que custa), seria melhor garantir que o programa não tenha nenhum erro de sintaxe antes de executar o código. Sua empresa executará muitos códigos, portanto a verificação manual não funcionará. Escreva um programa que leia o código STDIN para Brainfuck e saia com o status de saída definido como algo diferente de 0 (erro) se o programa tiver algum erro de sintaxe (por exemplo, ]é um erro de sintaxe, porque não há correspondência [). Saia com o status de saída definido como 0 se o programa estiver completamente correto.

Verifique se o seu programa percebe corretamente os erros envolvidos []. Você não gostaria que outro computador explodisse, queria? Ah, e verifique se é o mais curto possível - seu chefe paga por programas curtos (porque ele acha que eles são rápidos, ou algo assim). Ah, e você não precisa codificar no Brainfuck (na verdade, não pode, porque o Brainfuck não suporta códigos de saída) - seu código será executado no computador normal.

Portanto, como você pode ver, seu trabalho é verificar se o programa Brainfuck é "válido" (possui []símbolos emparelhados ). Observe que os programas Brainfuck podem ter outros caracteres além de [], portanto, não recuse o programa apenas porque possui outros comandos. O menor código vence, mas provavelmente você se importaria mais com upvotes.

GolfScript, 18 caracteres

.{[]`?)},~](`91?./

Esse código é executado com êxito com o código de saída 0 (e imprime algum lixo em stdout) se os colchetes na entrada estiverem balanceados. Caso contrário, ele falhará com um código de saída diferente de zero e imprimirá uma mensagem de erro no stderr, por exemplo:

(eval):2:in `/': divided by 0 (ZeroDivisionError)

ou

(eval):1:in `initialize': undefined method `ginspect' for nil:NilClass (NoMethodError)

Como o desafio não disse nada sobre saída para stdout / stderr, acho que isso se qualifica. Em qualquer caso, você sempre pode redirecioná-los para /dev/null.

Explicação:

O código {[]`?)},retira tudo, exceto colchetes, da entrada e ~avalia o resultado como código GolfScript. A parte complicada é que colchetes desequilibrados são perfeitamente legais no GolfScript (e, de fato, meu código inclui um!), Portanto, precisamos de outra maneira de fazer com que o código falhe.

O truque que estou usando é deixar uma cópia da entrada na parte inferior da pilha, coletar a pilha inteira em uma matriz (usando o desbalanceado ]) e desativar o primeiro elemento. Neste ponto, três coisas podem acontecer:

• Se a entrada terminar em um não fechado [, tentar deslocar um elemento de uma matriz vazia trava o intérprete (que, nesse caso, é exatamente o que queremos!)
• Se os colchetes na entrada estiverem balanceados, o elemento deslocado será a sequência de entrada original.
• Caso contrário (se a entrada tiver uma abertura ]ou uma abertura [), será uma matriz.

Minha entrada original de 14 caracteres comparou o valor alterado com uma string, que falharia se fosse uma matriz aninhada. Infelizmente, acontece que comparar uma matriz plana (ou, em particular, vazia) com uma string também é legal no GolfScript, então tive que mudar de direção.

Minha submissão atual, em vez disso, usa um método de força bruta para diferenciar matrizes de strings: desvaloriza-as e tenta encontrar a primeira ocorrência de [(código ASCII 91), que será zero se e somente se as não avaliadas A variável era uma matriz. Nesse caso, dividir o zero consigo dispara a falha desejada.

Ps. Duas outras soluções de 18 caracteres são:

.{[]`?)},{.}%~](n<

e

.{[]`?)},~]([n]+n<

Infelizmente, ainda não encontrei uma maneira mais curta de resolver o "problema do array vazio".

Brainfuck 76 bytes

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

Isso desaparece se os colchetes estiverem desequilibrados, tornando o interpretador / compilador bf com falha no tempo de execução e alguns deles possuem códigos de saída para refletir isso.

requer eof = 0, valores de quebra automática e número finito de células

No Ubuntu você pode usar o intérprete bf( sudo apt-get install bf)

% echo '[[[]' | bf -n bf_matching.bf
Error: Out of range! Youwanted to '<' below the first cell.
To solve, add some '>'s at the beginning, for example.
an error occured
% echo $? 
5
% bf -n bf_matching.bf < bf_matching.bf
% echo $?
0

Befunge 98 - 26 31 20 19 caracteres

~:']-!\'[-!-+:0`j#q

Livre-se de alguns condicionais massivos. Agora o programa funciona da seguinte maneira:

~:   read an input char and duplicate it

']-! push a 1 if the char is the ] char, 0 otherwise

\    swap the comparison value for the duplicated input char

'[-! push a 1 if the char is the [ char, 0 otherwise

-    subtract the two comparison values. If the second one is 1, the first is 0, 
     so the result is -1. Else if the second one is 0, the first is 1 and the result is
     1. Else, the first and the second are both 0 and the result is 0

+    Add the number to the counter (which is 0 if there is none already)

:0`  test if the counter is positive (that'd mean an invalid program). Pushes a 1 if 
     positive, 0 otherwise.

j#q  if the counter is positive, then this jumps to the q. Otherwise, it skips the q 
     and continues to the ~ at the beginning of the line. If there are no more chars in
     the input, then the IP will be sent back to the q. 

qsai do programa e exibe o valor superior como um valor de erro. O valor do erro será -1 1 se houver muitos ], 0 se estiverem equilibrados e negativo positivo se houver muitos [. Se o número for negativo positivo , serão necessários muitos do valor absoluto desse número ]para equilibrar o programa.

Editar: incremento e decréscimo comutado. [usado para incrementar o contador e ]decrementá-lo. Ao alterná-lo, eu salvo 1 caractere, porque para a condição de saída, só tenho que verificar se o contador é positivo, e não negativo.

Versão antiga

~:'[-!j;\1+\#;']-!j;1-#;:0\`j#q

Este código funciona da seguinte maneira:

~    read one char of input
:    duplicate it
'[-! push 1 if the character is [, 0 otherwise
j    jump that number of characters
;    skip until next ;
\1+\ increment counter

similarily for ].

#q when end of input is reached, ~ reflects the IP back. q ends the program with the error value on the stack.

Edit: percebeu que isso aceita entradas como ][, agora termina sempre que a contagem fica negativa, usando

:0\`j

J ( 38 35)

exit({:+.<./)+/\+/1 _1*'[]'=/1!:1[3

Explicação:

• 1!:1[3: leia stdin
• '[]'=/: crie uma matriz em que a primeira linha seja uma máscara de bit do [ s na entrada e a segunda linha é os ]s.
• 1 _1*: multiplique a primeira linha por 1 e a segunda linha por -1.
• +/: soma as colunas da matriz, fornecendo recuo delta por caractere
• +/\: crie um total atual, fornecendo nível de recuo em cada caractere
• ({:+.<./): retorna o GCD do elemento final ( {:) e o menor elemento ( <./). Se todas as chaves coincidirem, ambas devem ser, 0portanto, isso retornará0 . Se os colchetes não corresponderem, ele retornará um valor diferente de zero.
• exit: defina o valor de saída como esse e saia.

rubi (64)

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.empty?

anteriormente (68) era:

exit ARGF.read.tr('^[]','').tap{|x| 0 while x.gsub!('[]','')}.empty?

Outra solução equivalente usa

exit $<.read.tr('^[]','').tap{|x|0while x.gsub!('[]','')}.size>0

não pode usar sizesozinho porque daria falsos negativos (!!!) quando o número total de colchetes desequilibrados for múltiplo de 256

Perl, 30 caracteres

Sua regex recursiva básica do Perl para o resgate:

perl -0ne 'exit!/^(([^][]|\[(?1)\])*)$/'

Para aqueles que não estão familiarizados com os argumentos de linha de comando usados ​​aqui: -0permite definir o caractere de final de linha para fins de entrada de arquivo; usar -0sem argumento define o caractere de final de linha como EOF. -nlê automaticamente a entrada (neste caso, o arquivo inteiro) em$_ antes.

Se o regex corresponder, ele retornará um valor verdadeiro, que é negado a 0 para o código de saída. Caso contrário, o valor de retorno falso produzirá um código de saída 1.

festança (tr + sed) - 42

[ -z `tr -Cd []|sed ":a;s/\[\]//g;t a"` ]

Se você não se importa com as mensagens de erro, pode remover o último espaço entre `e ]obter o comprimento 41.

Perl (56 caracteres)

$/=0;$r=qr/[^][]*(\[(??{$r})\])*[^][]*/;<>=~m/^$r$/||die

A solução Perl óbvia: um regex recursivo. Infelizmente, é uma construção bastante detalhada.

Haskell (143)

import System.Exit
f=exitFailure
v c []|c==0=exitSuccess|True=f
v c (s:t)|c<0=f|s=='['=v(c+1)t|s==']'=v(c-1)t|True=v c t
main=getContents>>=v 0

to jgon: Usar 2 guardas parece ser mais denso do que se-então-outro. Além disso, não acho que o seu verifique se os colchetes estão na ordem correta ("] [" passa)

C, 73 64 caracteres

Graças às sugestões da breadbox (embora isso provavelmente exija pouco trabalho):

i;main(c){while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Como funciona:

• global implícito implícito ié inicializado como 0
• ctorna-se um int implícito que é obtido argc(inicializado como 1, mas não nos importamos, desde que os bits mais altos não estejam definidos)
• read(0,&c,1)lê um único caractere no byte baixo de c (em arquiteturas little-endian) e retorna 0 no EOF; i+1 != 0a menos que a cotação entre colchetes seja -1; multiplicá-los juntos funciona como um booleano (seguro) E que leva um caractere a menos do que&&
• c==91avalia como 1 para '['ec==93 avalia como 1 para ']'. (Pode haver algum truque minucioso que seria menor, mas não consigo pensar em nada.)
• return isai com o código de status 0 se estiver equilibrado, diferente de zero se não estiver. Retornar -1 tecnicamente viola o POSIX, mas ninguém se importa com isso.

Versão anterior:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)

GTB , 55

0→O:0→X[`I@I="[":X+1→X@I="]":X-1→X@X<0:1→O@!!Ig;e]l;e~O

Sente falta []

Use 0para parar.

MATEMÁTICA, 88 caracteres

s = "[ [ my crazy code ] [ don't explode please! [] [ :)Ahh) ]  [] []]]";

r=StringReplace;
StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]

Rubi, 59. 58

Procura entre colchetes de abertura e fechamento, contando [como 1 e ]como -1, e sai se a contagem cair abaixo de 0.

b=0
$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b

Hássio , 104 bytes

func main(){l=0;r=0;b=input();foreach (c in b){if(c=="[")l++;if(c=="]")r++;}if(!(r==l))exit(1);exit(0);}

Expandido completo (a nota não funciona no intérprete online, pois a entrada () está desativada) aqui

Código da máquina de Turing, 286 276 bytes

Mais uma vez, estou usando a sintaxe da tabela de regras definida aqui.

0 * * l 1
1 _ ! r Q
5 _ _ r 5
5 * * * W
W [ ! l E
W ] ! l T
W _ _ l I
W * ! r *
E ! ! l *
E * * * R
R _ [ r O
R * * l *
T ! ! l *
T * * * Y
Y _ _ r U
Y * * l *
U [ _ r O
U ! ! * halt-err
I ! ! l *
I _ _ r halt
I * * l halt-err
O ! ! r Q
O _ _ l I
O * * r *
Q ! ! r *
Q * * * W

Termina no estado haltpara aceitar a entrada e halt-errrejeitá-la.

Pitão, 25 bytes

Ilzv::z"[^[\]]"k"]\[""],[

Experimente online!

import re
z=input()
if len(z):
 print(eval(re.sub("]\[","],[",re.sub("[^[\]]","",z))))

Haskell ( 167 , 159)

Fiz isso principalmente por diversão, se alguém tiver alguma sugestão de como reduzi-lo, ficaria feliz em ouvi-los :)

import System.Exit
p x y b|b=x|True=y
main=getContents>>=(return.all (>=0).scanl (\v->p (v-1) (v+1).(==']')) 0.filter (`elem`"[]"))>>=p exitSuccess exitFailure

Editar: Corrigido um problema apontado para mim nos comentários (adicionado 11 bytes).

Edit 2: Função auxiliar criada para testar predicados usando proteções inspiradas no user13350, removendo 8 bytes.

Stax , 14 11 caracteres

╬Äτ↔EªÉs «Ü

Execute e depure

Crédito para @recursive por -3 bytes.

Equivalente ASCII:

.[]Y|&{yz|egp!

Remova todos os caracteres [], exceto e remova []até que a sequência não seja mais alterada. Retorne 1se a sequência final estiver vazia.