Content is user-generated and unverified.

Balanced parentheses in Brainfuck

Problem

Read a string made only of ( and ) characters. Output yes if the parentheses are balanced, otherwise no. An empty string is balanced.

Strategy

Maintain a depth counter, increment on (, decrement on ), and check at the end that depth is zero and no underflow ever occurred.

Phases

Read characters one at a time
Classify each: ( is ASCII 40, ) is ASCII 41, so char − 40 gives 0 for open, 1 for close; anything else terminates the loop
On (: increment depth
On ): if depth > 0, decrement; otherwise set an error flag
After the loop: if depth = 0 and error = 0, print yes; else no

Input termination

The program treats any byte that is not ( or ) as end-of-input. This handles all three common EOF conventions (0, unchanged, 255) as well as trailing newlines that some interpreters or shells append. After detecting a non-paren byte, CHAR is cleared to 0 and no further reads are attempted.

Why an error flag?

A naive approach would just decrement depth on ) and check depth = 0 at the end. But with 8-bit unsigned cells, decrementing 0 wraps to 255 — the string )( would end with depth = 1 and look balanced. The error flag catches this: any ) when depth is already zero is recorded permanently.

Character classification detail

After computing d = char − 40:

If d == 0: it is ( (open paren)
If d == 1: it is ) (close paren)
Otherwise: invalid byte — clear CHAR to exit the main loop

The d == 1 test works by decrementing d by one and checking for zero, but only when d was already confirmed nonzero (guarded by the d == 0 test), preventing a false wrap from 0 to 255.

Memory layout

text

  Cell  Purpose
  ────  ────────────────────────────
   0    depth counter
   1    error flag (1 = saw underflow)
   2    current input character
   3–9  work cells (classification, if-else logic)

Raw code (1098 characters)

brainfuck

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

Test results

text

Input       Expected  EOF=0  EOF=unch  EOF=255
──────────  ────────  ─────  ───────  ───────
()()"       yes       OK     OK       OK
((()))      yes       OK     OK       OK
())(        no        OK     OK       OK
(           no        OK     OK       OK
(empty)     yes       OK     OK       OK
(()())      yes       OK     OK       OK
()          yes       OK     OK       OK

All cases also verified with a trailing newline appended.

Content is user-generated and unverified.