Yet another Brainfuck parsing problem, but this time... different.

You are working in the Infinite Monkeys Incorporated, the company making Brainfuck programs, to solve various interesting problems (by accident, no less - after all, the company makes random programs). However, it appears that your fast Turing machines that only execute Brainfuck have a small and expensive problem with syntax errors - make one, and the computer explodes. It's probably a design flaw, but nobody had bothered to find why it happens.

As Turing machines (especially fast ones) are expensive (after all, they have infinity RAM which costs), it would be better to make sure that the program doesn't have any syntax errors before executing the code. Your company is going to run lots of code, so manual verification won't work. Write a program that reads the STDIN for Brainfuck code, and exits with exit status set to anything other than 0 (error) if program has any syntax error (for example, ] is a syntax error, because there is no matching [). Exit with exit status set to 0 if the program is completely fine.

Make sure that your program correctly notices mistakes involving []. You wouldn't want another computer to explode, would you? Oh, and make sure it's as short as possible - your boss pays for short programs (because he thinks they are fast, or something). Oh, and you don't have to code in Brainfuck (in fact, you cannot, because Brainfuck doesn't support exit codes) - your code will be ran on normal computer.

So, as you can see, your job is to check if Brainfuck program is "valid" (has paired [] symbols). Please note that Brainfuck programs can have other characters than [], so don't refuse the program just because it has other commands. Smallest code wins, but probably you would care more about upvotes anyway.

  • 1
    \$\begingroup\$ What about languages that don't allow setting a process exit code? \$\endgroup\$ Commented Jan 3, 2014 at 17:24
  • 1
    \$\begingroup\$ @KendallFrey: Simple, use something else. Or in GolfScript, embed Ruby code. Perhaps this blocks some esoteric programming languages, but well... \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 17:26
  • 1
    \$\begingroup\$ Is it okay to set the error code to something other than 1 (as long as it's not 0 of course) on failure? \$\endgroup\$
    – marinus
    Commented Jan 3, 2014 at 18:31
  • \$\begingroup\$ @marinus: I don't know why you would want that, but I think it's fine. \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 18:33
  • \$\begingroup\$ @GlitchMr: because then I can use GCD(a,b) instead of 0 != a || b. \$\endgroup\$
    – marinus
    Commented Jan 3, 2014 at 18:50

23 Answers 23


Brainfuck 76 bytes


This goes out of it's bonds if square brackets are unbalanced turning the bf interpreter/compiler to fail runtime and some of them have exit codes to reflect that.

requires eof=0, wrapping values and finit number of cells

In Ubuntu you can use the interpreter 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 $? 
% bf -n bf_matching.bf < bf_matching.bf
% echo $?
  • 5
    \$\begingroup\$ I like how you used Brainfuck even though the question said that was impossible. \$\endgroup\$
    – Riking
    Commented Jan 4, 2014 at 1:09
  • \$\begingroup\$ Oh, wow. I'm honestly surprised. I assumed it was impossible, but it's not. \$\endgroup\$
    – null
    Commented Jan 4, 2014 at 10:34
  • 1
    \$\begingroup\$ @xfix: Brainfuck is turing-complete so it can do anything (given the I/O constraints.) \$\endgroup\$
    – marinus
    Commented Jan 8, 2014 at 1:38
  • 3
    \$\begingroup\$ @marinus Turing completness only means it can do all computations. Brainfuck is Turing complete without I/O as you can run a program that calculates any calculation and see the result by inspecting it's memory after running. BF without I/O would make people less interested as it would be difficult to make utilities. e.g. i could never have made my lisp interpreter. \$\endgroup\$
    – Sylwester
    Commented Jan 8, 2014 at 7:37

Befunge 98 - 26 31 20 19 chars


Got rid of some massive conditionals. Now the program works as follows:

~:   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. 

q quits the program and pops the top value as an error value. The error value will be -1 1 if there are too many ]'s, 0 if they are balanced, and positive negative if there are too many ['s. If the number is positive negative, then that many the absolute value of that number ]'s are needed to balance the program.

Edit: Switched increment and decrement. [ used to increment the counter and ] used to decrement it. By switching it, I save 1 char, because for the exit condition, I only have to check if the counter is positive, rather than negative.

Old version


This code works as follows:

~    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: realized that this accepted inputs like ][, now it ends whenever the count gets negative, using

  • 1
    \$\begingroup\$ 18 bytes \$\endgroup\$
    – Jo King
    Commented Apr 9, 2018 at 8:57
  • \$\begingroup\$ @JoKing that's pretty nice, using the distance between [ and ] to do the comparison with both. \$\endgroup\$
    – Justin
    Commented Apr 9, 2018 at 15:42

GolfScript, 18 chars


This code runs successfully with exit code 0 (and prints some garbage to stdout) if the square brackets in the input are balanced. If they are not, it fails with a non-zero exit code and prints an error message to stderr, e.g.:

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


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

Since the challenge said nothing about output to stdout / stderr, I figure this qualifies. In any case, you can always redirect those to /dev/null.


The code {[]`?)}, strips everything but square brackets from the input, and the ~ evaluates the result as GolfScript code. The tricky part is that unbalanced brackets are perfectly legal in GolfScript (and, indeed, my code includes one!), so we need some other way to make the code crash.

The trick I'm using is to leave a copy of the input at the bottom of the stack, collect the entire stack into an array (using the unbalanced ]) and shift the first element off. At this point, three things can happen:

  • If the input ended in an unclosed [, trying to shift an element off an empty array will crash the interpreter (which, in this case, is exactly what we want!)
  • If the brackets in the input were balanced, the shifted element will be the original input string.
  • Otherwise (if the input had an unopened ] or an unclosed [) it will be an array.

My original 14-char entry then compared the shifted value with a string, which would crash if it was a nested array. Unfortunately, it turns out that comparing a flat (or, in particular, empty) array with a string is also legal in GolfScript, so I had to switch tack.

My current submission, instead, uses a very brute-force method to tell arrays from strings: it un-evals them and tries to find the first occurrence of [ (ASCII code 91), which will be zero if and only if the un-evaled variable was an array. If so, dividing the zero with itself triggers the desired crash.

Ps. Two other 18-char solutions are:




Alas, I haven't yet found a shorter way to solve the "empty array problem".

  • \$\begingroup\$ is this balanced?: ][ (ie does it fail in your program?) \$\endgroup\$
    – Justin
    Commented Jan 3, 2014 at 22:46
  • \$\begingroup\$ @Quincunx: It fails, as it should. \$\endgroup\$ Commented Jan 3, 2014 at 22:52
  • \$\begingroup\$ However, it did turn out to accept [[]; I've fixed it now, at the cost of 4 chars, and it passes all my tests now. \$\endgroup\$ Commented Jan 4, 2014 at 0:16
  • \$\begingroup\$ If I understand you correctly, you had a 14-char solution which fails to distinguish between a string and an array only in the case that the array is empty. 1+ will turn an empty array into a non-empty array, an non-empty array into a non-empty array, and a string into a string. \$\endgroup\$ Commented Jan 4, 2014 at 9:43
  • \$\begingroup\$ @PeterTaylor: Yes, it was .{[]`?)},~](n<. I did try your 1+, but it seems that the array needs to contain something other than a number (presumably so that the interpreter will crash when it tries to recursively compare a character with an array/string). Using n+ doesn't work either, since it coerces the array to a string; [n]+ does work, but still puts me at 18 chars. \$\endgroup\$ Commented Jan 4, 2014 at 16:19

J (38 35)

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


  • 1!:1[3: read stdin
  • '[]'=/: create a matrix where the first row is a bitmask of the [s in the input, and the second row is the ]s.
  • 1 _1*: multiply the first row by 1 and the second row by -1.
  • +/: sum the columns of the matrix together, giving delta-indentation per character
  • +/\: create a running total of these, giving indentation level at each character
  • ({:+.<./): return the GCD of the final element ({:) and the smallest element (<./). If all the braces match, both of these should be 0 so this will return 0. If the braces do not match, it will return a nonzero value.
  • exit: set the exit value to that and exit.
  • \$\begingroup\$ Nice breakdown... \$\endgroup\$ Commented Jan 3, 2014 at 20:51

ruby (64)

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

previously (68) it was:

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

Another equivalent solution uses

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

can't use size alone because it would give false negatives (!!!) when the total number of unbalanced brackets is multiple of 256

  • \$\begingroup\$ This is codegolf. I'm sure you can remove some whitespace here. Ruby is somewhat whitespace sensitive, but it ignores it in many cases. To begin with, you don't need whitespace near = operator. \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 18:03
  • \$\begingroup\$ better version (somewhat inspired by the sed+tr solution). I'm not sure I can get much better than this. At least it has as low as 4 whitespaces! \$\endgroup\$
    – rewritten
    Commented Jan 3, 2014 at 18:08
  • 1
    \$\begingroup\$ And yet, I can remove two of them. \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 18:18
  • 2
    \$\begingroup\$ I think the spaces around the 0 can go. \$\endgroup\$
    – marinus
    Commented Jan 3, 2014 at 18:23

Perl, 30 characters

Your basic Perl recursive regex to the rescue:

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

For those unfamiliar with the command-line arguments used here: -0 allows one to set the line-ending character for the purposes of file input; using -0 with no argument sets the line-ending character to EOF. -n automatically reads the input (in this case, the entire file) into $_ beforehand.

If the regex matches, it returns a true value, which is negated to 0 for the exit code. Otherwise, the false return value yields an exit code of 1.

  • \$\begingroup\$ Guess I'll have to golf my answer better to beat this 30 char solution. \$\endgroup\$
    – Justin
    Commented Jan 4, 2014 at 7:37
  • \$\begingroup\$ There. My solution is now much shorter than it was before. Nice solution. +1 \$\endgroup\$
    – Justin
    Commented Jan 4, 2014 at 9:04

bash (tr + sed) - 42

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

If you don't mind error messages then you can remove the last space between ` and ] to get length 41.

  • \$\begingroup\$ Unless I miss anything, you have useless use of cat and $() (also "[]" can be written as []). I accepted this answer, but until I will see improvements in length, I'm not going to upvote this, as while short, it could be way shorter for bash. \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 17:43
  • \$\begingroup\$ Well, actually I don't know shell scripting that well. I'm unable to make most of those work. I replaced $() with backticks and did the "[]" -> [] you suggested. \$\endgroup\$
    – shiona
    Commented Jan 3, 2014 at 17:51
  • \$\begingroup\$ There is still useless use of cat. \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 17:56
  • 1
    \$\begingroup\$ I could've sword I tried and failed this, but I was wrong. \$\endgroup\$
    – shiona
    Commented Jan 3, 2014 at 18:09

Perl (56 chars)


The obvious Perl solution: a recursive regex. Unfortunately it's a rather verbose construct.


Haskell (143)

import System.Exit
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: Using 2 guards seems to be more dense than if-then-else. Also, I don't think yours checks that the brackets are in the right order ("][" passes)

  • \$\begingroup\$ oh wow, only saw this comment when it was pointed out today. Fixed my code, but yeah nice, guards do seem to be denser (+1). \$\endgroup\$
    – jgon
    Commented Apr 10, 2018 at 1:26

C, 73 64 chars

Thanks to suggestions from breadbox (although this probably requires little-endian to work):

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

How it works:

  • implicit int global i gets initialized to 0
  • c becomes an implicit int which gets argc (initialized to 1 but we don't care, just as long as the higher bits aren't set)
  • read(0,&c,1) reads a single character into the low byte of c (on little-endian architectures) and returns 0 at EOF; i+1 != 0 unless the balanced bracket quote goes to -1; multiplying them together works as a (safe) boolean AND that takes one less char than &&
  • c==91 evaluates to 1 for '[', and c==93 evaluates to 1 for ']'. (There might be some fiddly bit-fiddling trick that would be smaller but I can't think of anything.)
  • return i exits with status code 0 if it's balanced, non-zero if it isn't. Returning -1 technically violates POSIX but nobody actually cares about that.

Previous version:

main(i){char c;i=0;while(read(0,&c,1)*(i+1))i+=(c==91)-(c==93);return i;}
  • \$\begingroup\$ Using getchar() instead of read will shorten the code and allow you to use (implicit) int instead of char for your variable. Also remember that globals are automatically initialized to zero. \$\endgroup\$
    – breadbox
    Commented Jan 4, 2014 at 0:39
  • \$\begingroup\$ Thanks, I forgot about getchar(). Not sure how the global init helps, though - defining a global int i takes more characters than using the implicit argc one. \$\endgroup\$
    – fluffy
    Commented Jan 4, 2014 at 3:17
  • 1
    \$\begingroup\$ Globals can also be implicit. Outside of a function c; defines a global int. \$\endgroup\$
    – breadbox
    Commented Jan 4, 2014 at 3:21
  • \$\begingroup\$ Meanwhile, getchar(c) ends up not making it any shorter, at least using this approach, because it needs to be tested for >=0 in some way, and an implicit int for c passed into read() isn't guaranteed to work due to endianness. \$\endgroup\$
    – fluffy
    Commented Jan 4, 2014 at 3:22
  • \$\begingroup\$ What about ][ ? I'm sure it's not balanced. Don't you have to keep track whether it goes negative at least once? \$\endgroup\$
    – vsz
    Commented Jan 4, 2014 at 9:16

Turing Machine Code, 286 272 bytes

Again, I'm using the rule table syntax defined here.

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-r
I ! ! l *
I _ _ r halt
I * * l halt-r
O ! ! r Q
O _ _ l I
O * * r *
Q ! ! r *
Q * * * W

Terminates in state halt to accept the input and halt-r to reject it.

  • \$\begingroup\$ halt-err can be shorter, such as halt* for example. \$\endgroup\$ Commented Apr 9, 2018 at 19:22

Lua, 56

os.exit(("["..io.read"*a".."]"):match"^%b[]$"and 0 or 1)
  • \$\begingroup\$ "^%b[]$" what is this? Can you explain? Surely, this isn't regex? \$\endgroup\$
    – Cruncher
    Commented Jan 3, 2014 at 17:57
  • \$\begingroup\$ @Cruncher: It's not. It's Lua pattern, not regex (Lua patterns are similar to regexes, but they aren't). In this case it matches the beginning of string (^), balanced set of [ and ] with anything inbetween (%b[]), and end of string ($). \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 18:02

GTB, 55


Misses []

Use 0 to stop.



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

StringLength@FixedPoint[r[#,"[]"-> ""]&,r[s,Except@Characters["[]"]-> ""]]
  • \$\begingroup\$ With functions name like RegularExpression` and StringLength I can never win text code golf context with Mathematica! :) \$\endgroup\$
    – Murta
    Commented Jan 4, 2014 at 1:37
  • \$\begingroup\$ I know what you mean:) ToCharacterCode is much longer than ord as well... PS: What about setting an exit code? \$\endgroup\$
    – Ajasja
    Commented Jan 4, 2014 at 10:14
  • \$\begingroup\$ Length[StringCases[s,"["|"]"]//.{x___,"[","]",y___}:>{x,y}] \$\endgroup\$
    – alephalpha
    Commented Jan 6, 2014 at 9:51

Ruby, 59 58

Scans for opening and closing bracket, counting [ as 1 and ] as -1, and exits if the count drops below 0.

$<.read.scan(/\]|\[/){exit 1if(b+=92-$&.ord)<0}
exit b
  • 1
    \$\begingroup\$ Upvoted, and shortened by one character (I removed whitespace after exit 1 in case you ask). \$\endgroup\$
    – null
    Commented Jan 3, 2014 at 21:28

Hassium, 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);}

Full expanded (note doesn't work in online interpreter as input() is disabled) here


Pyth, 25 bytes


Try it online!

Python 3 translation:
import re
if len(z):

Haskell (167,159)

Did this mostly for fun, if anyone's got any suggestions for how to make it shorter, I'd be glad to hear them tho :)

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

Edit: Fixed an issue pointed out to me in the comments (added 11 bytes).

Edit 2: Created auxiliary function for testing predicates using guards inspired by user13350, removing 8 bytes.

  • \$\begingroup\$ Fails for ][ (pointed out by user13350) \$\endgroup\$
    Commented Apr 9, 2018 at 11:56
  • \$\begingroup\$ @user202729 That's an excellent point, that was super careless. Pretty sure it's fixed now. \$\endgroup\$
    – jgon
    Commented Apr 10, 2018 at 1:25

Stax, 14 11 characters

╬Äτ↔EªÉs «Ü

Run and debug it

Credit to @recursive for -3 bytes.

ASCII equivalent:


Remove all characters except [], then remove [] until the string no longer changes. Return 1 if the final string is empty.

  • 1
    \$\begingroup\$ Nice. You can use .[]|& to filter the characters, and then re-use the literal for 11 \$\endgroup\$
    – recursive
    Commented Apr 9, 2018 at 17:38

Vyxal, 10 bytes


Try it Online!

The joys of having a balanced-bracket digraph.


‛[]↔       # remove all non "[]" from the input
    øβ¬    # are the brackets unbalanced?
       [°* # if so, multiply the input by the imaginary number `i`. Obviously you can't multiply a string by an imaginary number in python, so this errors.
  • \$\begingroup\$ The thing says 'brainfuck program', so you can safely assume that it doesn't need to remove non-[] chars. \$\endgroup\$
    – emanresu A
    Commented Dec 27, 2021 at 7:16
  • \$\begingroup\$ @emanresuA > Please note that Brainfuck programs can have other characters than [], so don't refuse the program just because it has other commands. \$\endgroup\$
    – lyxal
    Commented Dec 27, 2021 at 8:27

JCram, 13 bytes.


Encodes the ES6 program


Uiua, 23 bytes


Try it!


Setanta, 88 bytes

gniomh(s){a:=0le i idir(0,fad@s){i=s[i]a+=(i=='['|0&1)-(i==']'|0&1)ma a<0 bris}toradh!a}

Try on try-setanta.ie


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.