# Balanced brackets

• Generate a string with   N   opening brackets   [   and with   N   closing brackets   ],   in some arbitrary order.
• Determine whether the generated string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest.
Balanced brackets
You are encouraged to solve this task according to the task description, using any language you may know.

Examples
   (empty)      OK
[]           OK
[][]         OK
[[][]]       OK
][         NOT OK
][][       NOT OK
[]][[]     NOT OK


## 11l

Translation of: Python
F gen(n)
V txt = [‘[’, ‘]’] * n
random:shuffle(&txt)
R txt.join(‘’)

F is_balanced(s)
V nesting_level = 0
L(c) s
S c
‘[’
nesting_level++
‘]’
I --nesting_level < 0
R 0B
R 1B

L(n) 0..9
V s = gen(n)
print(s‘’(‘ ’ * (20 - s.len))‘is ’(I is_balanced(s) {‘balanced’} E ‘not balanced’))
Output:
                    is balanced
[]                  is balanced
[]][                is not balanced
][[[]]              is not balanced
[]][][[]            is not balanced
][[][[[]]]          is not balanced
[[]]][[][]][        is not balanced
[[]][[]]]][[][      is not balanced
[]]][[[[]]]]][[[    is not balanced
]][]]][[[[[]][]][[  is not balanced


## 360 Assembly

*        Balanced brackets         28/04/2016
BALANCE  CSECT
USING  BALANCE,R13        base register and savearea pointer
SAVEAREA B      STM-SAVEAREA(R15)
DC     17F'0'
STM      STM    R14,R12,12(R13)
ST     R13,4(R15)
ST     R15,8(R13)
LA     R8,1               i=1
LOOPI    C      R8,=F'20'          do i=1 to 20
BH     ELOOPI
MVC    C(20),=CL20' '     c=' '
LA     R1,1
LA     R2,10
BAL    R14,RANDOMX
LR     R11,R0             l=randomx(1,10)
SLA    R11,1              l=l*2
LA     R10,1              j=1
LOOPJ    CR     R10,R11            do j=1 to 2*l
BH     ELOOPJ
LA     R1,0
LA     R2,1
BAL    R14,RANDOMX
LR     R12,R0             m=randomx(0,1)
LTR    R12,R12            if m=0
BNZ    ELSEM
MVI    Q,C'['             q='['
B      EIFM
ELSEM    MVI    Q,C']'             q=']'
EIFM     LA     R14,C-1(R10)       @c(j)
MVC    0(1,R14),Q         c(j)=q
LA     R10,1(R10)         j=j+1
B      LOOPJ
ELOOPJ   BAL    R14,CHECKBAL
LR     R2,R0
C      R2,=F'1'           if checkbal=1
BNE    ELSEC
MVC    PG+24(2),=C'ok'    rep='ok'
B      EIFC
ELSEC    MVC    PG+24(2),=C'? '    rep='? '
EIFC     XDECO  R8,XDEC            i
MVC    PG+0(2),XDEC+10
MVC    PG+3(20),C
XPRNT  PG,26
LA     R8,1(R8)           i=i+1
B      LOOPI
ELOOPI   L      R13,4(0,R13)
LM     R14,R12,12(R13)
XR     R15,R15            set return code to 0
BR     R14 -------------- end
CHECKBAL CNOP   0,4 -------------- checkbal
SR     R6,R6              n=0
LA     R7,1               k=1
LOOPK    C      R7,=F'20'          do k=1 to 20
BH     ELOOPK
LR     R1,R7              k
LA     R4,C-1(R1)         @c(k)
MVC    CI(1),0(R4)        ci=c(k)
CLI    CI,C'['            if ci='['
BNE    NOT1
LA     R6,1(R6)           n=n+1
NOT1     CLI    CI,C']'            if ci=']'
BNE    NOT2
BCTR   R6,0               n=n-1
NOT2     LTR    R6,R6              if n<0
BNM    NSUP0
SR     R0,R0              return(0)
B      RETCHECK
NSUP0    LA     R7,1(R7)           k=k+1
B      LOOPK
ELOOPK   LTR    R6,R6              if n=0
BNZ    ELSEN
LA     R0,1               return(1)
B      RETCHECK
ELSEN    SR     R0,R0              return(0)
RETCHECK BR     R14 -------------- end checkbal
RANDOMX  CNOP   0,4 -------------- randomx
LR     R3,R2              i2
SR     R3,R1              ii=i2-i1
L      R5,SEED
M      R4,=F'1103515245'
A      R5,=F'12345'
SRDL   R4,1               shift to improve the algorithm
ST     R5,SEED            seed=(seed*1103515245+12345)>>1
LR     R6,R3              ii
LA     R6,1(R6)           ii+1
L      R5,SEED            seed
LA     R4,0               clear
DR     R4,R6              seed//(ii+1)
AR     R4,R1              +i1
LR     R0,R4              return(seed//(ii+1)+i1)
BR     R14 -------------- end randomx
SEED     DC     F'903313037'
C        DS     20CL1
Q        DS     CL1
CI       DS     CL1
PG       DC     CL80' '
XDEC     DS     CL12
REGS
END    BALANCE
Output:
 1 ][[[][[]             ?
2 ]][]][][[[[][[       ?
3 []                   ok
4 ][                   ?
5 ][[][]]]]]           ?
6 ][]]                 ?
7 ]][][][]]]           ?
8 [[[[][[[[][[]]       ?
9 ][[]][[[[[[[[[]]][   ?
10 ]]]][][[][]]][][[[   ?
11 [][[]][][][[[]       ?
12 ]]                   ?
13 [][[[]]]             ok
14 ][                   ?
15 []][                 ?
16 ][[]][]]][[]         ?
17 ][][]]               ?
18 []                   ok
19 [[[[[[][[[[[][][     ?
20 [[][[][]             ?


## AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
or android 64 bits with application Termux
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program balencebrac64.s   */

/************************************/
/* Constantes                       */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessResult:          .asciz "Expression : "
szMessBalenced:        .asciz " balanced"
szMessNotBalenced:     .asciz " not balanced"
szMessStart:           .asciz "Program 64 bits start.\n"
szCarriageReturn:      .asciz "\n"

/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:             .skip 24   // conversion buffer
sBuffer:               .skip 80
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main
main:                            // entry of program
bl affichageMess

mov x0,0b111000              // bit 1 = open bracket bit 0 = close bracket
bl testBalanced

mov x0,0b110100
bl testBalanced
mov x0,0b11001001
bl testBalanced

mov x19,10                   // number random test
1:
mov x0,1                     // mini number
mov x1,10000                 // maxi random number
bl extRandom                 // generate random number
bl testBalanced
subs x19,x19,1
bge 1b

100:                             // standard end of the program
mov x0, #0                   // return code
mov x8,EXIT
svc #0                       // perform the system call

/***************************************************/
/*   routine to test expression                    */
/***************************************************/
/* x0 expression   */
testBalanced:
stp x1,lr,[sp,-16]!      // save  registres
stp x2,x3,[sp,-16]!      // save  registres
bl isBalanced
cmp x0,0
csel x3,x3,x4,eq

mov x0,#4                    // string number to display
bl displayStrings            // display message
100:
ldp x2,x3,[sp],16         // restaur registres
ldp x1,lr,[sp],16         // restaur registres
ret
/***************************************************/
/*   control if expression is balenced             */
/***************************************************/
/* x0 expression   */
/* x0 return 1 if balanced else zero */
isBalanced:
stp x1,lr,[sp,-16]!   // save  registres
stp x2,x3,[sp,-16]!   // save  registres
mov x3,63
clz x2,x0             // number of zeros on the left
sub x2,x3,x2          // so many useful numbers right
mov x4,1              // mask to test bit
lsl x4,x4,x2          // shift left begin expression
mov x3,0              // top if right bracket > left bracket
mov x7,0              // indice display buffer expression
mov x5,0              // counter brackets
1:                        // begin loop to test bits
tst x0,x4
beq 2f                // bit = 0
mov x6,'('            // else bit = 1 -> open bracket
strb w6,[x1,x7]       // store in buffer
add x5,x5,1           // increment open bracket
b 3f
2:                        // bit = 0
mov x6,')'            // close bracket
strb w6,[x1,x7]       // store in buffer
subs x5,x5,1          // decrement open bracket
bge 3f                // if negative
mov x3,1              // top error
3:
lsr x4,x4,1           // shift mask right
cbnz x4,1b            // and loop if not zero
strb wzr,[x1,x7]      // zero final on buffer
cmp x5,0              // right bracket <> left bracket -> error
bne 4f
cmp x3,0              // in expression left bracket > right bracket
bne 4f
mov x0,1              // balanced
b 100f
4:
mov x0,0              // not balanced
100:
ldp x2,x3,[sp],16     // restaur registres
ldp x1,lr,[sp],16     // restaur registres
ret
/***************************************************/
/*   display multi strings                         */
/*   new version 24/05/2023                        */
/***************************************************/
/* x0  contains number strings address */
displayStrings:            // INFO:  displayStrings
stp x8,lr,[sp,-16]!    // save  registers
stp x2,fp,[sp,-16]!    // save  registers
add fp,sp,#32          // save paraméters address (4 registers saved * 8 bytes)
mov x8,x0              // save strings number
cmp x8,#0              // 0 string -> end
ble 100f
mov x0,x1              // string 1
bl affichageMess
cmp x8,#1              // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x8,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x8,#3
ble 100f
mov x0,x4
bl affichageMess
cmp x8,#4
ble 100f
mov x0,x5
bl affichageMess
cmp x8,#5
ble 100f
mov x0,x6
bl affichageMess
cmp x8,#6
ble 100f
mov x0,x7
bl affichageMess

100:
ldp x2,fp,[sp],16        // restaur  registers
ldp x8,lr,[sp],16        // restaur  registers
ret
/******************************************************************/
/*     random number                                          */
/******************************************************************/
/*  x0 contains inferior value */
/*  x1 contains maxi value */
/*  x0 return random number */
extRandom:
stp x1,lr,[sp,-16]!        // save  registers
stp x2,x8,[sp,-16]!        // save  registers
stp x19,x20,[sp,-16]!      // save  registers
sub sp,sp,16               // reserve 16 octets on stack
mov x19,x0
mov x0,sp                  // store result on stack
mov x1,8                   // length 8 bytes
mov x2,0
mov x8,278                 //  call system Linux 64 bits Urandom
svc 0
mov x0,sp                  // load résult on stack
ldr x0,[x0]
sub x2,x20,x19             // calculation of the range of values
udiv x1,x0,x2              // calculation range modulo
msub x0,x1,x2,x0
100:
ldp x19,x20,[sp],16        // restaur  2 registers
ldp x2,x8,[sp],16          // restaur  2 registers
ldp x1,lr,[sp],16          // restaur  2 registers
ret                        // retour adresse lr x30
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"
Output:
Program 64 bits start.
Expression : ((())) balanced
Expression : (()()) balanced
Expression : (())())( not balanced
Expression : ((()))))()))) not balanced
Expression : (()())())())) not balanced
Expression : ()(((()((()) not balanced
Expression : ())()(()())() not balanced
Expression : ())))((()))((( not balanced
Expression : (())()())(() not balanced
Expression : ())()))))(()( not balanced
Expression : ())()(())(()( not balanced
Expression : ())(()(()())) not balanced
Expression : ((()))()))))) not balanced
Expression : (()))((()))( not balanced


## ABAP

CLASS lcl_balanced_brackets DEFINITION.
PUBLIC SECTION.
CLASS-METHODS:
class_constructor,

are_brackets_balanced
IMPORTING
seq                            TYPE string
RETURNING
VALUE(r_are_brackets_balanced) TYPE abap_bool,

get_random_brackets_seq
IMPORTING
n                    TYPE i
RETURNING
VALUE(r_bracket_seq) TYPE string.

PRIVATE SECTION.
CLASS-DATA: random_int TYPE REF TO cl_abap_random_int.

CLASS-METHODS:
_split_string
IMPORTING
i_text         TYPE string
RETURNING
VALUE(r_chars) TYPE stringtab,

_rand_bool
RETURNING
VALUE(r_bool) TYPE i.
ENDCLASS.

CLASS lcl_balanced_brackets IMPLEMENTATION.
METHOD class_constructor.
random_int = cl_abap_random_int=>create( seed = CONV #( sy-uzeit )
min  = 0
max  = 1 ).
ENDMETHOD.

METHOD are_brackets_balanced.
DATA: open_bracket_count TYPE i.

DATA(chars) = _split_string( seq ).

r_are_brackets_balanced = abap_false.

LOOP AT chars ASSIGNING FIELD-SYMBOL(<c>).
IF <c> = ']' AND open_bracket_count = 0.
RETURN.
ENDIF.

IF <c> = ']'.
open_bracket_count = open_bracket_count - 1.
ENDIF.

IF <c> = '['.
open_bracket_count = open_bracket_count + 1.
ENDIF.
ENDLOOP.

IF open_bracket_count > 0.
RETURN.
ENDIF.

r_are_brackets_balanced = abap_true.
ENDMETHOD.

METHOD get_random_brackets_seq.
DATA(itab) = VALUE stringtab( FOR i = 1 THEN i + 1 WHILE i <= n
( COND #( WHEN _rand_bool( ) = 0 THEN '['
ELSE ']' ) ) ).
r_bracket_seq = concat_lines_of( itab ).
ENDMETHOD.

METHOD _rand_bool.
r_bool = random_int->get_next( ).
ENDMETHOD.

METHOD _split_string.
DATA: off TYPE i VALUE 0.

DO strlen( i_text ) TIMES.
INSERT i_text+off(1) INTO TABLE r_chars.
off = off + 1.
ENDDO.
ENDMETHOD.
ENDCLASS.

START-OF-SELECTION.
DO 10 TIMES.
DATA(seq) = lcl_balanced_brackets=>get_random_brackets_seq( 10 ).
cl_demo_output=>write( |{ seq } => { COND string( WHEN lcl_balanced_brackets=>are_brackets_balanced( seq ) = abap_true THEN 'OK'
ELSE 'NOT OK' ) }| ).
ENDDO.
cl_demo_output=>display( ).

Output:
[[]][[]]]] => NOT OK

][]][[][][ => NOT OK

[][]]][[[] => NOT OK

][][[[][[] => NOT OK

[[[][]]][] => OK

][][]][[[[ => NOT OK

][][[[[]][ => NOT OK

][[][]][[] => NOT OK

[[]][[]][] => OK

[][]]][]]] => NOT OK



## Action!

PROC Generate(BYTE size CHAR ARRAY s)
BYTE i,half

s(0)=size
half=size RSH 1

FOR i=1 TO half
DO s(i)='[ OD

FOR i=half+1 TO size
DO s(i)='] OD
RETURN

PROC Shuffle(CHAR ARRAY s)
BYTE i,j,k,n,len,tmp

len=s(0)
n=Rand(len+1)
FOR k=1 TO n
DO
i=Rand(len)+1
j=Rand(len)+1
tmp=s(i)
s(i)=s(j)
s(j)=tmp
OD
RETURN

BYTE FUNC Balanced(CHAR ARRAY s)
INT i,lev

lev=0
FOR i=1 TO s(0)
DO
IF s(i)='[ THEN
lev==+1
ELSE
lev==-1
FI

IF lev<0 THEN
RETURN (0)
FI
OD

IF lev#0 THEN
RETURN (0)
FI
RETURN (1)

PROC Main()
CHAR ARRAY s(20)
BYTE i,b

FOR i=0 TO 20 STEP 2
DO
Generate(i,s)
Shuffle(s)
b=Balanced(s)

IF s(0)=0 THEN
Print("(empty)")
ELSE
Print(s)
FI
Print(" is ")
IF b=0 THEN
Print("not ")
FI
PrintE("balanced")
OD
RETURN
Output:
(empty) is balanced
[] is balanced
[[]] is balanced
][][[] is not balanced
[]][[][] is not balanced
[[[]]]][[] is not balanced
[[[[[[]]]]]] is balanced
[[]][[[][]]][] is balanced
[[[[]][[]]]][]][ is not balanced
][][][[[[[]]][]]][ is not balanced
[[[[][][][][]][]]][] is balanced


## Acurity Architect

Using #HASH-OFF

FUNCTION bBRACKETS_MATCH(zStringWithBrackets: STRING): STRING
VAR sCount: SHORT
VAR sBracketCounter: SHORT
VAR zOK: STRING
//
SET zOK = "NOT OK"
DO sCount = 1 TO LENGTH(zStringWithBrackets)
CASE SUBSTR(zStringWithBrackets, sCount, 1)
VALUE "["
SET sBracketCounter = sBracketCounter + 1
VALUE "]"
SET sBracketCounter = sBracketCounter - 1
ENDCASE
ENDDO
IF sBracketCounter = 0
SET zOK = "OK"
ENDIF
RETURN zOK
ENDFUNCTION
Output:
bBRACKETS_MATCH("[][][][][][][[[[[]]]]]") = "OK"
bBRACKETS_MATCH("sdapasd[a]dfa[fdf][f]a[era[d]as[a]sd[as][da]s[") = "NOT OK"
bBRACKETS_MATCH("3r acwf4[a][ a]sg5s]4t[5e4][taw][ra][r] c[ra]2[r]") = "NOT OK"
bBRACKETS_MATCH("234 rq4ctac3rc[q2 ]r[q4tq4 ]t[4v5 y7 [e6y[]a[45 rv[2q]5q[2q3") = "NOT OK"


with Ada.Numerics.Discrete_Random;
procedure Brackets is
package Random_Positive is new Ada.Numerics.Discrete_Random (Positive);
Positive_Generator : Random_Positive.Generator;
procedure Swap (Left, Right : in out Character) is
Temp : constant Character := Left;
begin
Left := Right;
Right := Temp;
end Swap;
function Generate_Brackets (Bracket_Count : Natural;
Opening_Bracket : Character := '[';
Closing_Bracket : Character := ']')
return String is
All_Brackets : String := Bracket_Count * Opening_Bracket & Bracket_Count * Closing_Bracket;
begin
for I in All_Brackets'Range loop
Swap (All_Brackets (I), All_Brackets (Random_Positive.Random (Positive_Generator) mod (Bracket_Count * 2) + 1));
end loop;
return All_Brackets;
end Generate_Brackets;

function Check_Brackets (Test : String;
Opening_Bracket : Character := '[';
Closing_Bracket : Character := ']')
return Boolean is
Open : Natural := 0;
begin
for I in Test'Range loop
if Test (I) = Opening_Bracket then
Open := Open + 1;
elsif Test (I) = Closing_Bracket then
if Open = 0 then
return False;
else
Open := Open - 1;
end if;
end if;
end loop;
return True;
end Check_Brackets;
begin
Random_Positive.Reset (Positive_Generator);
for I in 0 .. 4 loop
for J in 0 .. I loop
declare
My_String : constant String := Generate_Brackets (I);
begin
Ada.Text_IO.Put_Line (My_String & ": " & Boolean'Image (Check_Brackets (My_String)));
end;
end loop;
end loop;
end Brackets;


Output:

Brackets
: TRUE
[]: TRUE
][: FALSE
[]][: FALSE
][][: FALSE
][][: FALSE
[[]]][: FALSE
[][][]: TRUE
[]]][[: FALSE
][][][: FALSE
]]][[[[]: FALSE
[[[]][]]: TRUE
[][][]][: FALSE
[[][]]][: FALSE
[]]]][[[: FALSE

## Aime

unbalanced(data s)
{
integer b, i;

b = i = 0;
while (i + ~s && -1 < b) {
b += s[i -= 1] == '[' ? -1 : 1;
}

b;
}

generate(data b, integer d)
{
if (d) {
d.times(l_bill, list(), -1, '[', ']').l_rand().ucall(b_append, 1, b);
}
}

main(void)
{
integer i;

i = 0;
while (i < 10) {
data s;

generate(s, i);
o_(s, " is ", unbalanced(s) ? "un" : "", "balanced\n");

i += 1;
}

0;
}

Sample output:

 is balanced
][ is unbalanced
]][[ is unbalanced
]]][[[ is unbalanced
[[]][][] is balanced
[[][]][][] is balanced
[]]]][][[][[ is unbalanced
][[[]][[][]]][ is unbalanced
[][[[][[]]]]][][ is unbalanced
[[][[[[][]]][][]]] is balanced

## ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.win32
# generates a string of random opening and closing brackets. The number of    #
# each type of brackets is speccified in length                               #
PROC get brackets = ( INT length ) STRING:
BEGIN
INT   result length = length * 2;
[ 1 : result length ]CHAR result;
# initialise the brackets to all open brackets                        #
FOR char pos TO result length DO result[ char pos ] := "[" OD;
# set half of the brackets to close brackets                          #
INT   close count := 0;
WHILE close count < length
DO
INT   random pos = 1 + ENTIER ( next random * result length );
IF result[ random pos ] = "["
THEN
close count          +:= 1;
result[ random pos ]  := "]"
FI
OD;
result
END # get brackets # ;

# returns TRUE if the brackets string contains a correctly nested sequence    #
# of brackets, FALSE otherwise                                                #
PROC check brackets = ( STRING brackets ) BOOL:
BEGIN
INT depth := 0;
FOR char pos FROM LWB brackets TO UPB brackets
WHILE
IF brackets[ char pos ] = "["
THEN
depth +:= 1
ELSE
depth -:= 1
FI;
depth >= 0
DO
SKIP
OD;
# depth will be 0 if we reached the end of the string and it was     #
# correct, non-0 otherwise                                           #
depth = 0
END # check brackets # ;

# procedure to test check brackets                                           #
PROC test check brackets = ( STRING brackets ) VOID:
print( ( ( brackets
+ ": "
+ IF check brackets( brackets ) THEN "ok" ELSE "not ok" FI
)
, newline
)
) ;

# test the bracket generation and checking PROCs                             #
test check brackets( get brackets( 0 ) );
FOR length TO 12
DO
TO 2
DO
test check brackets( get brackets( length ) )
OD
OD
Output:
: ok
[]: ok
][: not ok
[][]: ok
[]][: not ok
[]]][[: not ok
[[]][]: ok
]]][[][[: not ok
[[][[]]]: ok
[][]]][[][: not ok
[[[[]]]][]: ok
]][]]][[[[][: not ok
[[[][[[]]]]]: ok
[[[]]][[][[]]]: ok
[][[][][][][]]: ok
[]]][][]][[[[]][: not ok
]][]][][[[][][][: not ok
][][]][]][]][[[[[]: not ok
]]][[][][][[[][]][: not ok
[[[[][][]][]]][[]]][: not ok
][]][]]][][][][][[[[: not ok
][][]][[][[[[]][][[]]]: not ok
]][[[]][[[[]]]][[[]]][: not ok
]][][]]][]][][]][[[[[[][: not ok
]]][][][]][][[]][[[][][[: not ok


## Amazing Hopper

#include <basico.h>

algoritmo

braizq="[", brader="]" // bug de Hopper :(

largo de datos=0
preparar datos (DATA_BRACKET)
obtener tamaño de datos, menos '1', guardar en 'largo de datos'

iterar

bra="", obtener dato, guardar en 'bra'

i=1, b=0, error_pos=""
iterar grupo( ++i, #( i<=len(bra) && is not neg (b) ),\
#( b += ((bra[i]==braizq) - (bra[i]==brader)) )\
#( error_pos = cat(replicate(" ",i-1),"^\n") ) )

solo si ( #(is pos(b)),\
#( error_pos=cat(cat(" ",error_pos),"(missing closed bracket)\n\n")))

solo si ( #(is neg(b)),\
#( error_pos=cat(error_pos,"(extra closed bracket)\n\n")))

imprimir ( #( rpad(" ",40,bra) ), ": ", \
solo si (b, "un"), "balanced\n",\
solo si (b, error_pos) )

mientras ' largo de datos-- '

terminar

subrutinas

DATA_BRACKET:
datos ("","[ [ ] [ [[] ][] ] [[]] ]","[[ ][[[ ][ ]]",\
"[][][[]]][","][[]][] [[[]]] [][]","[][]  [][][[]]",\
"[ a-b * [c/d] + [[10 * sin 30 ]-1] ]",\
"[ a-b * [c/d] + [[10 * sin 30 ]]-1] ]")
back

Output:
                                        : balanced
[ [ ] [ [[] ][] ] [[]] ]                : balanced
[[ ][[[ ][ ]]                           : unbalanced
^
(missing closed bracket)

[][][[]]][                              : unbalanced
^
(extra closed bracket)

][[]][] [[[]]] [][]                     : unbalanced
^
(extra closed bracket)

[][]  [][][[]]                          : balanced
[ a-b * [c/d] + [[10 * sin 30 ]-1] ]    : balanced
[ a-b * [c/d] + [[10 * sin 30 ]]-1] ]   : unbalanced
^
(extra closed bracket)


## ANTLR

### Java

grammar balancedBrackets ;

options {
language = Java;
}

bb	:	{System.out.print("input is: ");} (balancedBrackets {System.out.print($balancedBrackets.text);})* NEWLINE {System.out.println();} ; balancedBrackets : OpenBracket balancedBrackets* CloseBracket ; OpenBracket : '[' ; CloseBracket : ']' ; NEWLINE : '\r'? '\n' ;  Produces:  input is: [] input is: [] ][ input is: line 1:0 missing NEWLINE at ']' [][] input is: [][] ][][ input is: line 1:0 missing NEWLINE at ']' [[][]] input is: [[][]] []][[] input is: []line 1:2 missing NEWLINE at ']'  ## APL Works with: Dyalog APL These are a function to generate a random string of N brackets of each type, and a function to check whether a given string of brackets is balanced. gen ← (⊂+?+)⍨ ⌷ ('[]'/⍨⊢) bal ← (((|≡⊢)+\) ∧ 0=+/)(+⌿1 ¯1×[1]'[]'∘.=⊢)  Sample run for 0..N..10:  ↑{br←gen ⍵ ⋄ br,': ',(1+bal br)⊃'Bad' 'Good'}¨0,⍳10 : Good []: Good ][][: Bad [][[]]: Good []]][[][: Bad ][][[[[]]]: Bad ][][][][][[]: Bad ][[[][[][]][]]: Bad [[][[]]][[[[]]]]: Good [[[]][[[[][]][]]]]: Good ]][][][][[][][]][[[]: Bad  ## AppleScript Translation of: JavaScript (ES6 functionally composed version) -- CHECK NESTING OF SQUARE BRACKET SEQUENCES --------------------------------- -- Zero-based index of the first problem (-1 if none found): -- imbalance :: String -> Integer on imbalance(strBrackets) script on errorIndex(xs, iDepth, iIndex) set lngChars to length of xs if lngChars > 0 then set iNext to iDepth + cond(item 1 of xs = "[", 1, -1) if iNext < 0 then -- closing bracket unmatched iIndex else if lngChars > 1 then -- continue recursively errorIndex(items 2 thru -1 of xs, iNext, iIndex + 1) else -- end of string cond(iNext = 0, -1, iIndex) end if end if else cond(iDepth = 0, -1, iIndex) end if end errorIndex end script result's errorIndex(characters of strBrackets, 0, 0) end imbalance -- TEST ---------------------------------------------------------------------- -- Random bracket sequences for testing -- brackets :: Int -> String on randomBrackets(n) -- bracket :: () -> String script bracket on |λ|(_) cond((random number) < 0.5, "[", "]") end |λ| end script intercalate("", map(bracket, enumFromTo(1, n))) end randomBrackets on run set nPairs to 6 -- report :: Int -> String script report property strPad : concat(replicate(nPairs * 2 + 4, space)) on |λ|(n) set w to n * 2 set s to randomBrackets(w) set i to imbalance(s) set blnOK to (i = -1) set strStatus to cond(blnOK, "OK", "problem") set strLine to "'" & s & "'" & ¬ (items (w + 2) thru -1 of strPad) & strStatus set strPointer to cond(blnOK, ¬ "", linefeed & concat(replicate(i + 1, space)) & "^") intercalate("", {strLine, strPointer}) end |λ| end script linefeed & ¬ intercalate(linefeed, ¬ map(report, enumFromTo(1, nPairs))) & linefeed end run -- GENERIC FUNCTIONS --------------------------------------------------------- -- map :: (a -> b) -> [a] -> [b] on map(f, xs) tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to |λ|(item i of xs, i, xs) end repeat return lst end tell end map -- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs) tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) end repeat return v end tell end foldl -- Text -> [Text] -> Text on intercalate(strText, lstText) set {dlm, my text item delimiters} to {my text item delimiters, strText} set strJoined to lstText as text set my text item delimiters to dlm return strJoined end intercalate -- concat :: [[a]] -> [a] | [String] -> String on concat(xs) script append on |λ|(a, b) a & b end |λ| end script if length of xs > 0 and class of (item 1 of xs) is string then set empty to "" else set empty to {} end if foldl(append, empty, xs) end concat -- Egyptian multiplication - progressively doubling a list, appending -- stages of doubling to an accumulator where needed for binary -- assembly of a target length -- replicate :: Int -> a -> [a] on replicate(n, a) set out to {} if n < 1 then return out set dbl to {a} repeat while (n > 1) if (n mod 2) > 0 then set out to out & dbl set n to (n div 2) set dbl to (dbl & dbl) end repeat return out & dbl end replicate -- Value of one of two expressions -- cond :: Bool -> a -> b -> c on cond(bln, f, g) if bln then set e to f else set e to g end if if class of e is handler then mReturn(e)'s |λ|() else e end if end cond -- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n) if m > n then set d to -1 else set d to 1 end if set lst to {} repeat with i from m to n by d set end of lst to i end repeat return lst end enumFromTo -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f) if class of f is script then f else script property |λ| : f end script end if end mReturn  Sample output: '][' problem ^ '[][[' problem ^ '[[][]]' OK '][][[][[' problem ^ '[]][][[][]' problem ^ '[[[][]]]][][' problem ^ ## ARM Assembly .data balanced_message: .ascii "OK\n" unbalanced_message: .ascii "NOT OK\n" .text .equ balanced_msg_len, 3 .equ unbalanced_msg_len, 7 BalancedBrackets: mov r1, #0 mov r2, #0 mov r3, #0 process_bracket: ldrb r2, [r0, r1] cmp r2, #0 beq evaluate_balance cmp r2, #'[' addeq r3, r3, #1 cmp r2, #']' subeq r3, r3, #1 cmp r3, #0 blt unbalanced add r1, r1, #1 b process_bracket evaluate_balance: cmp r3, #0 beq balanced unbalanced: ldr r1, =unbalanced_message mov r2, #unbalanced_msg_len b display_result balanced: ldr r1, =balanced_message mov r2, #balanced_msg_len display_result: mov r7, #4 mov r0, #1 svc #0 mov pc, lr ## Arturo isBalanced: function [s][ cnt: 0 loop split s [ch][ if? ch="]" [ cnt: cnt-1 if cnt<0 -> return false ] else [ if ch="[" -> cnt: cnt+1 ] ] cnt=0 ] loop 1..10 'i [ str: join map 0..(2*i)-1 [x][ sample ["[" "]"]] prints str if? isBalanced str -> print " OK" else -> print " Not OK" ]  Output: [] OK [[[] Not OK [][][] OK [[][[]]] OK [[[[[][[]] Not OK [[]][[[]]][] OK ][[]][][[[[[[] Not OK ]][[]]][[[]]][]] Not OK ][[[[[[]]][]]][][] Not OK []][][][]]][[[[][][] Not OK ## AutoHotkey ; Generate 10 strings with equal left and right brackets Loop, 5 { B = %A_Index% loop 2 { String = Loop % B String .= "[n" Loop % B String .= "]n" Sort, String, Random StringReplace, String, String,n,,All Example .= String " - " IsBalanced(String) "n" } } MsgBox % Example return IsBalanced(Str) { Loop, PARSE, Str { If A_LoopField = [ i++ Else if A_LoopField = ] i-- If i < 0 return "NOT OK" } Return "OK" }  Output: ][ - NOT OK ][ - NOT OK [][] - OK [[]] - OK []][[] - NOT OK ]][[[] - NOT OK ][[]][][ - NOT OK [][[[]]] - OK [][]]][[[] - NOT OK [[][[]]][] - OK  A second example repeatedly replacing []: Loop, 5 { B = %A_Index% loop 2 { String = Loop % B String .= "[n" Loop % B String .= "]n" Sort, String, Random StringReplace, String, String,n,,All Example .= String " - " IsBalanced(String) "n" } } MsgBox % Example return IsBalanced(Str){ While (Instr(Str,"[]")) StringReplace, Str, Str,[],,All Return Str ? "False" : "True" }  Sample output: [] - True ][ - False ]][[ - False []][ - False [[]]][ - False ]][[[] - False [][]]][[ - False []][][][ - False [[[][]][]] - True [][][[[]]] - True  ## AutoIt #include <Array.au3> Local$Array[1]
_ArrayAdd($Array, "[]") _ArrayAdd($Array, "[][]")
_ArrayAdd($Array, "[[][]]") _ArrayAdd($Array, "][")
_ArrayAdd($Array, "][][") _ArrayAdd($Array, "[]][[]")

For $i = 0 To UBound($Array) -1
Balanced_Brackets($Array[$i])
If @error Then
ConsoleWrite($Array[$i] &" = NOT OK"&@CRLF)
Else
ConsoleWrite($Array[$i] &" = OK"&@CRLF)
EndIf
Next

Func Balanced_Brackets($String) Local$cnt = 0
$Split = Stringsplit($String, "")
For $i = 1 To$Split[0]
If $split[$i] = "[" Then $cnt += 1 If$split[$i] = "]" Then$cnt -= 1
If $cnt < 0 Then Return SetError(1,0,0) Next Return 1 EndFunc  ## AWK #!/usr/bin/awk -f BEGIN { print isbb("[]") print isbb("][") print isbb("][][") print isbb("[][]") print isbb("[][][]") print isbb("[]][[]") } function isbb(x) { s = 0 for (k=1; k<=length(x); k++) { c = substr(x,k,1) if (c=="[") {s++} else { if (c=="]") s-- } if (s<0) {return 0} } return (s==0) }  Output: 1 0 0 1 1 0 ## BaCon FOR len = 0 TO 18 STEP 2 str$ = ""
DOTIMES len
str$= str$ & CHR$(IIF(RANDOM(2) = 0, 91, 93)) DONE status = 0 FOR x = 1 TO LEN(str$)
IF MID$(str$, x, 1) = "[" THEN
INCR status
ELSE
DECR status
FI
IF status < 0 THEN BREAK
NEXT

IF status = 0 THEN
PRINT "OK: ", str$ELSE PRINT "BAD: ", str$
ENDIF
NEXT
Output:
OK:
OK: []
OK: [[]][]
OK: [[[][]]]
OK: [[][][][][][]]
BAD: ][][][][[[[[][]]][

## BASIC

Works with: QBasic
DECLARE FUNCTION checkBrackets% (brackets AS STRING)
DECLARE FUNCTION generator$(length AS INTEGER) RANDOMIZE TIMER DO x$ = generator$(10) PRINT x$,
IF checkBrackets(x$) THEN PRINT "OK" ELSE PRINT "NOT OK" END IF LOOP WHILE LEN(x$)

FUNCTION checkBrackets% (brackets AS STRING)
'returns -1 (TRUE) if everything's ok, 0 (FALSE) if not
DIM L0 AS INTEGER, sum AS INTEGER

FOR L0 = 1 TO LEN(brackets)
SELECT CASE MID$(brackets, L0, 1) CASE "[" sum = sum + 1 CASE "]" sum = sum - 1 END SELECT IF sum < 0 THEN checkBrackets% = 0 EXIT FUNCTION END IF NEXT IF 0 = sum THEN checkBrackets% = -1 ELSE checkBrackets% = 0 END IF END FUNCTION FUNCTION generator$ (length AS INTEGER)
z = INT(RND * length)
IF z < 1 THEN generator$= "": EXIT FUNCTION REDIM x(z * 2) AS STRING FOR i = 0 TO z STEP 2 x(i) = "[" x(i + 1) = "]" NEXT FOR i = 1 TO UBOUND(x) z = INT(RND * 2) IF z THEN SWAP x(i), x(i - 1) NEXT xx$ = ""
FOR i = 0 TO UBOUND(x)
xx$= xx$ + x(i)
NEXT
generator$= xx$
END FUNCTION

Output:
 [][[][][]]    OK
][[[]]        NOT OK
[][]          OK
[]][][][[]    NOT OK
[][[]][[]]    OK
][][[]        NOT OK
][[]          NOT OK
][][[]][][    NOT OK
][[[][]]      NOT OK
][][[[]]      NOT OK
][[]][        NOT OK
OK

### Applesoft BASIC

The MSX BASIC solution works without any changes.

### BASIC256

Translation of: Yabasic
s$= "[[]][]" print s$; " = ";

if not check_brackets(s$) then print "not "; print "ok" end function check_brackets(s$)
level = 0
for i = 1 to length(s$) c$ = mid(s$, i, 1) begin case case c$ = "["
level = level + 1
case c$= "]" level = level - 1 if level < 0 then exit for end case next i return level = 0 end function ### Chipmunk Basic The MSX BASIC solution works without any changes. ### Commodore BASIC Based on ZX Spectrum BASIC implementation 10 PRINT CHR$(147): REM CLEAR SCREEN
20 FOR N=1 TO 7
30   READ S$40 IF S$="" THEN PRINT"(EMPTY)";: GOTO 60
50   PRINT S$; 60 PRINT TAB(20); 70 GOSUB 1000 80 NEXT N 90 END 100 REM ******************************** 1000 S = 0 1010 FOR K=1 TO LEN(S$)
1020   C$= MID$(S$,K,1) 1030 IF C$="[" THEN S = S+1
1040   IF C$="]" THEN S = S-1 1050 IF S<0 THEN PRINT "NOT OK": RETURN 1060 NEXT K 1070 IF S=0 THEN PRINT "OK": RETURN 1090 PRINT "NOT OK" 1100 RETURN 2000 DATA , [], ][, [][], ][][, [[][]], []][[]  ### GW-BASIC Works with: PC-BASIC version any Works with: BASICA The MSX BASIC solution works without any changes. ### MSX Basic Based on Commodore BASIC implementation Works with: MSX BASIC version any Works with: Applesoft BASIC Works with: BASICA Works with: Chipmunk Basic Works with: GW-BASIC Works with: PC-BASIC version any Works with: QBasic 100 CLS : rem 10 HOME for Applesoft BASIC 110 FOR N = 1 TO 7 120 READ S$
130   IF S$= "" THEN PRINT"(EMPTY)";: GOTO 150 140 PRINT S$;
150   PRINT TAB(9);
160   GOSUB 190
170 NEXT N
180 END
190 S = 0
200 FOR K = 1 TO LEN(S$) 210 C$ = MID$(S$,K,1)
220   IF C$= "[" THEN S = S+1 230 IF C$ = "]" THEN S = S-1
240   IF S < 0 THEN PRINT "NOT OK": RETURN
250 NEXT K
260 IF S = 0 THEN PRINT "  OK": RETURN
270 PRINT "NOT OK"
280 RETURN
290 DATA "", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"

Output:
(EMPTY)    OK
[]         OK
][       NOT OK
[][]       OK
][][     NOT OK
[[][]]     OK
[]][[]   NOT OK

### True BASIC

Translation of: Run BASIC
DIM brk$(10) LET brk$(1)  = "[[[][]]]"
LET brk$(2) = "[[[]][[[][[][]]]]]" LET brk$(3)  = "][][]][["
LET brk$(4) = "[][][]" LET brk$(5)  = "[][]][]][[]]][[["
LET brk$(6) = "]][[[[]]]][]]][[[[" LET brk$(7)  = "[[][[[]]][]]"
LET brk$(8) = "[]][][][[[]]" LET brk$(9)  = "][]][["
LET brk$(10) = "[]][][][[]" FOR i = 1 TO 7 LET b$ = brk$(i) DO WHILE POS(b$,"[]") <> 0
LET x = POS(b$,"[]") IF x > 0 THEN LET b$ = (b$)[1:x-1] & (b$)[x+2:maxnum]
LOOP
IF TRIM$(b$) = "" THEN
PRINT "    OK ";
ELSE
PRINT "Not OK ";
END IF
PRINT brk$(i) NEXT i END  ### uBasic/4tH @(0) := "[]][][][[]" @(1) := "[[[][]]]" @(2) := "[[[]][[[][[][]]]]]" @(3) := "][][]][[" @(4) := "[][][]" @(5) := "[][]][]][[]]][[[" @(6) := "]][[[[]]]][]]][[[[" @(7) := "[[][[[]]][]]" @(8) := "[]][][][[[]]" @(9) := "][]][[" For x = 0 To 9 Print Using "(_#)";x,Show (@(x));Tab (30); Do While (Set (a, Find(@(x), "[]")) < 0) = 0 @(x) = Join (Clip (@(x), Len (@(x)) - a), Chop (@(x), a + 2)) Loop Print "is";Show (Iif (Len (@(x))," not "," "));"balanced" Next  Output: ( 0) []][][][[] is not balanced ( 1) [[[][]]] is balanced ( 2) [[[]][[[][[][]]]]] is balanced ( 3) ][][]][[ is not balanced ( 4) [][][] is balanced ( 5) [][]][]][[]]][[[ is not balanced ( 6) ]][[[[]]]][]]][[[[ is not balanced ( 7) [[][[[]]][]] is balanced ( 8) []][][][[[]] is not balanced ( 9) ][]][[ is not balanced 0 OK, 0:472  ## Batch File Uses the rewrite rule "[]" -> null to check if brackets are balanced. :: Balanced Brackets Task from Rosetta Code :: Batch File Implementation @echo off setlocal enabledelayedexpansion set "num_pairs=10" set "num_strings=10" :: the main thing for /l %%s in (1, 1, %num_strings%) do ( call :generate call :check ) echo( pause exit /b 0 :: generate strings of brackets :generate set "string=" rem put %num_pairs% number of "[" in string for /l %%c in (1, 1, %num_pairs%) do set "string=!string![" rem put %num_pairs% number of "]" in random spots of string set "ctr=%num_pairs%" for /l %%c in (1, 1, %num_pairs%) do ( set /a "rnd=!random! %% (!ctr! + 1)" for %%x in (!rnd!) do ( set "left=!string:~0,%%x!" set "right=!string:~%%x!" ) set "string=!left!]!right!" set /a "ctr+=1" ) goto :EOF :: check for balance :check set "new=%string%" :check_loop if "%new%" equ "" ( echo( echo(%string% is Balanced. goto :EOF ) else if "%old%" equ "%new%" ( %== unchangeable already? ==% echo( echo(%string% is NOT Balanced. goto :EOF ) rem apply rewrite rule "[]" -> null set "old=%new%" set "new=%old:[]=%" goto check_loop  Output: [][][[[[]]][]]]][[][ is NOT Balanced. ][[]][][][[]]][[[[]] is NOT Balanced. [[[][]][][]][[][][]] is Balanced. ][[[[[]]][][][][][]] is NOT Balanced. ]][][[][]]]][]][[[[[ is NOT Balanced. [[[][[][][[]]]][][]] is Balanced. ][]]][[]][[][[][[]][ is NOT Balanced. [[[][[][]][[[]]][]]] is Balanced. ]][]]][[[][]][[][[[] is NOT Balanced. ][[]][][[]][][]][[][ is NOT Balanced. Press any key to continue . . . ## BBC BASIC FOR x%=1 TO 10 test$=FNgenerate(RND(10))
PRINT "Bracket string ";test$;" is ";FNvalid(test$)
NEXT x%
END
:
DEFFNgenerate(n%)
LOCAL l%,r%,t%,output$WHILE l%<n% AND r%<n% CASE RND(2) OF WHEN 1: l%+=1 output$+="["
WHEN 2:
r%+=1
output$+="]" ENDCASE ENDWHILE IF l%=n% THEN output$+=STRING$(n%-r%,"]") ELSE output$+=STRING$(n%-l%,"[") =output$
:
DEFFNvalid(q$) LOCAL x%,count% IF LEN(q$)=0 THEN ="OK."
FOR x%=1 TO LEN(q$) IF MID$(q$,x%,1)="[" THEN count%+=1 ELSE count%-=1 IF count%<0 THEN ="not OK." NEXT x% ="OK."  Bracket string [[[][]]] is OK. Bracket string [[[]][[[][[][]]]]] is OK. Bracket string ][][]][[ is not OK. Bracket string [][][] is OK. Bracket string [][]][]][[]]][[[ is not OK. Bracket string ]][[[[]]]][]]][[[[ is not OK. Bracket string [[][[[]]][]] is OK. Bracket string []][][][[[]] is not OK. Bracket string ][]][[ is not OK. Bracket string []][][][[] is not OK. ## Befunge Works with: befungee This code implements the second part of the task: it reads from standard input an arbitrary string of opening and closing brackets, and checks whether it's balanced or not. v > "KO TON" ,,,,,, v > ~ : 25*- #v_$ |                   > 25*, @
> "KO" ,,           ^
> : 1991+*+- #v_ v
> \ : 1991+*+- #v_v
\ $^ < <$<


## BQN

Balanced brackets are a monoid with the following presentation:

⟨l, r | l·r = e⟩

This allows for a particular simple implementation:

Gen ← (•rand.Deal⊏⥊⟜"[]") 2⊸×
Bal ← {
Mul ← {a‿b𝕊x‿y: ⟨a+0⌈x-b, y+0⌈b-x⟩}
0‿0 ≡ 0‿0("]["⊸=⊸Mul)´𝕩
}

Output:
   (⊢≍Bal¨) Gen¨5⥊3
┌─
╵ "]][][[" "[][][]" "][][[]" "[[][]]" "][[][]"
0        1        0        1        0
┘


## Bracmat

Bracmat has no 'random' function, so the shuffle is a bit improvised. A variable someNumber is initialised with a big number is repeatedly divided by the number of '['s in the test string until zero. The remainders are used as index to partition and swap the first half of the test string. Then the second half and first half are also swapped. The test whether the test string is balanced is simple, but not very efficient.

( (bal=|"[" !bal "]" !bal)
& ( generate
=   a j m n z N S someNumber
.   !arg:<1&
& (!arg:?n)+1:?N
& :?S
&   whl
' (!n+-1:~<0:?n&"[" "]" !S:?S)
&   whl
& mod$(!someNumber.!N):?j & div$(!someNumber.!N):?someNumber
& !S:?a [!j ?m [!N ?z
& !z !m !a:?S
)
& !S
)
& 0:?L
&   whl
' ( generate$!L:?S & put$(str$(!S ":")) & out$ (!S:!bal&Balanced|"Not balanced")
& !L+1:<11:?L
)
);

Output:

:Balanced
][:Not balanced
[][]:Balanced
[][[]]:Balanced
[[[]]]][:Not balanced
]]]][][[[[:Not balanced
[[][[[]]][]]:Balanced
[][]][]]]][[[[:Not balanced
[][]][[[]]][][][:Not balanced
[][[[[]][]]][[[]]]:Balanced
[][[][]][]]][][[[]][:Not balanced

## Brat

string.prototype.balanced? = {
brackets = []
balanced = true

my.dice.each_while { c |
true? c == "["
{ brackets << c }
{ true? c == "]"
{ last = brackets.pop
false? last == "["
{ balanced = false }
}
}

balanced
}

true? brackets.empty?
{ balanced }
{ false }
}

generate_brackets = { n | (n.of("[") + n.of("]")).shuffle.join }

1.to 10 { n |
test = generate_brackets n

true? test.balanced?
{ p "#{test} is balanced" }
{ p "#{test} is not balanced" }
}

Output:

[] is balanced
][][ is not balanced
[[]][] is balanced
[[[]][]] is balanced
[[[[]]]]][ is not balanced
][[][]][[[]] is not balanced
]][[][][[]][][ is not balanced
[[[][[]]][][][]] is balanced
][]][]]]][][[[][[[ is not balanced
][[[[][][][[][][]]]] is not balanced

## C

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int isBal(const char*s,int l){
signed c=0;
while(l--)
if(s[l]==']') ++c;
else if(s[l]=='[') if(--c<0) break;
return !c;
}

void shuffle(char*s,int h){
int x,t,i=h;
while(i--){
t=s[x=rand()%h];
s[x]=s[i];
s[i]=t;
}
}

void genSeq(char*s,int n){
if(n){
memset(s,'[',n);
memset(s+n,']',n);
shuffle(s,n*2);
}
s[n*2]=0;
}

void doSeq(int n){
char s[64];
const char *o="False";
genSeq(s,n);
if(isBal(s,n*2)) o="True";
printf("'%s': %s\n",s,o);
}

int main(){
int n=0;
while(n<9) doSeq(n++);
return 0;
}


result:

'': True
'[]': True
']][[': False
'[][][]': True
'[]][[]][': False
'[]][[[[]]]': False
']]]][[[]][[[': False
']]]]]][][[[[[[': False
'[][]][[][[[]]][]': False


## C#

using System;
using System.Linq;

class Program
{
static bool IsBalanced(string text, char open = '[', char close = ']')
{
var level = 0;
foreach (var character in text)
{
if (character == close)
{
if (level == 0)
{
return false;
}
level--;
}
if (character == open)
{
level++;
}
}
return level == 0;
}

static string RandomBrackets(int count, char open = '[', char close = ']')
{
var random = new Random();
return string.Join(string.Empty,
(new string(open, count) + new string(close, count)).OrderBy(c => random.Next()));
}

static void Main()
{
for (var count = 0; count < 9; count++)
{
var text = RandomBrackets(count);
Console.WriteLine("\"{0}\" is {1}balanced.", text, IsBalanced(text) ? string.Empty : "not ");
}
}
}


Sample output:

"" is balanced.
"[]" is balanced.
"[]][" is not balanced.
"[][][]" is balanced.
"[[[]][]]" is balanced.
"[][[][[]]]" is balanced.
"[]][][][[][]" is not balanced.
"[]]][][]][[][[" is not balanced.
"[]]][]]][[][[][[" is not balanced.
                       // simple solution
if (input.Length % 2 != 0)
{
Console.WriteLine("Not Okay");
return;
}
for (int i = 0; i < input.Length; i++)
{
if (i < input.Length - 1)
{
if (input[i] == '[' && input[i + 1] == ']')
{
input = input.Remove(i, 2);
i = -1;
}
}

}
if (input.Length == 0)
Console.WriteLine("Okay");
else
Console.WriteLine("Not Okay");


## C++

#include <algorithm>
#include <iostream>
#include <string>

std::string generate(int n, char left = '[', char right = ']')
{
std::string str(std::string(n, left) + std::string(n, right));
std::random_shuffle(str.begin(), str.end());
return str;
}

bool balanced(const std::string &str, char left = '[', char right = ']')
{
int count = 0;
for (std::string::const_iterator it = str.begin(); it != str.end(); ++it)
{
if (*it == left)
count++;
else if (*it == right)
if (--count < 0) return false;
}
return count == 0;
}

int main()
{
srand(time(NULL)); // seed rng
for (int i = 0; i < 9; ++i)
{
std::string s(generate(i));
std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n";
}
}


Output:

 ok:
ok: []
ok: [][]
ok: [[[]][]]
ok: [[[]][[]][]]


## Ceylon

import com.vasileff.ceylon.random.api {
platformRandom,
Random
}
"""Run the example code for Rosetta Code ["Balanced brackets" task] (http://rosettacode.org/wiki/Balanced_brackets)."""
shared void run() {
value rnd = platformRandom();
for (len in (0..10)) {
value c = generate(rnd, len);
print("c.padTrailing(20) - if (balanced(c)) then "OK" else "NOT OK" ");
}
}

String generate(Random rnd, Integer count)
=> if (count == 0) then ""
else let(length = 2*count,
brackets = zipEntries(rnd.integers(length).take(length),
"[]".repeat(count))
.sort((a,b) => a.key<=>b.key)
.map(Entry.item))
String(brackets);

Boolean balanced(String input)
=> let (value ints = { for (c in input) if (c == '[') then 1 else -1 })
ints.filter((i) => i != 0)
.scan(0)(plus<Integer>)
.every((i) => i >= 0);


Output:

                     - OK
[]                   - OK
][[]                 - NOT OK
][[]][               - NOT OK
[]]][[][             - NOT OK
[[[][][]]]           - OK
[[][]][[]][]         - OK
[[][[[]]][]][]       - OK
]][[][][[][]][[]     - NOT OK
[[]]]]]]][[[[][][[   - NOT OK
[[]][[]][[]]]][[[]][ - NOT OK

## Clojure

(defn gen-brackets [n]
(->> (concat (repeat n $) (repeat n$))
shuffle
(apply str ,)))

(defn balanced? [s]
(loop [[first & coll] (seq s)
stack '()]
(if first
(if (= first $) (recur coll (conj stack \[)) (when (= (peek stack) \[) (recur coll (pop stack)))) (zero? (count stack)))))  There are other ways to express the balanced? function. • We can use reduce to consume the sequence: (defn balanced? [s] (empty? (reduce (fn [stack first] (case first \[ (conj stack \[)$ (if (seq stack)
(pop stack)
(reduced [:UNDERFLOW]))))
'()
s)))

• Only [s are put on the stack. We can just count the unmatched ones.
(defn balanced? [s]
(let [opens-closes (->> s
(map {$1,$ -1})
(reductions + 0))]
(and (not-any? neg? opens-closes) (zero? (last opens-closes)))))


Output:

user> (->> (range 10)
(map gen-brackets ,)
(map (juxt identity balanced?) ,)
vec)
[["" true]
["[]" true]
["[[]]" true]
["[][[]]" true]
["[]][][][" nil]
["[[[[[]]]]]" true]
["]][[][][[[]]" nil]
["[]]]][[[[]][][" nil]
["][][[]]][[][][][" nil]
["][][]]][]][[[][[[]" nil]

## CLU

% This program needs the random number generator from
% "misc.lib" that comes with PCLU.

shuffle = proc [T: type] (a: array[t])
aT = array[t]
for i: int in int$from_to_by(aT$size(a)-1,0,-1) do
x: int := aT$low(a) + i y: int := aT$low(a) + random$next(i+1) temp: T := a[x] a[x] := a[y] a[y] := temp end end shuffle brackets = proc (n: int) returns (string) br: array[char] := array[char]$[]
for i: int in int$from_to(1,2*n) do if i<=n then array[char]$addh(br, '[')
else array[char]$addh(br, ']') end end shuffle[char](br) return(string$ac2s(br))
end brackets

balanced = proc (br: string) returns (bool)
depth: int := 0
for c: char in string$chars(br) do if c='[' then depth := depth + 1 elseif c=']' then depth := depth - 1 end if depth<0 then return(false) end end return(depth = 0) end balanced start_up = proc () po: stream := stream$primary_output()
d: date := now()
random$seed(d.second + 60*(d.minute + 60*d.hour)) for size: int in int$from_to(0, 10) do
b: string := brackets(size)
stream$puts(po, "\"" || b || "\": ") if balanced(b) then stream$putl(po, "balanced")
else
stream$putl(po, "not balanced") end end end start_up Output: "": balanced "[]": balanced "[][]": balanced "[[]][]": balanced "[[]][[]]": balanced "][[]][][[]": not balanced "[][][]][]][[": not balanced "][]][]]][][[[[": not balanced "[][[]][][][[[]]]": balanced "][[][][]][[]][][[]": not balanced "]]]][[[[]][][][[][[]": not balanced ## COBOL Works with: OpenCOBOL  IDENTIFICATION DIVISION. PROGRAM-ID. test-balanced-brackets. DATA DIVISION. WORKING-STORAGE SECTION. 01 True-Val CONSTANT 0. 01 False-Val CONSTANT 1. LOCAL-STORAGE SECTION. 01 current-time PIC 9(10). 01 bracket-type PIC 9. 88 add-open-bracket VALUE 1. 01 bracket-string-area. 03 bracket-string PIC X(10) OCCURS 10 TIMES. 01 i PIC 999. 01 j PIC 999. PROCEDURE DIVISION. *> Seed RANDOM(). MOVE FUNCTION CURRENT-DATE (7:10) TO current-time MOVE FUNCTION RANDOM(current-time) TO current-time *> Generate random strings of brackets. PERFORM VARYING i FROM 1 BY 1 UNTIL 10 < i PERFORM VARYING j FROM 1 BY 1 UNTIL i < j COMPUTE bracket-type = FUNCTION REM(FUNCTION RANDOM * 1000, 2) IF add-open-bracket MOVE "[" TO bracket-string (i) (j:1) ELSE MOVE "]" TO bracket-string (i) (j:1) END-IF END-PERFORM END-PERFORM *> Display if the strings are balanced or not. PERFORM VARYING i FROM 1 BY 1 UNTIL 10 < i CALL "check-if-balanced" USING bracket-string (i) IF RETURN-CODE = True-Val DISPLAY FUNCTION TRIM(bracket-string (i)) " is balanced." ELSE DISPLAY FUNCTION TRIM(bracket-string (i)) " is not balanced." END-IF END-PERFORM GOBACK . END PROGRAM test-balanced-brackets. IDENTIFICATION DIVISION. PROGRAM-ID. check-if-balanced. DATA DIVISION. WORKING-STORAGE SECTION. 01 True-Val CONSTANT 0. 01 False-Val CONSTANT 1. LOCAL-STORAGE SECTION. 01 nesting-level PIC S999. 01 i PIC 999. LINKAGE SECTION. 01 bracket-string PIC X(100). PROCEDURE DIVISION USING bracket-string. PERFORM VARYING i FROM 1 BY 1 UNTIL (100 < i) OR (bracket-string (i:1) = SPACE) OR (nesting-level < 0) IF bracket-string (i:1) = "[" ADD 1 TO nesting-level ELSE SUBTRACT 1 FROM nesting-level IF nesting-level < 0 MOVE False-Val TO RETURN-CODE GOBACK END-IF END-IF END-PERFORM IF nesting-level = 0 MOVE True-Val TO RETURN-CODE ELSE MOVE False-Val TO RETURN-CODE END-IF GOBACK . END PROGRAM check-if-balanced.  ## CoffeeScript isBalanced = (brackets) -> openCount = 0 for bracket in brackets openCount += if bracket is '[' then 1 else -1 return false if openCount < 0 openCount is 0 bracketsCombinations = (n) -> for i in [0...Math.pow 2, n] str = i.toString 2 str = '0' + str while str.length < n str.replace(/0/g, '[').replace(/1/g, ']') for brackets in bracketsCombinations 4 console.log brackets, isBalanced brackets  output > coffee balanced.coffee [[[[ false [[[] false [[][ false [[]] true [][[ false [][] true []][ false []]] false ][[[ false ][[] false ][][ false ][]] false ]][[ false ]][] false ]]][ false ]]]] false  ## Common Lisp (defun string-of-brackets (n) (let* ((len (* 2 n)) (res (make-string len)) (opening (/ len 2)) (closing (/ len 2))) (dotimes (i len res) (setf (aref res i) (cond ((zerop opening) #\]) ((zerop closing) #$) (t (if (= (random 2) 0) (progn (decf opening) #\[) (progn (decf closing) #$)))))))) (defun balancedp (string) (zerop (reduce (lambda (nesting bracket) (ecase bracket (#\] (if (= nesting 0) (return-from balancedp nil) (1- nesting))) (#$(1+ nesting)))) string :initial-value 0))) (defun show-balanced-brackets () (dotimes (i 10) (let ((s (string-of-brackets i))) (format t "~3A: ~A~%" (balancedp s) s))))  Output: CL-USER> (show-balanced-brackets) T : NIL: ][ T : [[]] NIL: []]][[ T : [][][][] NIL: []][]][[[] NIL: []]]]][][[[[ NIL: ][]]]]][[[[][[ T : [[[[[[][[]]]]]]] NIL: ]][[[[][]][[[[]]]]  ## Component Pascal BlackBox Component Builder MODULE Brackets; IMPORT StdLog, Args, Stacks (* See Task Stacks *); TYPE Character = POINTER TO RECORD (Stacks.Object) c: CHAR END; PROCEDURE NewCharacter(c: CHAR): Character; VAR n: Character; BEGIN NEW(n);n.c:= c;RETURN n END NewCharacter; PROCEDURE (c: Character) Show*; BEGIN StdLog.String("Character(");StdLog.Char(c.c);StdLog.String(");");StdLog.Ln END Show; PROCEDURE CheckBalance(str: ARRAY OF CHAR): BOOLEAN; VAR s: Stacks.Stack; n,x: ANYPTR; i: INTEGER; c : CHAR; BEGIN i := 0; s := Stacks.NewStack(); WHILE (i < LEN(str)) & (~Args.IsBlank(str[i])) & (str[i] # 0X) DO IF s.Empty() THEN s.Push(NewCharacter(str[i])); ELSE n := s.top.data; WITH n : Character DO IF (str[i] = ']')& (n.c = '[') THEN x := s.Pop(); ELSE s.Push(NewCharacter(str[i])) END; ELSE RETURN FALSE; END; END; INC(i) END; RETURN s.Empty(); END CheckBalance; PROCEDURE Do*; VAR p : Args.Params; i: INTEGER; BEGIN Args.Get(p); (* Get Params *) FOR i := 0 TO p.argc - 1 DO StdLog.String(p.args[i] + ":>");StdLog.Bool(CheckBalance(p.args[i]));StdLog.Ln END END Do; END Brackets.  Execute: ^Q Brackets.Do [] [][] [[][]] ][ ][][ []][[]~ Output: [] :> TRUE [][] :> TRUE [[][]] :> TRUE ][ :> FALSE ][][ :> FALSE []][[]:> FALSE  ## Crystal def generate(n : Int) (['[',']'] * n).shuffle.join # Implicit return end def is_balanced(str : String) count = 0 str.each_char do |ch| case ch when '[' count += 1 when ']' count -= 1 if count < 0 return false end else return false end end count == 0 end 10.times do |i| str = generate(i) puts "#{str}: #{is_balanced(str)}" end  Output: : true []: true ][][: false ][[]][: false []]][][[: false ][[]][[[]]: false []]][[[]][[]: false [[][[[][]]]]][: false [[[]]]][][][][[]: false [[][][]][][[]][][]: true ## D ### Standard Version D standard library has a function for this. import std.stdio, std.algorithm, std.random, std.range; void main() { foreach (immutable i; 1 .. 9) { immutable s = iota(i * 2).map!(_ => "[]"[uniform(0, 2)]).array; writeln(s.balancedParens('[', ']') ? " OK: " : "bad: ", s); } }  Output:  OK: [] bad: []][ OK: [][][] bad: [][]]][[ OK: [[[]][]][] bad: ][][[[][][]] bad: [[]][[]]]]][[[ bad: ][]]][[[[][][][] ### Imperative Version Translation of: Raku import std.stdio, std.random, std.range, std.algorithm; bool isBalanced(in string txt) pure nothrow { auto count = 0; foreach (immutable c; txt) { if (c == ']') { count--; if (count < 0) return false; } else if (c == '[') count++; } return count == 0; } void main() { foreach (immutable i; 1 .. 9) { immutable s = iota(i * 2).map!(_ => "[]"[uniform(0, 2)]).array; writeln(s.isBalanced ? " OK " : "Bad ", s); } }  The output is similar. ### Functional Style Translation of: Haskell import std.stdio, std.random, std.range, std.algorithm; bool isBalanced(in string s, in char[2] pars="[]") pure nothrow @safe @nogc { bool bal(in string t, in int nb = 0) pure nothrow @safe @nogc { if (!nb && t.empty) return true; if (t.empty || nb < 0) return false; if (t[0] == pars[0]) return bal(t.dropOne, nb + 1); if (t[0] == pars[1]) return bal(t.dropOne, nb - 1); return bal(t.dropOne, nb); // Ignore char. } return bal(s); } void main() { foreach (immutable i; 1 .. 9) { immutable s = iota(i * 2).map!(_ => "[]"[uniform(0, )]).array; writeln(s.isBalanced ? " OK " : "Bad ", s); } }  ## Delphi procedure Balanced_Brackets; var BracketsStr : string; TmpStr : string; I,J : integer; begin Randomize; for I := 1 to 9 do begin { Create a random string of 2*N chars with N*"[" and N*"]" } TmpStr := ''; for J := 1 to I do TmpStr := '['+TmpStr+']'; BracketsStr := ''; while TmpStr > '' do begin J := Random(Length(TmpStr))+1; BracketsStr := BracketsStr+TmpStr[J]; Delete(TmpStr,J,1); end; TmpStr := BracketsStr; { Test for balanced brackets } while Pos('[]',TmpStr) > 0 do Delete(TmpStr,Pos('[]',TmpStr),2); if TmpStr = '' then writeln(BracketsStr+': OK') else writeln(BracketsStr+': not OK'); end; end;  []: OK [[]]: OK [][][]: OK [[[]][]]: OK ]]]][[[[[]: not OK ][[][][[[]]]: not OK [][[]]][[][[]]: not OK [[[[[]][]][[]]]]: OK []]][][[[[[]][]][]: not OK  ## Déjà Vu matching?: swap 0 for c in chars: if = c "]": ++ elseif = c "[": if not dup: drop return false -- not !. matching? "" !. matching? "[]" !. matching? "[][]" !. matching? "[[][]]" !. matching? "][" !. matching? "][][" !. matching? "[]][[]" Output: true true true true false false false ## EasyLang func balanced code . for i to len code h = substr code i 1 if h = "[" br += 1 elif h = "]" br -= 1 . if br < 0 return 0 . . return if br = 0 . repeat inp = input until inp = "eof" print inp & "\t" & balanced inp . # input_data [] [][] [[][]] ][ ][][ []][[] eof ## EchoLisp (define (balance str) (for/fold (closed 0) ((par str)) #:break (< closed 0 ) => closed (+ closed (cond ((string=? par "[") 1) ((string=? par "]") -1) (else 0))))) (define (task N) (define str (list->string (append (make-list N "[") (make-list N "]")))) (for ((i 10)) (set! str (list->string (shuffle (string->list str)))) (writeln (if (zero? (balance str)) '👍 '❌ ) str))) (task 4) ❌ "[]]][[][" ❌ "]][][[[]" ❌ "][[[]]][" 👍 "[][[[]]]" ❌ "]][[][][" ❌ "][][[[]]" 👍 "[][][[]]" ❌ "]][[][[]" ❌ "[[]]][[]" ❌ "[[][]]]["  ## Ecstasy module BalancedBrackets { Boolean balanced(String text) { Int depth = 0; for (Char ch : text) { switch (ch, depth) { case ('[', _): ++depth; break; case (']', 0): return False; case (']', _): --depth; break; } } return depth==0; } @Inject Console console; void run() { String[] tests = [ "[]", "[][]", "[]][[]", "[[[]][]]", "][[[[]][]]", "[[[]][[]][]]", "]][[]][[[[][]]", "[[]]]][]][[][[[]", ]; Int longest = tests.map(s -> s.size).reduce(0, (max, len) -> max.maxOf(len)); for (String test : tests) { console.print("{test}{' ' * (longest-test.size)} {balanced(test) ? "OK" : "NOT OK"}"); } } }  Output: [] OK [][] OK []][[] NOT OK [[[]][]] OK ][[[[]][]] NOT OK [[[]][[]][]] OK ]][[]][[[[][]] NOT OK [[]]]][]][[][[[] NOT OK  ## ed Balanced brackets can be recursively defined as: • A pair of brackets [] is balanced. • An expression wrapped in matching brackets and containing balanced brackets expressions is balanced. Based on that, the logic might be: if we remove the innermost balanced brackets, then the ones around them turn into simple matching brackets. Repeat recursively/iteratively, and a proper balanced set of brackets reduces to empty string. Unbalanced brackets don't, because they stop matching the [] part at some moment. # by Artyom Bologov H # Remove all the non-bracket chars g/.*/s/[^][]//gp # Repeatedly remove all the simple matching brackets. # Add more lines to handle deeper nested expressions. g/\[$/s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g//s///g g/./s/.*/Not balanced!/ g/^$/s/.*/Balanced!/
,p
Q

Output:

Notice that the script doesn't generate bracket expressions. That's because ed has no built-in Random Number Generator and any reliable ways to generate chaos. Still, it's good at recognizing patterns in input. That's why the example input is used here to test the algo.

$ed -s balanced-brackets.input < balanced-brackets.ed Newline appended [] [][] [[][]] ][ ][][ []][[] Balanced! Balanced! Balanced! Balanced! Not balanced! Not balanced! Not balanced! ## Elena ELENA 6.x : // Generate a string with N opening brackets ("[") and N closing brackets ("]"), in some arbitrary order. // Determine whether the generated string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), // none of which mis-nest. import system'routines; import extensions; import extensions'text; randomBrackets(len) { if (0 == len) { ^emptyString } else { var brackets := Array.allocate(len).populate::(i =>$91)
+
Array.allocate(len).populate::(i => $93); brackets := brackets.randomize(len * 2); ^ brackets.summarize(new StringWriter()).toString() } } extension op { get isBalanced() { var counter := new Integer(0); self.seekEach::(ch => counter.append((ch==$91).iif(1,-1)) < 0);

^ (0 == counter)
}
}

public program()
{
for(int len := 0; len < 9; len += 1)
{
var str := randomBrackets(len);

console.printLine("""",str,"""",str.isBalanced ? " is balanced" : " is not balanced")
};

}
Output:
"" is balanced
"[]" is balanced
"][[]" is not balanced
"[[[]]]" is balanced
"][[[]]][" is not balanced
"[]]]][[[][" is not balanced
"[[]][][[]]][" is not balanced
"[][]]]]][[[[][" is not balanced
"][]]][[[[][[][]]" is not balanced
"][]][][[]]][[[]][[" is not balanced


## Elixir

Translation of: Erlang
Works with: Elixir version 1.1
defmodule Balanced_brackets do
Enum.each(0..5, fn n ->
brackets = generate(n)
IO.puts "#{brackets} is #{result}"
end)
end

defp generate( 0 ), do: []
defp generate( n ) do
for _ <- 1..2*n, do: Enum.random ["[", "]"]
end

def is_balanced( brackets ), do: is_balanced_loop( brackets, 0 )

defp is_balanced_loop( _, n ) when n < 0, do: false
defp is_balanced_loop( [], 0 ), do: true
defp is_balanced_loop( [], _n ), do: false
defp is_balanced_loop( ["[" | t], n ), do: is_balanced_loop( t, n + 1 )
defp is_balanced_loop( ["]" | t], n ), do: is_balanced_loop( t, n - 1 )

defp task_balanced( true ), do: "OK"
defp task_balanced( false ), do: "NOT OK"
end


Output:
 is OK
[[ is NOT OK
[][] is OK
]][]][ is NOT OK
[[][][]] is OK
[][[][[]]] is OK


## Erlang

-module( balanced_brackets ).

generate( N ) ->
[generate_bracket(random:uniform()) || _X <- lists:seq(1, 2*N)].

is_balanced( String ) -> is_balanced_loop( String, 0 ).

lists:foreach( fun (N) ->
String = generate( N ),
Result = is_balanced( String ),
io:fwrite( "~s is ~s~n", [String, task_balanced(Result)] )
end,
lists:seq(0, 5) ).

is_balanced_loop( _String, N ) when N < 0 -> false;
is_balanced_loop( [], 0 ) -> true;
is_balanced_loop( [], _N ) -> false;
is_balanced_loop( [$[ | T], N ) -> is_balanced_loop( T, N + 1 ); is_balanced_loop( [$] | T], N ) -> is_balanced_loop( T, N - 1 ).

generate_bracket( N ) when N =< 0.5 -> $[; generate_bracket( N ) when N > 0.5 ->$].

task_balanced( false ) -> "NOT OK".

Output:
47> balanced_brackets:task().
is OK
[[ is NOT OK
[][] is OK
[[[[][ is NOT OK
[]]]]][[ is NOT OK
[[[][[[[]] is NOT OK


## Euphoria

function check_brackets(sequence s)
integer level
level = 0
for i = 1 to length(s) do
if s[i] = '[' then
level += 1
elsif s[i] = ']' then
level -= 1
if level < 0 then
return 0
end if
end if
end for
return level = 0
end function

function generate_brackets(integer n)
integer opened,closed,r
sequence s
opened = n
closed = n
s = ""
for i = 1 to n*2 do
r = rand(opened+closed)
if r<=opened then
s &= '['
opened -= 1
else
s &= ']'
closed -= 1
end if
end for
return s
end function

sequence s
for i = 1 to 10 do
s = generate_brackets(3)
puts(1,s)
if check_brackets(s) then
puts(1," OK\n")
else
puts(1," NOT OK\n")
end if
end for

Sample output:

]]][[[ NOT OK
[[[]]] OK
[[]][] OK
[][][] OK
]][[][ NOT OK
[][[]] OK
[[[]]] OK
[[]][] OK
[]]][[ NOT OK
[][[]] OK


## Excel

### LAMBDA

Binding the names bracketReport and testRandomBrackets to the following lambda expressions in the Name Manager of the Excel WorkBook, together with names for their helper functions:

bracketReport
=LAMBDA(bracketPair,
LAMBDA(s,
LET(
depths, SCANLCOLS(
LAMBDA(depth, charDelta,
depth + charDelta
)
)(0)(
codesFromBrackets(bracketPair)(
MID(s,
SEQUENCE(1, LEN(s), 1, 1),
1
)
)
),
overClosePosn, IFNA(MATCH(-1, depths, 0), 0),

IF(0 <> overClosePosn,
"Overclosed at char " & (overClosePosn - 1),
IF(0 <> LASTCOL(depths),
"Underclosed by end",
"OK"
)
)
)
)
)

testRandomBrackets
=LAMBDA(bracketPair,
LAMBDA(n,
LET(
sample, CONCAT(
bracketFromCode(bracketPair)(
RANDARRAY(1, n, -1, 1, TRUE)
)
),

APPENDCOLS(sample)(
bracketReport(bracketPair)(sample)
)
)
)
)

bracketFromCode
=LAMBDA(bracketPairString,
LAMBDA(c,
IF(0 <> c,
IF(0 < c,
MID(bracketPairString, 1, 1),
MID(bracketPairString, 2, 1)
),
"x"
)
)
)

codesFromBrackets
=LAMBDA(bracketPair,
LAMBDA(s,
LAMBDA(c,
LET(
posn, IFERROR(
FIND(c, bracketPair),
0
),

rem, "0 for non-bracket chars, (1, -1) for (open, close)",
IF(0 <> posn,
IF(1 < posn, -1, 1),
0
)
)
)(
MID(s,
SEQUENCE(1, LEN(s), 1, 1),
1
)
)
)
)


and also assuming the following generic bindings in the Name Manager for the WorkBook:

APPENDCOLS
=LAMBDA(xs,
LAMBDA(ys,
LET(
nx, COLUMNS(xs),
colIndexes, SEQUENCE(1, nx + COLUMNS(ys)),
rowIndexes, SEQUENCE(MAX(ROWS(xs), ROWS(ys))),

IFERROR(
IF(nx < colIndexes,
INDEX(ys, rowIndexes, colIndexes - nx),
INDEX(xs, rowIndexes, colIndexes)
),
NA()
)
)
)
)

CHARSROW
=LAMBDA(s,
MID(s,
SEQUENCE(1, LEN(s), 1, 1),
1
)
)

=LAMBDA(xs,
LET(REM, "The first item of each column in xs",

INDEX(xs, 1, SEQUENCE(1, COLUMNS(xs)))
)
)

=LAMBDA(xs,
LET(REM, "The first item of each row in xs",

INDEX(
xs,
SEQUENCE(ROWS(xs)),
SEQUENCE(1, 1)
)
)
)

LASTCOL
=LAMBDA(xs,
INDEX(
xs,
SEQUENCE(ROWS(xs), 1, 1, 1),
COLUMNS(xs)
)
)

SCANLCOLS
=LAMBDA(op,
LAMBDA(a,
LAMBDA(xs,
APPENDCOLS(a)(
LET(

IF(2 > COLUMNS(xs),
b,
SCANLCOLS(op)(b)(
TAILROW(xs)
)
)
)
)
)
)
)

TAILCOL
=LAMBDA(cols,
LET(REM, "The tail of each column in the grid.",

INDEX(
cols,
SEQUENCE(ROWS(cols) - 1, 1, 2, 1),
SEQUENCE(1, COLUMNS(cols))
)
)
)

TAILROW
=LAMBDA(xs,
LET(REM,"The tail of each row in the grid",
n, COLUMNS(xs) - 1,

IF(0 < n,
INDEX(
xs,
SEQUENCE(ROWS(xs), 1, 1, 1),
SEQUENCE(1, n, 2, 1)
),
NA()
)
)
)

Output:

The formula in cell B2 defines the pair of values (random bracket sample, and verdict on balance), which populates the range B2:C2

 =testRandomBrackets("[]")(10) fx A B C 1 Random sample Verdict 2 [[[[x[x]xx Underclosed by end 3 [][]x[]]][ Overclosed at char 8 4 ][x[x]]x]x Overclosed at char 1 5 [x[]x[]]xx OK 6 x]][[xxx[] Overclosed at char 2 7 [xxx[[[xxx Underclosed by end 8 []x[[[xx]x Underclosed by end 9 xxx[][xxx] OK 10 ][x]x]]]][ Overclosed at char 1 11 ]xxxxx[x]] Overclosed at char 1

Or applying the same bracketReport function to non-random samples, with a different bracket type:

 =bracketReport("()")(C2) fx A B C 1 Verdict Sample 2 OK (Non-random) sample string 3 OK (Non-random) (sample) string 4 Overclosed at char 1 )((Non-random) (sample) string) 5 Underclosed by end ((Non-random) ((sample) string) 6 Overclosed at char 24 ((Non-random)) (sample)) string)

## F#

let isBalanced str =
let rec loop count = function
| ']'::_  when count = 0 -> false
| '['::xs                -> loop (count+1) xs
| ']'::xs                -> loop (count-1) xs
| []                     -> count = 0
| _::_                   -> false

str |> Seq.toList |> loop 0

let shuffle arr =
let rnd = new System.Random()
Array.sortBy (fun _ -> rnd.Next()) arr

let generate n =
new string( String.replicate n "[]" |> Array.ofSeq |> shuffle )

for n in 1..10 do
let s = generate n
printfn "\"%s\" is balanced: %b" s (isBalanced s)


Output:

"[]" is balanced: true
"][][" is balanced: false
"][[]][" is balanced: false
"[][[]][]" is balanced: true
"[[]][[]][]" is balanced: true
"[[]][[[]][]]" is balanced: true
"][[[]][[[]][]]" is balanced: false
"][[][][]][[]][[]" is balanced: false
"][[]][][]][[]][[[]" is balanced: false
"][[]]][[][]][[]][[[]" is balanced: false

## Factor

USING: combinators formatting kernel math random sequences strings ;
IN: rosetta-code.balanced-brackets

: balanced? ( str -- ? )
0 swap [
{
{ CHAR: [ [ 1 + t ] }
{ CHAR: ] [ 1 - dup 0 >= ] }
[ drop t ]
} case
] all? swap zero? and ;

: bracket-pairs ( n -- str )
[ "[]" ] replicate "" concat-as ;

: balanced-brackets-main ( -- )
5 bracket-pairs randomize dup balanced? "" "not " ?
"String \"%s\" is %sbalanced.\n" printf ;

MAIN: balanced-brackets-main


The code below implements only the second part of the task: it reads from standard input an arbitrary string of opening and closing brackets, and checks whether it's balanced or not. Unlike the solution above, this one uses local variables.

USING: io formatting locals kernel math sequences unicode.case ;
IN: balanced-brackets

:: balanced ( str -- )
0 :> counter!
1 :> ok!
str
[ dup length 0 > ]
[ 1 cut swap
"[" = [ counter 1 + counter! ] [ counter 1 - counter! ] if
counter 0 < [ 0 ok! ] when
]
while
drop
ok 0 =
[ "NO" ]
[ counter 0 > [ "NO" ] [ "YES" ] if ]
if
print ;

balanced


## Fantom

class Main
{
static Bool matchingBrackets (Str[] brackets)
{
Int opened := 0
Int i := 0
while (i < brackets.size)
{
if (brackets[i] == "[")
opened += 1
else
opened -= 1
if (opened < 0) return false
i += 1
}
return true
}

public static Void main (Str[] args)
{
if (args.size == 1 && Int.fromStr(args[0], 10, false) != null)
{
n := Int.fromStr(args[0])
Str[] brackets := [,]
20.times
{
brackets = [,]
// create a random set of brackets
n.times { brackets.addAll (["[", "]"]) }
n.times { brackets.swap(Int.random(0..<2*n), Int.random(0..<2*n)) }
// report if matching or not
if (matchingBrackets(brackets))
echo (brackets.join(" ") + " Matching")
else
echo (brackets.join(" ") + " not matching")
}
}
}
}

Output (for n=3):

[ ] [ ] [ ] Matching
[ [ [ ] ] ] Matching
] [ [ ] ] [ not matching
[ ] ] ] [ [ not matching
] ] [ ] [ [ not matching
[ ] ] [ [ ] not matching
[ ] ] [ [ ] not matching
[ ] [ ] ] [ not matching
[ [ ] ] [ ] Matching
[ [ [ ] ] ] Matching
[ ] ] [ [ ] not matching
] ] [ [ [ ] not matching
[ ] ] [ [ ] not matching
[ [ ] [ ] ] Matching
[ ] [ ] [ ] Matching
[ ] [ [ ] ] Matching
[ [ [ ] ] ] Matching
[ ] ] [ [ ] not matching
] ] [ ] [ [ not matching
[ ] ] [ [ ] not matching


## Forth

Works with: 4tH version 3.61.1
include lib/choose.4th                 ( n1 -- n2)
include lib/ctos.4th                   ( n -- a 1)

10 constant /[]                       \ maximum number of brackets
/[] string    []                       \ string with brackets
\ create string with brackets
: make[]                               ( --)
0 dup [] place /[] choose 0 ?do 2 choose 2* [char] [ + c>s [] +place loop
;                                      \ empty string, fill with brackets
\ evaluate string
: eval[]                               ( --)
[] count 2dup over chars + >r swap type 0
begin                                \ setup string and count
over r@ <                          \ reached end of string?
while                                \ if not ..
dup 0< 0=                          \ unbalanced ]?
while                                \ if not ..
over c@ [char] \ - negate + swap char+ swap
repeat                               \ evaluate, goto next character
r> drop if ."  NOT" then ."  OK" cr drop
;                                      \ evaluate string and print result

make[] eval[]


Examples:

[][[]] OK
[[[[]][[ NOT OK
][[[]][] NOT OK
]][[[][ NOT OK
[]]]][][[ NOT OK
[]]][[]]] NOT OK
OK
[[[[]]]] OK
[[]] OK
[[[[]]]] OK
[][[]] OK
[] OK

## Fortran

Please see the compilation and program execution result as comments at the top of this source:

! $gfortran -g -O0 -std=f2008 -Wall f.f08 -o f.exe !$ ./f
!  compiles             syntax error
! :
! :                     ][
! :                     ]][[
! :[[[]]]
! :                     ][[][]][
! :                     ][[]]][[[]
! :                     ]]]][]][[[[[
! :                     ]]]][][]][[[[[
! :                     ][[[]]]]][]][[[[
! :                     [[][]]][]]][[[][[]
! :                     ]]][[][[[[[[[[]]]]]]
! :[[][[[][]]][]]
! :[[[][]][][[[]][]][]]

program balanced_brackets
implicit none
integer :: N
character(len=20) :: brackets, fmt
write(6,*)'compiles             syntax error'
call random_seed
do N=0, 10
call generate(N, brackets)
if (balanced(brackets)) then
fmt = '(a,a20)'
else
fmt = '(a,21x,a20)'
end if
write(6,fmt)':',brackets
end do

brackets = '[[][[[][]]][]]'
if (balanced(brackets)) then
fmt = '(a,a20)'
else
fmt = '(a,21x,a20)'
end if
write(6,fmt)':',brackets

N = 10
call generate(N, brackets)
do while (.not. balanced(brackets)) ! show a balanced set
call generate(N, brackets)
end do
fmt = '(a,a20)'
write(6,fmt)':',brackets

contains

logical function balanced(s)
implicit none
character(len=*), intent(in) :: s
integer :: i, a, n
n = len_trim(s)
a = 0
balanced = .true.
do i=1, n
if (s(i:i) == '[') then
a = a+1
else
a = a-1
end if
balanced = balanced .and. (0 <= a)
end do
end function balanced

subroutine generate(N, s)
implicit none
integer, intent(in) :: N
character(len=*), intent(out) :: s
integer :: L, R, i
real, dimension(2*N) :: harvest
character :: c
i = 1
L = 0
R = 0
s = ' '
call random_number(harvest)
do while ((L < N) .and. (R < N))
if (harvest(i) < 0.5) then
L = L+1
s(i:i) = '['
else
R = R+1
s(i:i) = ']'
end if
i = i+1
end do
c = merge('[', ']', L < N)
do while (i <= 2*N)
s(i:i) = c
i = i+1
end do
end subroutine generate
end program balanced_brackets


## FreeBASIC

' FB 1.05.0 Win64

Function isBalanced(s As String) As Boolean
If s = "" Then Return True
Dim countLeft As Integer = 0 '' counts number of left brackets so far unmatched
Dim c As String
For i As Integer = 1 To Len(s)
c = Mid(s, i, 1)
If  c = "[" Then
countLeft += 1
ElseIf countLeft > 0 Then
countLeft -= 1
Else
Return False
End If
Next
Return countLeft = 0
End Function

' checking examples in task description
Dim brackets(1 To 7) As String = {"", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"}
For i As Integer = 1 To 7
Print IIf(brackets(i) <> "", brackets(i), "(empty)"); Tab(10); IIf(isBalanced(brackets(i)), "OK", "NOT OK")
Next

' checking 7 random strings of brackets of length 8 say
Randomize
Dim r As Integer '' 0 will signify "[" and 1 will signify "]"
Dim s As String
For i As Integer = 1 To 7
s = Space(8)
For j As Integer = 1 To 8
r = Int(Rnd * 2)
If r = 0 Then
Mid(s, j) = "["
Else
Mid(s, j) = "]"
End If
Next j
Print s; Tab(10); IIf(isBalanced(s), "OK", "NOT OK")
Next i

Print
Print "Press any key to quit"
Sleep


Sample output (last 7 lines random) :

Output:
(empty)  OK
[]       OK
][       NOT OK
[][]     OK
][][     NOT OK
[[][]]   OK
[]][[]   NOT OK
][]][[[[ NOT OK
[]][][]] NOT OK
][][[[]] NOT OK
[[[[]]]] OK
[][[[[][ NOT OK
][[[]][] NOT OK
[][[[[][ NOT OK


## FutureBasic

Filters out non-bracket characters prior to evaluation.

include "NSLog.incl"

local fn BracketBalance( strWithBracket as CFStringRef ) as CFStringRef
NSInteger   i, bracketTracker = 0
CFStringRef result

CFCharacterSetRef bracketSet      = fn CharacterSetWithCharactersInString( @"[]" )
CFCharacterSetRef bracketsOnlySet = fn CharacterSetInvertedSet( bracketSet )
CFArrayRef         trimmedSArray  = fn StringComponentsSeparatedByCharactersInSet( strWithBracket, bracketsOnlySet )
CFStringRef        trimmedStr     = fn ArrayComponentsJoinedByString( trimmedSArray, @"" )

NSUInteger strLen = len( trimmedStr )

// Empty string, no brackets
if ( strLen == 0  ) then result = @"No brackets" : exit fn
// String with odd number of brackets is unbalanced
if ( strLen mod 2 ) then result = @"Unbalanced"  : exit fn

for i = 0 to strLen - 1
CFStringRef bracket = fn StringWithFormat( @"%C", fn StringCharacterAtIndex( trimmedStr, i ) )
if fn StringisEqual( bracket, @"[" ) then bracketTracker++
if fn StringisEqual( bracket, @"]" ) then bracketTracker--
if bracketTracker < 0 then result = @"Unbalanced" : break
next
if bracketTracker == 0 then result = @"Balanced"
end fn = result

NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @""     ) ), @""     )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"["    ) ), @"["    )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"]"    ) ), @"]"    )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[]"   ) ), @"[]"   )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[]"  ) ), @"[[]"  )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[]]"  ) ), @"[]]"  )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[][]" ) ), @"[][]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"]["   ) ), @"]["   )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"][][" ) ), @"][][" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[]][][][[][]]"       ) ), @"[[]][][][[][]]"         )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"][[]][][][]]][["      ) ), @"][[]][][][]]][["        )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[[abc]][[d]]]]]"     ) ), @"[[[abc]][[def]]]]]"     )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[[abc]]][[[[[d]]]]]" ) ), @"[[[abc]]][[[[[def]]]]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[][abc]]][[[[[d]]]]]" ) ), @"[][abc]]][[[[[def]]]]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"The quick brown fox"  ) ), @"The quick brown fox"    )

HandleEvents
Output:
 No brackets:
Unbalanced: [
Unbalanced: ]
Balanced: []
Unbalanced: [[]
Unbalanced: []]
Balanced: [][]
Unbalanced: ][
Unbalanced: ][][
Balanced: [[]][][][[][]]
Unbalanced: ][[]][][][]]][[
Unbalanced: [[[abc]][[def]]]]]
Balanced: [[[abc]]][[[[[def]]]]]
Unbalanced: [][abc]]][[[[[def]]]]]
No brackets: The quick brown fox


## Gambas

'Altered to prevent lines starting with ']' or ending with '[' being generated as they can't work

siNumberOfBrackets As Short = 20              'Maximum amount of brackets in a line
siNumberOfLines As Short = 20                 'Amount of lines to test

'----

Public Sub Main()
Dim sBrks As String[] = GenerateBrackets()    'Get random array to check
Dim sTemp, sHold, sWork As String             'Working variables
Dim siCount As Short                          'Counter

For Each sTemp In sBrks                       'For each line in the sBrk array (e.g. '[][][][[[[]][]]]')
sWork = sTemp                               'Make sWork = sTemp
Repeat                                      'Repeat
sHold = sWork                             'Make sHold = sWork
sWork = Replace(sWork, "[]", "")          'Remove all brackets that match '[]'
Until sHold = sWork                         'If sHold = sWork then there are no more '[]' matches

If sWork = "" Then                          'So if all the brackets 'Nested' correctly sWork will be empty
Print "    OK ";                        'Print 'OK'
Else                                        'Else they did not all match
Print "NOT OK ";                          'So print 'NOT OK'
Endif

For siCount = 1 To Len(sTemp)               'Loop through the line of brackets
Print Mid(sTemp, siCount, 1) & " ";       'Print each bracket + a space to make it easier to read
Next
Print                                       'Print a new line
Next

End

'----

Public Sub GenerateBrackets() As String[]     'Generates an array of random quantities of '[' and ']'
Dim siQty As New Short[]                      'To store the random number (of brackets) to put in a line
Dim sBrk As New String[]                      'To store the lines of brackets
Dim siNum, siEnd, siLoop As Short             'Various counters
Dim sTemp As String                           'Temp string

Repeat                                        'Repeat
siNum = Rand(0, siNumberOfBrackets)         'Pick a number between 0 and the total number of brackets requested
If Even(siNum) Then siQty.Add(siNum)        'If the number is even then add the number to siQty
Until siQty.Count = siNumberOfLines           'Keep going until we have the number of lines requested

For Each siNum In siQty                       'For each number in siQty..(e.g. 6)
Do
siEnd = Rand(0, 1)                        'Generate a 0 or a 1
If siEnd = 0 Then sTemp &= "["            'If '0' then add a '[' bracket
If siEnd = 1 Then sTemp &= "]"            'If '1' then add a ']' bracket

If siNum = 0 Then                         'If siNum = 0 then..
sTemp = ""                            'Clear sTemp
Break                                 'Exit the Do Loop
Endif

If Len(sTemp) = siNum Then                'If the length of sTemp = the required amount then..
If sTemp Not Begins "]" And sTemp Not Ends "[" Then  'Check to see that sTemp does not start with "]" and does not end with a "["
sTemp = ""                            'Clear sTemp
Break                                 'Exit the Do Loop
Else                                    'Else
sTemp = ""                            'Clear sTemp
End If                                  'Try again!
Endif
Loop
Next

Return sBrk                                   'Return the sBrk array

End


Output:

NOT OK [ ] ] [ [ ] [ [ ] [ [ [ ] [ [ ] [ ]
NOT OK [ [ [ ] [ [ ] [ [ ] ] [ ] ]
NOT OK [ ] [ [ [ ] ] [ [ ] ] ] [ ] ] [ ] ] ] ]
NOT OK [ [ [ ] [ ] ] ] ] ] [ [ ] ] [ ] [ [ ] ]
NOT OK [ [ ] ] ] ]
NOT OK [ ] ] [ [ ] [ ] [ ]
NOT OK [ [ [ ] [ ]
OK [ ]
NOT OK [ ] ] ] [ ]
NOT OK [ [ ] ] ] ]
OK [ [ [ [ ] ] [ ] [ ] ] ]
OK [ ]
OK [ ] [ ]
NOT OK [ ] ] ] [ ] [ [ [ [ ] [ [ ] [ ]
NOT OK [ ] ] ] [ [ ] ] ] [ ] ] ] ]
NOT OK [ ] ] ] ] ] [ [ ] [ ] ] ] [ ] [ [ [ [ ]


## GAP

Balanced := function(L)
local c, r;
r := 0;
for c in L do
if c = ']' then
r := r - 1;
if r < 0 then
return false;
fi;
elif c = '[' then
r := r + 1;
fi;
od;
return r = 0;
end;

Balanced("");
# true

Balanced("[");
# false

Balanced("]");
# false

Balanced("[]");
# true

Balanced("][");
# false

Balanced("[[][]]");
# true

Balanced("[[[]][]]]");
# false


## GDScript

Works with: Godot version 4.0
extends MainLoop

func generate_brackets(n: int) -> String:
var brackets: Array[String] = []

# Add opening and closing brackets
brackets.resize(2*n)
for i in range(0, 2*n, 2):
brackets[i] = "["
brackets[i+1] = "]"

brackets.shuffle()
return "".join(brackets)

func is_balanced(str: String) -> bool:
var unclosed_brackets := 0
for c in str:
match c:
"[":
unclosed_brackets += 1
"]":
if unclosed_brackets == 0:
return false
unclosed_brackets -= 1
_:
return false
return unclosed_brackets == 0

func _process(_delta: float) -> bool:
randomize()

for i in range(6):
var bracket_string := generate_brackets(i)

if is_balanced(bracket_string):
else:

return true # Exit


## Go

package main

import (
"bytes"
"fmt"
"math/rand"
"time"
)

func init() {
rand.Seed(time.Now().UnixNano())
}

func generate(n uint) string {
a := bytes.Repeat([]byte("[]"), int(n))
for i := len(a) - 1; i >= 1; i-- {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
return string(a)
}

func testBalanced(s string) {
fmt.Print(s + ": ")
open := 0
for _,c := range s {
switch c {
case '[':
open++
case ']':
if open == 0 {
fmt.Println("not ok")
return
}
open--
default:
fmt.Println("not ok")
return
}
}
if open == 0 {
fmt.Println("ok")
} else {
fmt.Println("not ok")
}
}

func main() {
rand.Seed(time.Now().UnixNano())
for i := uint(0); i < 10; i++ {
testBalanced(generate(i))
}
testBalanced("()")
}


Output:

: ok
][: not ok
]][[: not ok
[[][]]: ok
[][[][]]: ok
[[[][][]]]: ok
]][[]]][[[[]: not ok
]][[[]][[][[]]: not ok
[[[[[]]][]]][]][: not ok
[][[][[]][][[][]]]: ok
(): not ok


## Groovy

Generate Arbitrary String of Bracket Pairs:

def random = new Random()

def factorial = { (it > 1) ? (2..it).inject(1) { i, j -> i*j } : 1 }

def makePermutation;
makePermutation = { string, i ->
def n = string.size()
if (n < 2) return string
def fact = factorial(n-1)
assert i < fact*n

def index = i.intdiv(fact)
string[index] + makePermutation(string[0..<index] + string[(index+1)..<n], i % fact)
}

def randomBrackets = { n ->
if (n == 0) return ''
def base = '['*n + ']'*n
def p = random.nextInt(factorial(n*2))
makePermutation(base, p)
}


Check Balance of Bracket String:

boolean balancedBrackets(String brackets, int depth=0) {
if (brackets == null || brackets.empty) return depth == 0
switch (brackets[0]) {
case '[':
return brackets.size() > 1  &&  balancedBrackets(brackets[1..-1], depth + 1)
case ']':
return depth > 0  &&  (brackets.size() == 1  ||  balancedBrackets(brackets[1..-1], depth - 1))
default:
return brackets.size() == 1  ?  depth == 0  :  balancedBrackets(brackets[1..-1], depth)
}
}


Test:

Set brackets = []
(0..100).each {
(0..8).each { r ->
brackets << randomBrackets(r)
}
}

brackets.sort { a, b ->
a.size() <=> b.size() ?: a <=> b
} .each {
def bal = balancedBrackets(it) ? "balanced:   " : "unbalanced: "
println "${bal}${it}"
}


Output:

balanced:
balanced:    []
unbalanced:  ][
balanced:    [[]]
balanced:    [][]
unbalanced:  []][
unbalanced:  ][[]
unbalanced:  ][][
unbalanced:  ]][[
balanced:    [[[]]]
balanced:    [[][]]
balanced:    [[]][]
unbalanced:  [[]]][
balanced:    [][[]]
balanced:    [][][]
unbalanced:  [][]][
unbalanced:  []][[]
unbalanced:  []][][
unbalanced:  []]][[
unbalanced:  ][[[]]
unbalanced:  ][[][]
unbalanced:  ][[]][
unbalanced:  ][][[]
unbalanced:  ][][][
unbalanced:  ][]][[
unbalanced:  ]][[[]
unbalanced:  ]][[][
unbalanced:  ]][][[
unbalanced:  ]]][[[
balanced:    [[[[]]]]
balanced:    [[[][]]]
balanced:    [[[]][]]
balanced:    [[[]]][]
unbalanced:  [[[]]]][
balanced:    [[][[]]]
balanced:    [[][]][]
unbalanced:  [[][]]][
balanced:    [[]][[]]
balanced:    [[]][][]
unbalanced:  [[]][]][
unbalanced:  [[]]][[]
unbalanced:  [[]]]][[
balanced:    [][[][]]
balanced:    [][[]][]
unbalanced:  [][]][[]
unbalanced:  [][]][][
unbalanced:  [][]]][[
unbalanced:  []][[][]
unbalanced:  []][[]][
unbalanced:  []][][[]
unbalanced:  []][][][
unbalanced:  []][]][[
unbalanced:  []]][[[]
unbalanced:  []]][[][
unbalanced:  []]]][[[
unbalanced:  ][[[[]]]
unbalanced:  ][[[]][]
unbalanced:  ][[[]]][
unbalanced:  ][[][][]
unbalanced:  ][[][]][
unbalanced:  ][][[[]]
unbalanced:  ][][[][]
unbalanced:  ][][[]][
unbalanced:  ][][][[]
unbalanced:  ][][][][
unbalanced:  ][][]][[
unbalanced:  ][]][[[]
unbalanced:  ][]][[][

... <SOME OF THE SAME CUT>

balanced:    [[]][[][][[]]]
unbalanced:  [[]][[][]][]][
balanced:    [[]][[]][][[]]
balanced:    [[]][][[][[]]]
balanced:    [[]][][][[][]]
unbalanced:  [[]][][][]]][[
unbalanced:  [[]][][]][[]][
unbalanced:  [[]][]][[[][]]
unbalanced:  [[]][]][[][[]]
unbalanced:  [[]][]][[][][]
unbalanced:  [[]][]][][[][]
unbalanced:  [[]][]][][]][[
unbalanced:  [[]][]]][[][][
unbalanced:  [[]][]]][][[][
unbalanced:  [[]]][[[]][][]
unbalanced:  [[]]][[][[][]]
unbalanced:  [[]]][[][[]]][
unbalanced:  [[]]][][[[[]]]
unbalanced:  [[]]][][[]]][[
unbalanced:  [[]]][][]][[[]
unbalanced:  [[]]][]][[[]][
unbalanced:  [[]]][]][[][][
unbalanced:  [[]]]][[][[]][
unbalanced:  [[]]]][][[[]][
unbalanced:  [[]]]][][[][[]
unbalanced:  [[]]]][][]][[[
unbalanced:  [[]]]]][[[[]][
unbalanced:  [[]]]]][][[[[]
unbalanced:  [[]]]]]][][[[[
unbalanced:  [[]]]]]]][[[[[
balanced:    [[[[[[[]]]]][]]]
unbalanced:  [[[[[[[]]]]]]]][
balanced:    [[[[[[][]]]][]]]
unbalanced:  [[[[[[][]]]]]]][
balanced:    [[[[[[]]][][]]]]
balanced:    [[[[[[]]]][[]]]]
balanced:    [[[[[[]]]][]][]]
balanced:    [[[[[[]]]][]]][]
balanced:    [[[[[[]]]]][][]]
unbalanced:  [[[[[[]]]]][]]][
balanced:    [[[[[[]]]]]][][]
unbalanced:  [[[[[[]]]]]][]][
balanced:    [[[[[][][[]]]]]]
balanced:    [[[[[][][]][]]]]
balanced:    [[[[[][]][[]]]]]
balanced:    [[[[[][]][]][]]]
balanced:    [[[[[][]]]]][][]
unbalanced:  [[[[[][]]]]]]][[
balanced:    [[[[[]][[][]]]]]
balanced:    [[[[[]][[]]]]][]
balanced:    [[[[[]][][[]]]]]
balanced:    [[[[[]][]][[]]]]
balanced:    [[[[[]][]]]][[]]
balanced:    [[[[[]]][[[]]]]]
balanced:    [[[[[]]][[][]]]]
unbalanced:  [[[[[]]][[]]]]][
balanced:    [[[[[]]][][][]]]
balanced:    [[[[[]]][]][[]]]
balanced:    [[[[[]]][]][]][]
unbalanced:  [[[[[]]][]][]]][
balanced:    [[[[[]]][]]][[]]
unbalanced:  [[[[[]]]][]][]][
balanced:    [[[[[]]]]][[]][]
balanced:    [[[[[]]]]][][[]]
balanced:    [[[[[]]]]][][][]
unbalanced:  [[[[[]]]]][]][[]
unbalanced:  [[[[[]]]]]][[]][
unbalanced:  [[[[[]]]]]][][[]
balanced:    [[[[][[[[]]]]]]]
balanced:    [[[[][[[][]]]]]]
balanced:    [[[[][[]][[]]]]]
balanced:    [[[[][[]][][]]]]
balanced:    [[[[][[]]]]][][]
balanced:    [[[[][][][][]]]]
balanced:    [[[[][][][]]][]]
balanced:    [[[[][][]][][]]]
balanced:    [[[[][][]]][][]]
unbalanced:  [[[[][][]]][]]][
balanced:    [[[[][][]]]][][]
balanced:    [[[[][]][[[]]]]]
balanced:    [[[[][]][[]]]][]
balanced:    [[[[][]][][]][]]
unbalanced:  [[[[][]]][]]]][[
balanced:    [[[[][]]]][[[]]]
balanced:    [[[[][]]]][][[]]
unbalanced:  [[[[][]]]]][][][
unbalanced:  [[[[][]]]]]]][[[
balanced:    [[[[]][[][]][]]]
balanced:    [[[[]][[]]]][[]]
balanced:    [[[[]][][[][]]]]
unbalanced:  [[[[]][][[]]]]][
balanced:    [[[[]][][][]][]]
balanced:    [[[[]][][]][[]]]
balanced:    [[[[]][][]][][]]
balanced:    [[[[]][][]][]][]
balanced:    [[[[]][][]]][[]]
unbalanced:  [[[[]][]][]][]][
balanced:    [[[[]][]]][[]][]
unbalanced:  [[[[]][]]]][[][]
unbalanced:  [[[[]][]]]][[]][
unbalanced:  [[[[]][]]]]][[[]
balanced:    [[[[]]][[]]][[]]
balanced:    [[[[]]][[]]][][]
balanced:    [[[[]]][][][[]]]
balanced:    [[[[]]][]][[]][]
unbalanced:  [[[[]]][]][[]]][
unbalanced:  [[[[]]][]]][[]][
unbalanced:  [[[[]]][]]][]][[
unbalanced:  [[[[]]][]]]][[[]
balanced:    [[[[]]]][[[[]]]]
balanced:    [[[[]]]][[[][]]]
balanced:    [[[[]]]][[]][][]
unbalanced:  [[[[]]]][[]][]][
unbalanced:  [[[[]]]][][]]][[
unbalanced:  [[[[]]]][]][[[]]
unbalanced:  [[[[]]]][]][[]][
unbalanced:  [[[[]]]][]]][][[
unbalanced:  [[[[]]]][]]]][[[
unbalanced:  [[[[]]]]][][][[]
unbalanced:  [[[[]]]]][][]][[
unbalanced:  [[[[]]]]]][[]][[
unbalanced:  [[[[]]]]]][][][[

The simplest solution exploits the idea of stack-based automaton, which could be implemented by a fold.

isMatching :: String -> Bool
isMatching = null . foldl aut []
where
aut ('[':s) ']' = s
-- aut ('{':s) '}' = s -- automaton could be extended
aut s x = x:s


This generates an infinite stream of correct balanced brackets expressions:

brackets = filter isMatching
$[1.. ] >>= (replicateM "[]{}")  λ> take 10 brackets ["[]","{}","[[]]","[][]","[]{}","[{}]","{[]}","{{}}","{}[]","{}{}"] In case the index of unmatched opening bracket is need to be found, following solution is suitable. import Control.Monad import System.Random import Text.Printf import VShuffle -- Return whether a string contains balanced brackets. Nothing indicates a -- balanced string, while (Just i) means an imbalance was found at, or just -- after, the i'th bracket. We assume the string contains only brackets. isBalanced :: String -> Maybe Int isBalanced = bal (-1) 0 where bal :: Int -> Int -> String -> Maybe Int bal _ 0 [] = Nothing bal i _ [] = Just i bal i (-1) _ = Just i bal i n ('[':bs) = bal (i + 1) (n + 1) bs bal i n (']':bs) = bal (i + 1) (n - 1) bs -- Print a string, indicating whether it contains balanced brackets. If not, -- indicate the bracket at which the imbalance was found. check :: String -> IO () check s = maybe (good s) (bad s) (isBalanced s) where good = printf "Good \"%s\"\n" bad s n = printf "Bad \"%s\"\n%*s^\n" s (n + 6) " " main :: IO () main = do let bs = cycle "[]" rs <- replicateM 10 newStdGen zipWithM_ (\n r -> check$ shuffle (take n bs) r) [0,2 ..] rs


We put our list shuffling function in a separate module. For efficiency we use mutable vectors, although for the short lists in our example it doesn't really matter.

module VShuffle
( shuffle
) where

import Data.List (mapAccumL)
import System.Random
import qualified Data.Vector as V
import qualified Data.Vector.Generic.Mutable as M

-- Generate a list of array index pairs, each corresponding to a swap.
pairs
:: (Enum a, Random a, RandomGen g)
=> a -> a -> g -> [(a, a)]
pairs l u r = snd $mapAccumL step r [l .. pred u] where step r i = let (j, r') = randomR (i, u) r in (r', (i, j)) -- Return a random permutation of the list. We use the algorithm described in -- http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm. shuffle :: (RandomGen g) => [a] -> g -> [a] shuffle xs r = V.toList . runST$
do v <- V.unsafeThaw $V.fromList xs mapM_ (uncurry$ M.swap v) $pairs 0 (M.length v - 1) r V.unsafeFreeze v  Here's some sample output. Good "" Bad "][" ^ Good "[[]]" Bad "[]][][" ^ Bad "[]]][][[" ^ Bad "][][[[]][]" ^ Bad "[[][][]]][][" ^ Bad "][]][[[][][[]]" ^ Good "[[][[][[]]][[]]]" Bad "]]][[[][][][[][]][" ^  and scanl also yields a simple fit when we want the index of the tipping point: import Control.Applicative ((<|>)) import Data.List (findIndex, replicate, scanl) import Data.List.Split (chunksOf) import System.Random -------------------- BALANCED BRACKETS ------------------- nesting :: String -> [Int] nesting = tail . scanl (flip level) 0 where level '[' = succ level ']' = pred level _ = id bracketProblemIndex :: String -> Maybe Int bracketProblemIndex s = findIndex (< 0) depths <|> unClosed where depths = nesting s unClosed | 0 /= last depths = Just$ pred (length s)
| otherwise = Nothing

--------------------------- TEST -------------------------
main :: IO ()
main = do
let g = mkStdGen 137
mapM_ (putStrLn . showProblem) $chunksOf 6 (bracket <$> take 60 (randomRs (0, 1) g))

showProblem s =
case bracketProblemIndex s of
Just i -> s <> ": Unmatched\n" <> replicate i ' ' <> "^"
_ -> s <> ": OK\n"

bracket :: Int -> Char
bracket 0 = '['
bracket _ = ']'

Output:
]][]][: Unmatched
^
][[][[: Unmatched
^
][][[[: Unmatched
^
]][][]: Unmatched
^
[[][]]: OK

]]][]]: Unmatched
^
[][][[: Unmatched
^
[]]]]]: Unmatched
^
][[][[: Unmatched
^
[][]][: Unmatched
^


## Icon and Unicon

procedure main(arglist)
every s := genbs(!arglist) do
write(image(s), if isbalanced(s) then " is balanced." else " is unbalanced")
end

procedure isbalanced(s) # test if a string is balanced re: []
return (s || " ") ? (bal(,'[',']') = *s+1)
end

procedure genbs(i)  # generate strings of i pairs of []
s := ""
every 1 to i do s ||:= "[]"       # generate i pairs
every !s := ?s                    # shuffle
return s
end


Output:

> isbal.exe 2 3 3 3 3 3 3 3 4 4 4

"[[]]" is balanced.
"]]]]]]" is unbalanced
"]]]]]]" is unbalanced
"[][][]" is balanced.
"]][[[]" is unbalanced
"[[[][[" is unbalanced
"]]]]]]" is unbalanced
"[]]]]]" is unbalanced
"]][]][]]" is unbalanced
"[[[[[][[" is unbalanced
"[[[[[][]" is unbalanced

## J

Solution:

bracketDepth    =:  '[]' -&(+/\)/@:(=/) ]
checkBalanced   =:  _1 -.@e. bracketDepth
genBracketPairs =:  (?~@# { ])@#"0 1&'[]'          NB. bracket pairs in arbitrary order


Examples:

   (, ' ' ,  ('bad';'OK') {::~ checkBalanced)"1 genBracketPairs i. 10
OK
[[[]]]             OK
[][[]][]           OK
[][[[][]]]         OK
[[]][[][][]][]     OK


Comments: This task highlights the versatility and usefulness of J's scanning modifiers, / and \.

The checkBalanced verb would need modification ( checkBalanced =: ((0 = {:) *. _1 -.@e. ])@bracketDepth ) if the task were extended to include uneven numbers of opening and closing brackets.

## Java

Works with: Java version 1.5+
public class BalancedBrackets {

public static boolean hasBalancedBrackets(String str) {
int brackets = 0;
for (char ch : str.toCharArray()) {
if (ch == '[') {
brackets++;
} else if (ch == ']') {
brackets--;
} else {
return false;   // non-bracket chars
}
if (brackets < 0) {   // closing bracket before opening bracket
return false;
}
}
return brackets == 0;
}

public static String generateBalancedBrackets(int n) {
assert n % 2 == 0;   // if n is odd we can't match brackets
char[] ans = new char[n];
int openBracketsLeft = n / 2;
int unclosed = 0;
for (int i = 0; i < n; i++) {
if (Math.random() >= 0.5 && openBracketsLeft > 0 || unclosed == 0) {
ans[i] = '[';
openBracketsLeft--;
unclosed++;
} else {
ans[i] = ']';
unclosed--;
}
}
return String.valueOf(ans);
}

public static void main(String[] args) {
for (int i = 0; i <= 16; i += 2) {
String brackets = generateBalancedBrackets(i);
System.out.println(brackets + ": " + hasBalancedBrackets(brackets));
}

String[] tests = {"", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"};
for (String test : tests) {
System.out.println(test + ": " + hasBalancedBrackets(test));
}
}
}


Sample output (generate uses random numbers, so it should not be the same every time):

: true
[]: true
[[]]: true
[[]][]: true
[][][][]: true
[][[][[]]]: true
[[][[][][]]]: true
[[][][]][[[]]]: true
[][[[][[][[]]]]]: true
: true
[]: true
][: false
[][]: true
][][: false
[[][]]: true
[]][[]: false

### Extended

import java.util.ArrayDeque;
import java.util.Deque;

public class BalancedBrackets {

public static boolean areSquareBracketsBalanced(String expr) {
return isBalanced(expr, "", "", "[", "]", false);
}
public static boolean areBracketsBalanced(String expr) {
return isBalanced(expr, "", "", "{([", "})]", false);
}
public static boolean areStringAndBracketsBalanced(String expr) {
return isBalanced(expr, "'\"", "\\\\", "{([", "})]", true);
}
public static boolean isBalanced(String expr, String lit, String esc, String obr, String cbr, boolean other) {
boolean[] inLit = new boolean[lit.length()];
Deque<Character> stack = new ArrayDeque<Character>();
for (int i=0; i<expr.length(); i+=1) {
char c = get(expr, i);
int x;
if ((x = indexOf(inLit, true)) != -1) {
if (c == get(lit, x) && get(expr, i-1) != get(esc, x)) inLit[x] = false;
}
else if ((x = indexOf(lit, c)) != -1)
inLit[x] = true;
else if ((x = indexOf(obr, c)) != -1)
stack.push(get(cbr, x));
else if (indexOf(cbr, c) != -1) {
if (stack.isEmpty() || stack.pop() != c) return false;
}
else if (!other)
return false;
}
return stack.isEmpty();
}

static int indexOf(boolean[] a, boolean b) {
for (int i=0; i<a.length; i+=1) if (a[i] == b) return i;
return -1;
}
static int indexOf(String s, char c) {
return s.indexOf(c);
}
static char get(String s, int i) {
return s.charAt(i);
}

public static void main(String[] args) {
System.out.println("With areSquareBracketsBalanced:");
for (String s: new String[] {
"", "[]", "[][]", "[[][]]", "][", "][][", "[]][[]", "[", "]"
}
) {
System.out.printf("%s: %s\n", s, areSquareBracketsBalanced(s));
}
System.out.println("\nBut also with areStringAndBracketsBalanced:");
for (String s: new String[] {
"x[]", "[x]", "[]x", "([{}])", "([{}]()", "([{ '([{\\'([{' \"([{\\\"([{\" }])",
}
) {
System.out.printf("%s: %s\n", s, areStringAndBracketsBalanced(s));
}
}
}

Output:
With areSquareBracketsBalanced:
: true
[]: true
[][]: true
[[][]]: true
][: false
][][: false
[]][[]: false
[: false
]: false

But also with areStringAndBracketsBalanced:
x[]: true
[x]: true
[]x: true
([{}]): true
([{}](): false
([{ '([{\'([{' "([{\"([{" }]): true


## JavaScript

### ES5

#### Iterative

function shuffle(str) {
var a = str.split(''), b, c = a.length, d
while (c) b = Math.random() * c-- | 0, d = a[c], a[c] = a[b], a[b] = d
return a.join('')
}

function isBalanced(str) {
var a = str, b
do { b = a, a = a.replace(//g, '') } while (a != b)
return !a
}

var M = 20
while (M-- > 0) {
var N = Math.random() * 10 | 0, bs = shuffle('['.repeat(N) + ']'.repeat(N))
console.log('"' + bs + '" is ' + (isBalanced(bs) ? '' : 'un') + 'balanced')
}


Sample output:

"[]" is balanced
"]][[]][[[]" is unbalanced
"]][[[][][][]][" is unbalanced
"[][[[[][][[[]]]]]]" is balanced
"][" is unbalanced
"[[[]]]][[]" is unbalanced
"][[]" is unbalanced
"][[][]][[[]]" is unbalanced
"[[][]]][" is unbalanced
"[[[]]][[]]]][][[" is unbalanced
"[]][[]]][[[[][]]" is unbalanced
"[]" is balanced
"][]][[][" is unbalanced
"[[]][[][]]" is balanced
"[[]]" is balanced
"]][]][[]][[[" is unbalanced
"][]][][[" is unbalanced
"[[]]" is balanced
"][][" is unbalanced
"[[]]][][][[]][" is unbalanced

#### Another solution

Works with: Node.js
console.log("Supplied examples");
var tests = ["", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"];
for (var test of tests)
{
console.log("The string '" + test + "' is " +
(isStringBalanced(test) ? "" : "not ") + "OK.");
}
console.log();
console.log("Random generated examples");
for (var example = 1; example <= 10; example++)
{
var test = generate(Math.floor(Math.random() * 10) + 1);
console.log("The string '" + test + "' is " +
(isStringBalanced(test) ? "" : "not ") + "OK.");
}

function isStringBalanced(str)
{
var paired = 0;
for (var i = 0; i < str.length && paired >= 0; i++)
{
var c = str[i];
if (c == '[')
paired++;
else if (c == ']')
paired--;
}
return (paired == 0);
}

function generate(n)
{
var opensCount = 0, closesCount = 0;
// Choose at random until n of one type generated
var generated = "";
while (opensCount < n && closesCount < n)
{
switch (Math.floor(Math.random() * 2) + 1)
{
case 1:
opensCount++;
generated += "[";
break;
case 2:
closesCount++;
generated += "]";
break;
default:
break;
}
}
// Now pad with the remaining other brackets
generated +=
opensCount == n ? "]".repeat(n - closesCount) : "[".repeat(n - opensCount);
return generated;
}

Output:
Supplied examples
The string '' is OK.
The string '[]' is OK.
The string '][' is not OK.
The string '[][]' is OK.
The string '][][' is not OK.
The string '[[][]]' is OK.
The string '[]][[]' is not OK.

Random generated examples
The string ']]][[[[[]][[[]]]]][[' is not OK.
The string '[][]]][]][[]]][[[[' is not OK.
The string ']][][[[][][][]' is not OK.
The string '][]][[][[[][]]][' is not OK.
The string '[]][[[][]]' is not OK.
The string ']]][[[[]]]][]]][[[[[' is not OK.
The string ']]]][][]][[[[[' is not OK.
The string '[][[[[][]][]]]' is OK.
The string '][[]]][[[[]]][[[]]' is not OK.
The string '[]' is OK.


### ES6

#### Functional

With visual indication of where the balance fails:

(() => {
'use strict';

// ---------------- BALANCED BRACKETS ----------------

// firstUnbalancedBracket :: String -> String -> Maybe Int
const firstUnbalancedBracket = brackets =>
haystack => {
const [openBracket, closeBracket] = [...brackets];
const go = (xs, iDepth, iCharPosn) =>
// iDepth: initial nesting depth (0 = closed)
// iCharPosn: starting character position
0 < xs.length ? (() => {
const
h = xs[0],
tail = xs.slice(1),
iNext = iDepth + (
brackets.includes(h) ? (
openBracket === h ? (
1
) : -1
) : 0
);
return 0 > iNext ? (
Just(iCharPosn) // Unmatched closing bracket.
) : 0 < tail.length ? go(
tail, iNext, 1 + iCharPosn
) : 0 !== iNext ? (
Just(iCharPosn)
) : Nothing();
})() : 0 !== iDepth ? (
Just(iCharPosn)
) : Nothing();
return go([...haystack], 0, 0);
};

// ---------------------- TEST -----------------------
// main :: IO ()
const main = () => {
const
intPairs = 6,
strPad = ' '.repeat(4 + (2 * intPairs));
console.log(
enumFromTo(0)(intPairs)
.map(pairCount => {
const
stringLength = 2 * pairCount,
strSample = randomBrackets(stringLength);
return "'" + strSample + "'" +
iUnMatched => 'problem\n' +
' '.repeat(1 + iUnMatched) + '^'
)(
firstUnbalancedBracket('[]')(strSample)
);
}).join('\n')
);
};

// Int -> String
const randomBrackets = n =>
enumFromTo(1)(n)
.map(() => Math.random() < 0.5 ? (
'['
) : ']').join('');

// --------------------- GENERIC ---------------------

// Just :: a -> Maybe a
const Just = x => ({
type: 'Maybe',
Nothing: false,
Just: x
});

// Nothing :: Maybe a
const Nothing = () => ({
type: 'Maybe',
Nothing: true,
});

// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = m =>
n => !isNaN(m) ? (
Array.from({
length: 1 + n - m
}, (_, i) => m + i)
) : enumFromTo_(m)(n);

// maybe :: b -> (a -> b) -> Maybe a -> b
const maybe = v =>
// Default value (v) if m is Nothing, or f(m.Just)
f => m => m.Nothing ? (
v
) : f(m.Just);

// ---
return main();
})();

Output:
''              OK
'[]'            OK
'[][['          problem
^
'[]]][['        problem
^
'[][[][[['      problem
^
'[][[[]][]]'    OK
']]][[][][][]'  problem
^

## jq

Works with: jq

Works with gojq, the Go implementation of jq.

In this entry, two solutions are given: the first uses an external source of entropy and jq's until control structure; the second uses a low-entropy PRNG based on jq's now, and gsub/2.

### High entropy solution using until

< /dev/random tr -cd '0-9' | fold -w 1 | jq -Mcnr '

# Output: a PRN in range(0;$n) where$n is .
def prn:
if . == 1 then 0
else . as $n | (($n-1)|tostring|length) as $w | [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;

def prb: 2 | prn == 0;

def balanced:
{array: explode, parity: 0}
| until( .result | type == "boolean";
if .array == [] then .result = (.parity == 0)
else .parity += (.array[0] | if . == 91 then 1 else -1 end)
| if .parity < 0 then .result = false
else .array |= .[1:]
end
end ).result ;

def task($n): if$n%2 == 1 then null
else  [ (range(0; $n) | if prb then "[" else "]" end) // ""] | add | "$$.): \(balanced)" end; task(0), task(2), (range(0;10) | task(4))  Output: : true [[: false [][[: false ][[[: false ]][[: false [[]]: true ]][[: false ][[[: false [[[[: false [][[: false ][[[: false []][: false  ### Low entropy solution with gsub  def prb: (now|tostring[-1:] | tonumber) % 2 == 0; def balanced: if length==0 then true elif .[:1] == "]" then false else test("[[][]]") and (gsub("[[][]]"; "") | balanced) end; def task(n): if n%2 == 1 then null else (reduce range(0; n) as i (""; . + (if prb then "[" else "]" end) )) | "\(.): \(balanced)" end; task(0), task(2), (range(0;10) | task(4)) Output: Similar to above. ## Julia using Printf function balancedbrackets(str::AbstractString) i = 0 for c in str if c == '[' i += 1 elseif c == ']' i -=1 end if i < 0 return false end end return i == 0 end brackets(n::Integer) = join(shuffle(collect(Char, "[]" ^ n))) for (test, pass) in map(x -> (x, balancedbrackets(x)), collect(brackets(i) for i = 0:8)) @printf("%22s%10s\n", test, pass ? "pass" : "fail") end  Output:  pass ][ fail [][] pass ][[]][ fail [[[]]][] pass ]]]][[[][[ fail ]]][[][][[[] fail ]][]][][[[][][ fail []][]]]][[[][[[] fail One-line version: balancedbrackets(str::AbstractString) = foldl((x, y) -> x < 0 ? -1 : x + y, collect((x == '[') - (x == ']') for x in str), init = 0) == 0  ## K  gen_brackets:{"[]"@x _draw 2} check:{r:(-1;1)@"["=x; *(0=+/cs<'0)&(0=-1#cs:+\r)} {(x;check x)}' gen_brackets' 2*1+!10 (("[[";0) ("[][]";1) ("][][]]";0) ("[[][[][]";0) ("][]][[[[[[";0) ("]]][[]][]]][";0) ("[[[]][[[][[[][";0) ("[[]][[[]][]][][]";1) ("][[][[]]][[]]]][][";0) ("]][[[[]]]][][][[]]]]";0))  ## Klingphix "[[]][]]" %acc 0 !acc %flag false !flag len [ get tochar dup "[" == [acc 1 + !acc] if "]" == [acc 1 - !acc] if acc 0 < [true !flag] if ] for print acc 0 # flag or ( [" is NOT ok"] [" is OK"] ) if print " " input  ## Kotlin Translation of: FreeBASIC import java.util.Random fun isBalanced(s: String): Boolean { if (s.isEmpty()) return true var countLeft = 0 // number of left brackets so far unmatched for (c in s) { if (c == '[') countLeft++ else if (countLeft > 0) countLeft-- else return false } return countLeft == 0 } fun main(args: Array<String>) { println("Checking examples in task description:") val brackets = arrayOf("", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]") for (b in brackets) { print(if (b != "") b else "(empty)") println("\t " + if (isBalanced(b)) "OK" else "NOT OK") } println() println("Checking 7 random strings of brackets of length 8:") val r = Random() (1..7).forEach { var s = "" for (j in 1..8) { s += if (r.nextInt(2) == 0) '[' else ']' } println("s " + if (isBalanced(s)) "OK" else "NOT OK") } }  Sample output (last 7 lines random) : Output: Checking examples in task description: (empty) OK [] OK ][ NOT OK [][] OK ][][ NOT OK [[][]] OK []][[] NOT OK Checking 7 random strings of brackets of length 8: [[[[]]][ NOT OK [][[][]] OK [[[[[]]] NOT OK [[[[[]]] NOT OK [[[]]][] OK ]]]][[][ NOT OK ]][]][][ NOT OK  ## L++ (include "string") (defn bool balanced (std::string s) (def bal 0) (foreach c s (if (== c #$) (++ bal) (if (== c #$) (-- bal))) (if (< bal 0) (return false))) (return (== bal 0))) (main (decl std::string (at tests) |{"", "[]", "[][]", "[[][]]", "][", "][][", "[]][[]"}|) (pr std::boolalpha) (foreach x tests (prn x "\t" (balanced x))))  ## Lasso define randomparens(num::integer,open::string='[',close::string=']') => { local(out) = array with i in 1 to #num do { #out->insert(']', integer_random(1,#out->size || 1)) #out->insert('[', integer_random(1,#out->size || 1)) } return #out->join } define validateparens(input::string,open::string='[',close::string=']') => { local(i) = 0 #input->foreachcharacter => { #1 == #open ? #i++ #1 == #close && --#i < 0 ? return false } return #i == 0 ? true | false } with i in 1 to 10 let input = randomparens(#i) select #input + ' = ' + validateparens(#input)  Output: [] = true ][[] = false ]][[[] = false ][][[][] = false [[[]][[]]] = true ]]]][[[[][[] = false [[[[[[]]]]]][] = true [[]][][]][]][[[] = false [[[]][[[]][]]][[]] = true ## Liberty BASIC print "Supplied examples" for i =1 to 7 read test print "The string '"; test; "' is "; validString( test) next i print data "", "[]", "][","[][]","][][","[[][]]","[]][[]" print "Random generated examples" for example =1 to 10 test =generate( int( 1 +10 *rnd(1))) print "The string '"; test; "' is "; validString( test) next example end function validString( in) if left( in, 1) <>"[" and len( test) <>0 then validString ="not OK. Opens wrongly." exit function end if paired =0 for i =1 to len( in) c =mid( in, i, 1) if c ="[" then paired =paired +1 if c ="]" then paired =paired -1 if paired <0 then exit for end if next i if ( lBr =rBr) and ( paired >=0) then validString ="OK." else validString ="not OK. Unbalanced." end function function generate( N) lBr =0 rBr =0 ' choose at random until N of one type generated while ( lBr <N) and ( rBr <N) select case int( 1.5 +rnd( 1)) case 1 lBr =lBr +1 generate =generate +"[" case 2 rBr =rBr +1 generate =generate +"]" end select wend ' now pad with the remaining other brackets if lBr =N then generate =generate +string( N -rBr, "]") else generate =generate +string( N -lBr, "[") end if end function function string( n, c) for i =1 to n op =op +c next i string =op end function end Supplied examples The string is OK. The string '[]' is OK. The string '][' is not OK. Unbalanced. The string '[][]' is OK. The string '][][' is not OK. Unbalanced. The string '[[][]]' is OK. The string '[]][[]' is not OK. Unbalanced.  Random generated examples The string '[[][[[][]]]]' is OK. The string ']]]][[[[' is not OK. Unbalanced. The string '[[]][]' is OK. The string '[][[][[]][]]' is OK. The string '][[[]]][][' is not OK. Unbalanced. The string ']]]]][[[[[' is not OK. Unbalanced. The string '[[[]]]' is OK. The string ']][][[' is not OK. Unbalanced. The string '[[]]][][[][]' is not OK. Unbalanced. The string '][[][[][][]]][[]' is not OK. Unbalanced.  ## Lua function isBalanced(s) --Lua pattern matching has a 'balanced' pattern that matches sets of balanced characters. --Any two characters can be used. return s:gsub('%b[]','')=='' and true or false end function randomString() math.randomseed(os.time()) math.random()math.random()math.random()math.random() local tokens={'[',']'} local result={} for i=1,8 do table.insert(result,tokens[math.random(1,2)]) end return table.concat(result) end local RS=randomString() print(RS) print(isBalanced(RS))  ## M2000 Interpreter module Balanced_brackets{ // Generate a string with N opening brackets [ and with N closing brackets ], in some arbitrary order. function randomBrackets(max as long) { if max<1 then max=1 def putbracket()=mid("[[[[]]",random(1,6),1) dim a(random(1, max)) as string<<putbracket() =a()#str("") } // Determine whether the generated string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest. function check(s as string) { long i, level for i=1 to len(s) if mid(s,i,1)="[" then level++ else level-- if level<0 then exit for next =level=0 } string k boolean m do k=randomBrackets(10) m=check(k) print k;@(12);": ";if(m->"OK", "NOT OK") until m } Balanced_brackets Output: [[[] : NOT OK [[][]] : OK  ## Maple This functionality is provided by Maple. > use StringTools in > IsBalanced( "", "[", "]" ); > IsBalanced( "[", "[", "]" ); > IsBalanced( "]", "[", "]" ); > IsBalanced( "[]", "[", "]" ); > IsBalanced( "][", "[", "]" ); > IsBalanced( "[][]", "[", "]" ); > IsBalanced( "[[][]]", "[", "]" ); > IsBalanced( "[[[]][]]]", "[", "]" ); > s := Random( 20, "[]" ); > IsBalanced( s, "[", "]" ) > end use; true false false true false true true false s := "[[]][[[[[[[[[]][][]]" false Furthermore, Maple can check whether multiple fences are balanced in the same string. > StringTools:-IsBalanced( "[()()]", "[(", "])" ); true ## Mathematica /Wolfram Language (* Generate open/close events. *) gen[n_] := RandomSample[Table[{1, -1}, {n}] // Flatten] (* Check balance. *) check[lst_] := And @@ (# >= 0 & /@ Accumulate[lst]) (* Do task for string with n opening and n closing brackets. *) doString[n_] := ( lst = gen[n]; str = StringJoin[lst /. {1 -> "[", -1 -> "]"}]; Print[str <> If[match[lst, 0], " is balanced.", " is not balanced."]])  ## MATLAB / Octave function x = isbb(s) t = cumsum((s=='[') - (s==']')); x = all(t>=0) && (t(end)==0); end;  Output: octave:9> isbb('[]') ans = 1 octave:10> isbb('][') ans = 0 octave:11> isbb('][][') ans = 0 octave:12> isbb('[][]') ans = 1 octave:13> isbb('[][][]') ans = 1 octave:14> isbb('[]][[]') ans = 0  ## Maxima brack(s) := block( [n: slength(s), r: 0, c], catch( for i thru n do ( if cequal(c: charat(s, i), "]") then (if (r: r - 1) < 0 then throw(false)) elseif cequal(c, "[") then r: r + 1 ), is(r = 0) ) ) brack(""); true brack("["); false brack("]"); false brack("[]"); true brack("]["); false brack("[[][]]"); true brack("[[[]][]]]"); false  ## Mercury :- module balancedbrackets. :- interface. :- import_module io. :- pred main(io::di, io::uo) is det. :- import_module list, random, char. :- pred brackets(int::in,list(char)::out,supply::mdi,supply::muo) is det. :- pred imbalance(list(char)::in,int::out) is semidet. :- pred balanced(list(char)::in) is semidet. :- implementation. :- import_module int. imbalance([],0). imbalance(['['|T],N) :- imbalance(T,N+1). imbalance([']'|T],N) :- N > 0, imbalance(T,N-1). balanced(S) :- imbalance(S,0). brackets(N,S,!RS) :- ( N < 1 -> S is [] ; random(0,2,R,!RS), ( R is 0 -> S is ['['|T], brackets(N-1,T,!RS) ; S is [']'|T], brackets(N-1,T,!RS))). main(!IO) :- random.init(0,RS), brackets(4,S,RS,_), print(S,!IO), ( balanced(S) -> print(" is balanced\n",!IO) ; print(" is unbalanced\n", !IO) ). ## MiniScript We start by defining a function: isBalanced = function(str) level = 0 for c in str if c == "[" then level = level + 1 if c == "]" then level = level - 1 if level < 0 then return false end for return level == 0 end function  We can evaluate the example strings with this code: examples = [ "", "[]", "[][]", "[[][]]", "][", "][][", "[]][[]", "[[[]"] for str in examples balanced = isBalanced(str) if balanced then outcome = "is OK" else outcome = "NOT OK" print """" + str + """ " + outcome end for  Output: "" is OK "[]" is OK "[][]" is OK "[[][]]" is OK "][" NOT OK "][][" NOT OK "[]][[]" NOT OK "[[[]" NOT OK ## Modula-2 An interesting point is how to ensure that all strings of N left plus N right brackets are equally likely. The program below shows one way of doing this. MODULE Brackets; IMPORT IO, Lib; CONST MaxN = 4; PROCEDURE DoTest( N : CARDINAL); VAR brStr : ARRAY [0..2*MaxN] OF CHAR; (* string of brackets *) verdict : ARRAY [0..2] OF CHAR; br : CHAR; k, nL, nR, randNum : CARDINAL; count : INTEGER; BEGIN k := 0; (* index into brStr *) nL := N; nR := N; (* number of left/right brackets remaining *) WHILE (nL > 0) AND (nR > 0) DO randNum := Lib.RANDOM( nL + nR); IF (randNum < nL) THEN brStr[k] := '['; DEC(nL); ELSE brStr[k] := ']'; DEC(nR); END; INC(k); END; (* Here when only one kind of bracket is possible *) IF (nL = 0) THEN br := ']' ELSE br := '['; END; WHILE (k < 2*N) DO brStr[k] := br; INC(k); END; brStr[k] := 0C; (* null to mark end of string *) (* Test for balance *) count := 0; k := 0; REPEAT IF brStr[k] = '[' THEN INC( count) ELSE DEC( count) END; INC( k); UNTIL (count < 0) OR (k = 2*N); IF (count < 0) THEN verdict := 'no' ELSE verdict := 'yes' END; IO.WrStr( brStr); IO.WrStr(' '); IO.WrStr( verdict); IO.WrLn; END DoTest; (* Main routine *) VAR j : CARDINAL; BEGIN Lib.RANDOMIZE; FOR j := 1 TO 10 DO DoTest( Lib.RANDOM(MaxN) + 1); END; END Brackets.  Output: []][[]][ no [[[]]] yes ][ no ][]][[ no [][[]] yes ][[] no [][] yes ][][]][[ no [] yes []][[][] no  ## Nanoquery Translation of: Python import Nanoquery.Util def gen(N) txt = {"[", "]"} * N txt = new(Random).shuffle(txt) return "".join("", txt) end def balanced(txt) braced = 0 for ch in txt if ch = "[" braced += 1 else if ch = "]" braced -= 1 end if braced < 0 return false end end return braced = 0 end // unlike Python, the range function is inclusive in Nanoquery for N in range(1, 10) txt = gen(N) if balanced(txt) println format("%-22s is balanced", txt) else println format("%-22s is not balanced", txt) end end Output:  is balanced [] is balanced [][] is balanced []][][ is not balanced []][[[]] is not balanced [][[[[]]]] is balanced ][[]][][]][[ is not balanced ][]][[][]][[[] is not balanced [[]][[[]][]][]][ is not balanced [[][[]][][]]][[[]] is not balanced [[][][[[][]][[]]][]] is balanced ## Nim from random import random, randomize, shuffle from strutils import repeat randomize() proc gen(n: int): string = result = "[]".repeat(n) shuffle(result) proc balanced(txt: string): bool = var b = 0 for c in txt: case c of '[': inc(b) of ']': dec(b) if b < 0: return false else: discard b == 0 for n in 0..9: let s = gen(n) echo "'", s, "' is ", (if balanced(s): "balanced" else: "not balanced")  Output: '' is balanced '][' is not balanced '][[]' is not balanced '[][[]]' is balanced '[[]][][]' is balanced ']][][[[][]' is not balanced '][]][][][[][' is not balanced '[[[[[[]]]][]]]' is balanced '][[][]]]][[[[][]' is not balanced '][][][][][[][[]]][' is not balanced ## Nu def gen_brackets [n: int] { 1..in | each {["[" "]"]} | flatten | shuffle | str join } def check_brackets [] { split chars | reduce --fold 0 {|x, d| if (d < 0) {-1} else { d + (if (x == "[") {1} else {-1}) } } | in > -1 } 1..10 | each {gen_brackets in | {brackets: in, valid: (in | check_brackets)}} | print Output: ╭───┬──────────────────────┬───────╮ │ # │ brackets │ valid │ ├───┼──────────────────────┼───────┤ │ 0 │ ][ │ false │ │ 1 │ []][ │ false │ │ 2 │ [[][]] │ true │ │ 3 │ [[[][]]] │ true │ │ 4 │ ]]][[[[][] │ false │ │ 5 │ [][][][[[]]] │ true │ │ 6 │ ]]]]][]][[[[[[ │ false │ │ 7 │ ][[][]]]][[][[[] │ false │ │ 8 │ []]]][][][[][]][[[ │ false │ │ 9 │ ][][][[[[[]]]][[]][] │ false │ ╰───┴──────────────────────┴───────╯  ## Oberon-2 Works with: oo2c version 2 MODULE BalancedBrackets; IMPORT Object, Object:Boxed, ADT:LinkedList, ADT:Storable, IO, Out := NPCT:Console; TYPE (* CHAR is not boxed in the standard lib *) (* so make a boxed char *) Character* = POINTER TO CharacterDesc; CharacterDesc* = RECORD (Boxed.ObjectDesc) c: CHAR; END; (* Method for a boxed char *) PROCEDURE (c: Character) INIT*(x: CHAR); BEGIN c.c := x; END INIT; PROCEDURE NewCharacter*(c: CHAR): Character; VAR x: Character; BEGIN NEW(x);x.INIT(c);RETURN x END NewCharacter; PROCEDURE (c: Character) ToString*(): STRING; BEGIN RETURN Object.NewLatin1Char(c.c); END ToString; PROCEDURE (c: Character) Load*(r: Storable.Reader) RAISES IO.Error; BEGIN r.ReadChar(c.c); END Load; PROCEDURE (c: Character) Store*(w: Storable.Writer) RAISES IO.Error; BEGIN w.WriteChar(c.c); END Store; PROCEDURE (c: Character) Cmp*(o: Object.Object): LONGINT; BEGIN IF c.c < o(Character).c THEN RETURN -1 ELSIF c.c = o(Character).c THEN RETURN 0 ELSE RETURN 1 END END Cmp; (* end of methods for a boxed char *) PROCEDURE CheckBalance(str: STRING): BOOLEAN; VAR s: LinkedList.LinkedList(Character); chars: Object.CharsLatin1; n, x: Boxed.Object; i,len: LONGINT; BEGIN i := 0; chars := str(Object.String8).CharsLatin1(); len := str.length; s := NEW(LinkedList.LinkedList(Character)); WHILE (i < len) & (chars[i] # 0X) DO IF s.IsEmpty() THEN s.Append(NewCharacter(chars[i])) (* Push character *) ELSE n := s.GetLast(); (* top character *) WITH n: Character DO IF (chars[i] = ']') & (n.c = '[') THEN x := s.RemoveLast(); (* Pop character *) x := NIL ELSE s.Append(NewCharacter(chars[i])) END ELSE RETURN FALSE END (* WITH *) END; INC(i) END; RETURN s.IsEmpty() END CheckBalance; PROCEDURE Do; VAR str: STRING; BEGIN str := "[]";Out.String(str + ":> "); Out.Bool(CheckBalance(str));Out.Ln; str := "[][]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln; str := "[[][]]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln; str := "][";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln; str := "][][";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln; str := "[]][[]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln; END Do; BEGIN Do END BalancedBrackets.  Output: []:> TRUE [][]:> TRUE [[][]]:> TRUE ][:> FALSE ][][:> FALSE []][[]:> FALSE  ## Objeck bundle Default { class Balanced { function : IsBalanced(text : String) ~ Bool { level := 0; each(i : text) { character := text->Get(i); if(character = ']') { if(level = 0) { return false; }; level -= 1; }; if(character = '[') { level += 1; }; }; return level = 0; } function : Main(args : String[]) ~ Nil { ": "->Print(); IsBalanced("")->PrintLine(); "[]: "->Print(); IsBalanced("[]")->PrintLine(); "[][]: "->Print(); IsBalanced("[][]")->PrintLine(); "[[][]]: "->Print(); IsBalanced("[[][]]")->PrintLine(); "][: "->Print(); IsBalanced("][")->PrintLine(); "][][: "->Print(); IsBalanced("][][")->PrintLine(); "[]][[]: "->Print(); IsBalanced("[]][[]")->PrintLine(); } } } : true []: true [][]: true [[][]]: true ][: false ][][: false []][[]: false  ## OCaml let generate_brackets n = let rec aux i acc = if i <= 0 then acc else aux (pred i) ('['::']'::acc) in let brk = aux n [] in List.sort (fun _ _ -> (Random.int 3) - 1) brk let is_balanced brk = let rec aux = function | [], 0 -> true | '['::brk, level -> aux (brk, succ level) | ']'::brk, 0 -> false | ']'::brk, level -> aux (brk, pred level) | _ -> assert false in aux (brk, 0) let () = let n = int_of_string Sys.argv.(1) in Random.self_init(); let brk = generate_brackets n in List.iter print_char brk; Printf.printf " %B\n" (is_balanced brk); ;;   ocaml balanced_brackets.ml 3 []][[] false ocaml balanced_brackets.ml 3 [[]][] true  ## Oforth String method: isBalanced | c | 0 self forEach: c [ c '[' == ifTrue: [ 1+ continue ] c ']' <> ifTrue: [ continue ] 1- dup 0 < ifTrue: [ drop false return ] ] 0 == ; : genBrackets(n) "" #[ "[" "]" 2 rand 2 == ifTrue: [ swap ] rot + swap + ] times(n) ; Output: #[ genBrackets(5) dup print " -->" print isBalanced println ] times(10) [[][[]][]] -->-1 ][][][][][ -->0 ][[][][]][ -->0 ][[]][[]][ -->0 [][][][][] -->-1 ]]][][][[[ -->0 [[[[[]]]]] -->-1 [[[[[]]]]] -->-1 ][][][][][ -->0 ]]][][][[[ -->0  ## ooRexx tests = .array~of("", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]") -- add some randomly generated tests loop i = 1 to 8 tests~append(generateBrackets(i)) end loop test over tests say test":" checkbrackets(test) end ::routine checkBrackets use arg input -- counter of bracket groups. Must be 0 at end to be valid groups = 0 -- loop over all of the characters loop c over input~makearray("") if c == '[' then groups += 1 else if c == ']' then groups -= 1 else return .false -- non-bracket char found -- check for a close occurring before an open if groups < 0 then return .false end -- should be zero at the end return groups == 0 -- generate a string with n pairs of brackets ::routine generateBrackets use arg n answer = .mutablebuffer~new(,2*n) openBracketsNeeded = n unclosedBrackets = 0 loop while answer~length < 2 * n if random(0, 1) & openBracketsNeeded > 0 | unclosedBrackets == 0 then do answer~append('[') openBracketsNeeded -= 1 unclosedBrackets += 1 end else do answer~append(']') unclosedBrackets -= 1 end end return answer~string  Sample output (uses randomly generated groupings, so it should be different on each run): : 1 []: 1 ][: 0 [][]: 1 ][][: 0 [[][]]: 1 []][[]: 0 []: 1 [[]]: 1 [][[]]: 1 [][[][]]: 1 [][][[[]]]: 1 [[]][[][]][]: 1 [][][[][[][]]]: 1 [][[][][[[][]]]]: 1  ## OxygenBasic function CheckBrackets(string s) as bool '======================================= sys co, le=len s byte b at strptr s indexbase 0 for i=0 to <le select b(i) case "[" : co++ case "]" : co-- end select if co<0 then return 0 next if co=0 then return 1 end function 'TEST '==== print CheckBrackets "" '1 print CheckBrackets "[" '0 print CheckBrackets "]" '0 print CheckBrackets "[]" '1 print CheckBrackets "[[]" '0 print CheckBrackets "[]]" '0 print CheckBrackets "[][]"'1 print CheckBrackets "][" '0 ## PARI/GP balanced(s)={ my(n=0,v=Vecsmall(s)); for(i=1,#v, if(v[i]==91, n++ , if(v[i]==93 && n, n--, return(0)) ) ); !n }; rnd(n)=Strchr(vectorsmall(n,i,if(random(2),91,93))) forstep(n=0,10,2,s=rnd(n);print(s"\t"if(balanced(s),"true","false"))) ## Pascal See Delphi ## PascalABC.NET function GenBracketExpr(n: integer): string; begin var a := Arr('[',']')*n; Shuffle(a); Result := a.JoinToString end; function IsBalanced(s: string): boolean; begin Result := True; var st := new Stack<char>; foreach var c in s do if c = '[' then st.Push(c) else if (st.Count > 0) and (st.Peek = '[') then st.Pop else begin Result := False; exit end; end; begin loop 10 do begin var s := GenBracketExpr(Random(2,5)); Println(s, IsBalanced(s)); end; end.  Output: [][] True [[][]] True ]]][[[]][[ False [[[]]] True ]][][[[] False []]][[ False [][]]][[][ False [[][[][]]] True [][][][] True [[]][[[]]] True  ## Perl Idiomatic solution, using a regex that performs subpattern recursion (works with Perl 5.10 and newer): sub generate { my n = shift; my str = '[' x n; substr(str, rand(n + _), 0) = ']' for 1..n; return str; } sub balanced { shift =~ /^ ($(?1)*$)* /x; } for (0..8) { my input = generate(_); print balanced(input) ? " ok:" : "bad:", " 'input'\n"; }  Output:  ok: '' ok: '[]' bad: '[]][' bad: ']][][[' ok: '[[]][[]]' bad: '[[[][]]]][' bad: '][[[]][]][[]' ok: '[[]][[[][[]]]]' bad: ']][]]][[][][[][['  If input strings are allowed to contain unrelated characters, this can be extended to: sub balanced { shift =~ /^ ( [^]++ | $(?1)*$ )* /x; }  Regexp::Common::balanced can give such a regexp too (here via a subroutine call) use Regexp::Common 'RE_balanced'; sub balanced { return shift =~ RE_balanced(-parens=>'[]') }  Alternative implementation, using straightforward depth counting: sub balanced { my depth = 0; for (split //, shift) { if (_ eq '[') { ++depth } elsif (_ eq ']') { return if --depth < 0 } } return !depth }  ## Phix with javascript_semantics function check_brackets(sequence s) integer level = 0 for i=1 to length(s) do switch s[i] case '[': level += 1 case ']': level -= 1 if level<0 then return false end if end switch end for return (level=0) end function sequence s constant ok = {"not ok","ok"} for i=1 to 10 do for j=1 to 2 do s = shuffle(join(repeat("[]",i-1),"")) printf(1,"%s %s\n",{s,ok[check_brackets(s)+1]}) end for end for  Output:  ok ok [] ok ][ not ok [][] ok ][][ not ok []][][ not ok ][][[] not ok ][[][]][ not ok [][[][]] ok []]][[[]][ not ok ][]][[[]][ not ok ][[]]]][[][[ not ok [][[]][[]][] ok []][][]]][[[[] not ok [[][][]][][[]] ok [[][]][][[]][[]] ok ][][[[[][]]][]][ not ok [[[[]]][][[[][]]]] ok [[[]]][[[[][]]][]] ok  ## Phixmonti "[[]][]" 0 var acc len for get dup '[' == if acc 1 + var acc endif ']' == if acc 1 - var acc endif acc 0 < if exitfor endif endfor print acc 0 < if " is NOT ok" else " is OK" endif print ## PHP The sample is given as unix shell script, you need to have php-cli (or what your package manager calls it) installed. #!/usr/bin/php <?php # brackets generator function bgenerate (n) { if (n==0) return ''; s = str_repeat('[', n) . str_repeat(']', n); return str_shuffle(s); } function printbool(b) {return (b) ? 'OK' : 'NOT OK';} function isbalanced(s) { bal = 0; for (i=0; i < strlen(s); i++) { ch = substr(s, i, 1); if (ch == '[') { bal++; } else { bal--; } if (bal < 0) return false; } return (bal == 0); } # test parameters are N (see spec) tests = array(0, 2,2,2, 3,3,3, 4,4,4,4); foreach (tests as v) { s = bgenerate(v); printf("%s\t%s%s", s, printbool(isbalanced(s)), PHP_EOL); }  Sample run:  OK [][] OK [[]] OK []][ NOT OK ][][[] NOT OK [][[]] OK ][[[]] NOT OK ]][[][][ NOT OK []][][[] NOT OK ][]]][[[ NOT OK [[[][]]] OK  ## Picat ### Foreach loop go1 ?=> tests(Tests), member(Test,Tests), printf("%s: ", Test), ( balanced_brackets(Test) -> println("OK") ; println("NOT OK") ), fail, nl. go1 => true. % Check if a string of [] is balanced balanced_brackets(B) => C = 0, foreach(I in 1..B.length, C >= 0) C:= C + cond(B[I] = '[', 1, -1) end, C == 0. tests(["","[]", "[][]", "[[][]]", "][", "][][", "[]][[]", "[][][][][][][][][][]", "[[[[[[[]]]]]]]", "[[[[[[[]]]]]]", "[][[]][]","[[][]][]", "[][][[]][]"]). Output: : OK []: OK [][]: OK [[][]]: OK ][: NOT OK ][][: NOT OK []][[]: NOT OK [][][][][][][][][][]: OK [[[[[[[]]]]]]]: OK [[[[[[[]]]]]]: NOT OK [][[]][]: OK [[][]][]: OK [][][[]][]: OK ### DCG Here is an implementation using DCG (Definite Clause Grammars). go_dcg ?=> tests(Tests), foreach(Test in Tests) printf("%s: ", Test), if balanced(Test,[]) then println("OK") else println("NOT OK") end end, nl. go_dcg => true. balanced --> "". balanced --> "[", balanced, "]", balanced. ## PicoLisp (load "@lib/simul.l") # For 'shuffle' (de generateBrackets (N) (shuffle (make (do N (link "[" "]")))) ) (de checkBrackets (S) (let N 0 (for C S (if (= C "[") (inc 'N) (if2 (= C "]") (=0 N) (off N) (dec 'N) ) ) ) (=0 N) ) ) (for N 10 (prinl (if (checkBrackets (prin (generateBrackets N))) " OK" "not OK")) ) Output: [] OK [[]] OK ]]][[[not OK [[[][]]] OK [][][[[]]] OK []][[[][[]]]not OK [[[]]][][][][] OK ]][][[[[]][]]][[not OK []][][[[][[]]][]][not OK [[[][]]]]][][[]]][[[not OK ## PL/I *process m or(!) s attributes source; cb: Proc Options(main); /* PL/I program to check for balanced brackets [] ******************** * 07.12.2013 Walter Pachl translated from REXX Version 2 *********************************************************************/ Dcl v Char(20) Var; Dcl (i,j) Bin Fixed(31); Dcl r Bin Float(53); Call testbal(''); /* first some user written tests */ Call testbal('[][][][[]]'); Call testbal('[][][][[]]]['); Call testbal('['); Call testbal(']'); Call testbal('[]'); Call testbal(']['); Call testbal('][]['); Call testbal('[[]]'); Call testbal('[[[[[[[]]]]]]]'); Call testbal('[[[[[]]]][]'); Call testbal('[][]'); Call testbal('[]][[]'); Call testbal(']]][[[[]'); Call testbal('[[a]][b]'); Put Edit(' ')(Skip,a); r=random(12345); /* then some generated ones */ Do i=1 To 10; v=''; Do j=1 To 10; r=random(); If r>0.5 Then v=v!!']'; Else v=v!!'['; End; Call testbal(v); End; Return; testbal: Proc(s); /* test the given string and show result */ Dcl s Char(*); Dcl yesno(0:1) Char(20) Var Init('unbalanced',' balanced'); Put Edit(yesno(checkbal(s)),''''!!s!!'''')(Skip,a,x(1),a); End; checkBal: proc(s) Returns(Bin Fixed(31)); /*check for balanced brackets [] */ Dcl s Char(*); Dcl nest Bin Fixed(31) Init(0); Dcl i Bin Fixed(31); Do i=1 To length(s); Select(substr(s,i,1)); When('[') nest+=1; When(']') Do; If nest=0 Then return(0); nest-=1; End; Otherwise; End; End; Return(nest=0); End; End; Output:  balanced '' balanced '[][][][[]]' unbalanced '[][][][[]]][' unbalanced '[' unbalanced ']' balanced '[]' unbalanced '][' unbalanced '][][' balanced '[[]]' balanced '[[[[[[[]]]]]]]' unbalanced '[[[[[]]]][]' balanced '[][]' unbalanced '[]][[]' unbalanced ']]][[[[]' balanced '[[a]][b]' unbalanced '][[][[[[[]' balanced '[[]][[[]]]' unbalanced ']][[[[][[[' unbalanced '[[[][][[]]' unbalanced ']]][[[[[]]' balanced '[[[][][]]]' unbalanced '[][][][[][' unbalanced '[[]]]][[][' unbalanced '[]][]]][[]' unbalanced '][[][[[[[]' ## PowerShell Works with: PowerShell version 2 function Get-BalanceStatus ( String ) { Open = 0 ForEach ( Character in [char[]]String ) { switch ( Character ) { "[" { Open++ } "]" { Open-- } default { Open = -1 } } # If Open drops below zero (close before open or non-allowed character) # Exit loop If ( Open -lt 0 ) { Break } } Status = ( "NOT OK", "OK" )[( Open -eq 0 )] return Status }  # Test Strings = @( "" ) Strings += 1..5 | ForEach { ( [char[]]("[]" * _) | Get-Random -Count ( _ * 2 ) ) -join "" } ForEach ( String in Strings ) { String.PadRight( 12, " " ) + (Get-BalanceStatus String) } Output:  OK [] OK ]][[ NOT OK ]][][[ NOT OK [[[][]]] OK ][[[]][][] NOT OK  ### PowerShell (Regex Version) function Test-BalancedBracket { <# .SYNOPSIS Tests a string for balanced brackets. .DESCRIPTION Tests a string for balanced brackets. ("<>", "[]", "{}" or "()") .EXAMPLE Test-BalancedBracket -Bracket Brace -String '{abc(def[0]).xyz}' Test a string for balanced braces. .EXAMPLE Test-BalancedBracket -Bracket Curly -String '{abc(def[0]).xyz}' Test a string for balanced curly braces. .EXAMPLE Test-BalancedBracket -Bracket Curly -String ([System.IO.File]::ReadAllText('.\Foo.ps1')) Test a file for balanced curly braces. .LINK http://go.microsoft.com/fwlink/?LinkId=133231 #> [CmdletBinding()] [OutputType([bool])] Param ( [Parameter(Mandatory=true)] [ValidateSet("Angle", "Brace", "Curly", "Paren")] [string] Bracket, [Parameter(Mandatory=true)] [AllowEmptyString()] [string] String ) notFound = -1 brackets = @{ Angle = @{Left="<"; Right=">"; Regex="^[^<>]*(?>(?>(?'pair'\<)[^<>]*)+(?>(?'-pair'\>)[^<>]*)+)+(?(pair)(?!))"} Brace = @{Left="["; Right="]"; Regex="^[^]*(?>(?>(?'pair'$)[^\[$]*)+(?>(?'-pair'\])[^]*)+)+(?(pair)(?!))"} Curly = @{Left="{"; Right="}"; Regex="^[^{}]*(?>(?>(?'pair'\{)[^{}]*)+(?>(?'-pair'\})[^{}]*)+)+(?(pair)(?!))"} Paren = @{Left="("; Right=")"; Regex="^[^()]*(?>(?>(?'pair'\()[^()]*)+(?>(?'-pair'$$)[^()]*)+)+(?(pair)(?!))$"}
}

if ($String.IndexOf($brackets.$Bracket.Left) -eq$notFound -and
$String.IndexOf($brackets.$Bracket.Right) -eq$notFound -or  $String -eq [String]::Empty) { return$true
}

$String -match$brackets.$Bracket.Regex } '', '[]', '][', '[][]', '][][', '[[][]]', '[]][[]' | ForEach-Object { if ($_ -eq "") { $s = "(Empty)" } else {$s = $_ } "{0}: {1}" -f$s.PadRight(8), "$(if (Test-BalancedBracket Brace$s) {'Is balanced.'} else {'Is not balanced.'})"
}
Output:
(Empty) : Is balanced.
[]      : Is balanced.
][      : Is not balanced.
[][]    : Is balanced.
][][    : Is not balanced.
[[][]]  : Is balanced.
[]][[]  : Is not balanced.


## Prolog

DCG are very usefull for this kind of exercice !

rosetta_brackets :-
test_brackets([]),
test_brackets(['[',']']),
test_brackets(['[',']','[',']']),
test_brackets(['[','[',']','[',']',']']),
test_brackets([']','[']),
test_brackets([']','[',']','[']),
test_brackets(['[',']',']','[','[',']']).

balanced_brackets :-
gen_bracket(2,  B1, []), test_brackets(B1),
gen_bracket(4,  B2, []), test_brackets(B2),
gen_bracket(4,  B3, []), test_brackets(B3),
gen_bracket(6,  B4, []), test_brackets(B4),
gen_bracket(6,  B5, []), test_brackets(B5),
gen_bracket(8,  B6, []), test_brackets(B6),
gen_bracket(8,  B7, []), test_brackets(B7),
gen_bracket(10, B8, []), test_brackets(B8),
gen_bracket(10, B9, []), test_brackets(B9).

test_brackets(Goal) :-
(   Goal = [] -> write('(empty)'); maplist(write, Goal)),
(   balanced_brackets(Goal, []) ->
writeln(' succeed')
;
writeln(' failed')
).

% grammar of balanced brackets
balanced_brackets --> [].

balanced_brackets -->
['['],
balanced_brackets,
[']'].

balanced_brackets -->
['[',']'],
balanced_brackets.

% generator of random brackets
gen_bracket(0) --> [].

gen_bracket(N) -->
{N1 is N - 1,
R is random(2)},
bracket(R),
gen_bracket(N1).

bracket(0) --> ['['].
bracket(1) --> [']'].

Sample output :

 ?- balanced_brackets.
[[ failed
[[][ failed
[[]] succeed
[[][]] succeed
[][[][ failed
][]][[[] failed
[[[[]][] failed
[[[[[][[]] failed
[]][[[][]] failed
true .


Test with Rosetta examples :

 ?- rosetta_brackets.
(empty) succeed
[] succeed
[][] succeed
[[][]] succeed
][ failed
][][ failed
[]][[] failed
true.


## PureBasic

Procedure.s Generate(N)
For i=1 To N
sample$+"[]" Next For i=Len(sample$)-1 To 2 Step -1
r=Random(i-1)+1
If r<>i
a.c=PeekC(@sample$+r*SizeOf(Character)) b.c=PeekC(@sample$+i*SizeOf(Character))
PokeC(@sample$+r*SizeOf(Character), b) PokeC(@sample$+i*SizeOf(Character), a)
EndIf
Next
ProcedureReturn sample$EndProcedure Procedure Balanced(String$)
Protected *p.Character, cnt
*p=@String$While *p\c If *p\c='[' cnt+1 ElseIf *p\c=']' cnt-1 If cnt<0: Break: EndIf EndIf *p+SizeOf(Character) Wend If cnt=0 ProcedureReturn #True EndIf EndProcedure ;- Test code OpenConsole() For i=1 To 5 TestString$ = Generate(i)
Print(TestString$) If Balanced(TestString$)
PrintN(" is balanced.")
Else
PrintN(" is not balanced")
EndIf
Next

Output sample

 [] is balanced.
[[]] is balanced.
[[[]]] is balanced.
[][]]][[ is not balanced
[][][][]][ is not balanced


## Python

### Procedural

>>> def gen(N):
...     txt = ['[', ']'] * N
...     random.shuffle( txt )
...     return ''.join(txt)
...
>>> def balanced(txt):
...     braced = 0
...     for ch in txt:
...         if ch == '[': braced += 1
...         if ch == ']':
...             braced -= 1
...             if braced < 0: return False
...     return braced == 0
...
>>> for txt in (gen(N) for N in range(10)):
...     print ("%-22r is%s balanced" % (txt, '' if balanced(txt) else ' not'))
...
''                     is balanced
'[]'                   is balanced
'[][]'                 is balanced
'][[[]]'               is not balanced
'[]][[][]'             is not balanced
'[][[][]]]['           is not balanced
'][]][][[]][['         is not balanced
'[[]]]]][]][[[['       is not balanced
'[[[[]][]]][[][]]'     is balanced
'][[][[]]][]]][[[[]'   is not balanced

### Functional

Works with: Python version 3.2

Rather than explicitly track the count, we can just write the per-element test and use stdlib functions to turn it into a whole-sequence test. It's straightforwardly declarative, and hard to get wrong, but whether it's actually easier to understand depends on how familiar the reader is with thinking in itertools style.

>>> from itertools import accumulate
>>> from random import shuffle
>>> def gen(n):
...     txt = list('[]' * n)
...     shuffle(txt)
...     return ''.join(txt)
...
>>> def balanced(txt):
...     brackets = ({'[': 1, ']': -1}.get(ch, 0) for ch in txt)
...     return all(x>=0 for x in accumulate(brackets))
...
>>> for txt in (gen(N) for N in range(10)):
...     print ("%-22r is%s balanced" % (txt, '' if balanced(txt) else ' not'))
...
''                     is balanced
']['                   is not balanced
'[]]['                 is not balanced
']][[[]'               is not balanced
'][[][][]'             is not balanced
'[[[][][]]]'           is balanced
'][[[][][]][]'         is not balanced
'][]][][[]][[]['       is not balanced
'][[]]][][[]][[[]'     is not balanced
'][[][[]]]][[[]][]['   is not balanced

### Array Programming

Library: NumPy

The numpy library gives us a way to write just the elementwise tests and automatically turn them into whole-sequence tests, although it can be a bit clumsy to use for character rather than numeric operations. The simplicity of the final expression probably doesn't make up for all that extra clumsiness in this case.

>>> import numpy as np
>>> from random import shuffle
>>> def gen(n):
...     txt = list('[]' * n)
...     shuffle(txt)
...     return ''.join(txt)
...
>>> m = np.array([{'[': 1, ']': -1}.get(chr(c), 0) for c in range(128)])
>>> def balanced(txt):
...     a = np.array(txt, 'c').view(np.uint8)
...     return np.all(m[a].cumsum() >= 0)
...
>>> for txt in (gen(N) for N in range(10)):
...     print ("%-22r is%s balanced" % (txt, '' if balanced(txt) else ' not'))
...
''                     is balanced
']['                   is not balanced
'[[]]'                 is balanced
'[]][]['               is not balanced
']][]][[['             is not balanced
'[[]][[][]]'           is balanced
'[][[]][[]]]['         is not balanced
'[][[[]][[]]][]'       is balanced
'[[][][[]]][[[]]]'     is balanced
'][]][][[]][]][][[['   is not balanced

## Qi

(define balanced-brackets-0
[]      0   -> true
[]      _   -> false
[#$|R] Sum -> (balanced-brackets-0 R (+ Sum 1)) _ 0 -> false [_ |R] Sum -> (balanced-brackets-0 R (- Sum 1))) (define balanced-brackets "" -> true S -> (balanced-brackets-0 (explode (INTERN S)) 0)) (balanced-brackets "") (balanced-brackets "[]") (balanced-brackets "[][]") (balanced-brackets "[[][]]") (balanced-brackets "][") (balanced-brackets "][][") (balanced-brackets "[]][[]") ## Quackery  [ char [ over of swap char ] swap of join shuffle ] is bracket ( n -->  ) [ 0 swap witheach [ char [ = iff 1 else -1 + dup 0 < if conclude ] 0 = ] is balanced (  --> b ) 10 times [ 20 i 2 * - times sp i bracket dup echo say " is " balanced not if [ say "un" ] say "balanced." cr ] Output: Full disclosure: it took quite a few attempts to randomly achieve a pleasing distribution of balanced and unbalanced strings.  [[][]][][][[]][][] is balanced. [][]][][[]]][][[ is unbalanced. []][][]][[][[] is unbalanced. [][[[[][]]]] is balanced. ]][[][][][ is unbalanced. ]][[][][ is unbalanced. [][][] is balanced. [][] is balanced. ][ is unbalanced. is balanced. ## R balanced <- function(str){ str <- strsplit(str, "")[[1]] str <- ifelse(str=='[', 1, -1) all(cumsum(str) >= 0) && sum(str) == 0 } Alternately, using perl 5.10-compatible regexps, balanced <- function(str) { regexpr('^(\\[(?1)*\$)*$', str, perl=TRUE) > -1 } To generate some some examples: rand.parens <- function(n) paste(sample(c("[","]"),2*n,replace=T),collapse="") as.data.frame(within(list(), { parens <- replicate(10, rand.parens(sample.int(10,size=1))) balanced <- sapply(parens, balanced) })) Output:  balanced parens 1 FALSE ][][ 2 FALSE [][[]]][[]][]]][[[ 3 FALSE ][[][][]][][[] 4 FALSE ][][][][][][][ 5 TRUE [[[][]]][[[][][]]] 6 TRUE [] 7 FALSE ]][[][[] 8 FALSE []]]][[[]][[[] 9 TRUE [[[[][[][]]]]] 10 TRUE [] ## Racket #lang racket (define (generate n) (list->string (shuffle (append* (make-list n '(#$#$)))))) (define (balanced? str) (let loop ([l (string->list str)] [n 0]) (or (null? l) (if (eq? #$(car l)) (loop (cdr l) (add1 n)) (and (> n 0) (loop (cdr l) (sub1 n))))))) (define (try n) (define s (generate n)) (printf "~a => ~a\n" s (if (balanced? s) "OK" "NOT OK"))) (for ([n 10]) (try n)) ## Raku (formerly Perl 6) There's More Than One Way To Do It. ### Depth counter Works with: Rakudo version 2015.12 sub balanced(s) { my l = 0; for s.comb { when "]" { --l; return False if l < 0; } when "[" { ++l; } } return l == 0; } my n = prompt "Number of brackets"; my s = (<[ ]> xx n).flat.pick(*).join; say "s {balanced(s) ?? "is" !! "is not"} well-balanced" ### FP oriented Here's a more idiomatic solution using a hyperoperator to compare all the characters to a backslash (which is between the brackets in ASCII), a triangle reduction to return the running sum, a given to make that list the topic, and then a topicalized junction and a topicalized subscript to test the criteria for balance. sub balanced(s) { .none < 0 and .[*-1] == 0 given ([\+] '\\' «leg« s.comb).cache; } my n = prompt "Number of bracket pairs: "; my s = <[ ]>.roll(n*2).join; say "s { balanced(s) ?? "is" !! "is not" } well-balanced" ### String munging Of course, a Perl 5 programmer might just remove as many inner balanced pairs as possible and then see what's left. Works with: Rakudo version 2015.12 sub balanced(_ is copy) { Nil while s:g/'[]'//; _ eq ''; } my n = prompt "Number of bracket pairs: "; my s = <[ ]>.roll(n*2).join; say "s is", ' not' x not balanced(s), " well-balanced"; ### Parsing with a grammar Works with: Rakudo version 2015.12 grammar BalBrack { token TOP { '[' <TOP>* ']' } } my n = prompt "Number of bracket pairs: "; my s = ('[' xx n, ']' xx n).flat.pick(*).join; say "s { BalBrack.parse(s) ?? "is" !! "is not" } well-balanced"; ## Red ; Functional code balanced-brackets: [#"[" any balanced-brackets #"]"] rule: [any balanced-brackets end] balanced?: func [str][parse str rule] ; Tests tests: [ good: ["" "[]" "[][]" "[[]]" "[[][]]" "[[[[[]]][][[]]]]"] bad: ["[" "]" "][" "[[]" "[]]" "[]][[]" "[[[[[[]]]]]]]"] ] foreach str tests/good [ if not balanced? str [print [mold str "failed!"]] ] foreach str tests/bad [ if balanced? str [print [mold str "failed!"]] ] repeat i 10 [ str: random copy/part "[][][][][][][][][][]" i * 2 print [mold str "is" either balanced? str ["balanced"]["unbalanced"]] ] ## REXX ### with 40 examples /*REXX program checks for balanced brackets [ ] ─── some fixed, others random.*/ parse arg seed . /*obtain optional argument from the CL.*/ if datatype(seed,'W') then call random ,,seed /*if specified, then use as RANDOM seed*/ @.=0; yesNo.0= right('not OK', 50) /*for bad expressions, indent 50 spaces*/ yesNo.1= 'OK' /* [↓] the 14 "fixed" ][ expressions*/ q= ; call checkBal q; say yesNo.result '«null»' q= '[][][][[]]' ; call checkBal q; say yesNo.result q q= '[][][][[]]][' ; call checkBal q; say yesNo.result q q= '[' ; call checkBal q; say yesNo.result q q= ']' ; call checkBal q; say yesNo.result q q= '[]' ; call checkBal q; say yesNo.result q q= '][' ; call checkBal q; say yesNo.result q q= '][][' ; call checkBal q; say yesNo.result q q= '[[]]' ; call checkBal q; say yesNo.result q q= '[[[[[[[]]]]]]]' ; call checkBal q; say yesNo.result q q= '[[[[[]]]][]' ; call checkBal q; say yesNo.result q q= '[][]' ; call checkBal q; say yesNo.result q q= '[]][[]' ; call checkBal q; say yesNo.result q q= ']]][[[[]' ; call checkBal q; say yesNo.result q #=0 /*# additional random expressions*/ do j=1 until #==26 /*gen 26 unique bracket strings. */ q=translate( rand( random(1,10) ), '][', 10) /*generate random bracket string.*/ call checkBal q; if result==-1 then iterate /*skip if duplicated expression. */ say yesNo.result q /*display the result to console. */ #=#+1 /*bump the expression counter. */ end /*j*/ /* [↑] generate 26 random "Q" strings.*/ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ ?: ?=random(0,1); return ? || \? /*REXX BIF*/ rand: =copies(?()?(),arg(1)); _=random(2,length()); return left(,_-1)substr(,_) /*──────────────────────────────────────────────────────────────────────────────────────*/ checkBal: procedure expose @.; parse arg y /*obtain the "bracket" expression. */ if @.y then return -1 /*Done this expression before? Skip it*/ @.y=1 /*indicate expression was processed. */ !=0; do j=1 for length(y); _=substr(y,j,1) /*get a character.*/ if _=='[' then !=!+1 /*bump the nest #.*/ else do; !=!-1; if !<0 then return 0; end end /*j*/ return !==0 /* [↑] "!" is the nested ][ counter.*/ output using the (some internal, others random) expressions: OK «null» OK [][][][[]] not OK [][][][[]]][ not OK [ not OK ] OK [] not OK ][ not OK ][][ OK [[]] OK [[[[[[[]]]]]]] not OK [[[[[]]]][] OK [][] not OK []][[] not OK ]]][[[[] not OK []][ OK [][][][][][][][][][][][] not OK []][[]][[]][[]][[]][[]][[]][[]][ not OK []][[]][[]][[]][[]][[]][[]][[]][[]][[]][ not OK ][[]][[] not OK ][][][][][][][][][][][][][][][][ not OK ][[]][[]][[] not OK []][[]][ not OK ][][][][][][ OK [][][][][][] OK [][][][][][][][][][][][][][] OK [][][][][][][][][][][][][][][][][][][][] not OK []][[]][[]][[]][ not OK ][[] not OK []][[]][[]][[]][[]][[]][[]][ not OK ][[]][[]][[]][[]][[] not OK []][[]][[]][[]][[]][[]][ OK [][][][][][][][][][][][][][][][] not OK ][[]][[]][[]][[]][[]][[]][[]][[] not OK ][][][][][][][][][][][][ not OK ][[]][[]][[]][[]][[]][[]][[] not OK ][[]][[]][[]][[]][[]][[]][[]][[]][[]][[] not OK ][][][][][][][][][][][][][][][][][][ OK [][][][][][][][] not OK ][[]][[]][[]][[] not OK ][][][][][][][][][][][][][][][][][][][][  ### with examples + 30 permutations /*REXX program to check for balanced brackets [] ********************** * test strings and random string generation copied from Version 1 * the rest restructured (shortened) to some extent * and output made reproducible (random with a seed) * 10.07.2012 Walter Pachl **********************************************************************/ yesno.0 = 'unbalanced' yesno.1 = ' balanced' done.=0 /* memory what's been done */ n=0 /* number of tests */ Call testbal '[][][][[]]' /* first some user written tests */ Call testbal '[][][][[]]][' Call testbal '[' Call testbal ']' Call testbal '[]' Call testbal '][' Call testbal '][][' Call testbal '[[]]' Call testbal '[[[[[[[]]]]]]]' Call testbal '[[[[[]]]][]' Call testbal '[][]' Call testbal '[]][[]' Call testbal ']]][[[[]' Call testbal ']' Call testbal '[' /* then some random generated ones */ Call random 1,2,12345 /* call random with a seed */ /* makes test reproducible */ do Until n=30 /* up to 30 tests */ s=rand(random(1,8)) /* a 01 etc. string of length 4-32 */ q=translate(s,'[]',01) /* turn digits into brackets */ if done.q then /* string was already here */ iterate /* don't test again */ call testbal q /* test balance */ End exit testbal: /* test the given string and show result */ n=n+1 /* number of tests */ Parse Arg q /* get string to be tested */ done.q=1 /* mark as done */ call checkBal q /* test balance */ lq=format(length(q),2) say right(n,2) lq yesno.result q/* show result and string */ Return /*-----------------------------------PAND subroutine-----------------*/ pand: p=random(0,1); return p || \p /*-----------------------------------RAND subroutine-----------------*/ rand: pp=pand(); pp=pand()pp; pp=copies(pp,arg(1)) i=random(2,length(pp)); pp=left(pp,i-1)substr(pp,i) return pp checkBal: procedure /*check for balanced brackets () */ Parse arg y nest=0; do While y<>'' Parse Var y c +1 y /*pick off one character at a time */ if c='[' then /* opening bracket */ nest=nest+1 /* increment nesting */ else do /* closing bracket */ if nest=0 then /* not allowed */ return 0; /* no success */ nest=nest-1 /* decrement nesting */ end end return nest=0 /* nest=0 -> balanced */ Output:  1 10 balanced [][][][[]] 2 12 unbalanced [][][][[]]][ 3 1 unbalanced [ 4 1 unbalanced ] 5 2 balanced [] 6 2 unbalanced ][ 7 4 unbalanced ][][ 8 4 balanced [[]] 9 14 balanced [[[[[[[]]]]]]] 10 11 unbalanced [[[[[]]]][] 11 4 balanced [][] 12 6 unbalanced []][[] 13 8 unbalanced ]]][[[[] 14 1 unbalanced ] 15 1 unbalanced [ 16 20 unbalanced ][][][][][][][][][][ 17 24 unbalanced ][][][][][][][][][][][][ 18 20 unbalanced []][[]][[]][[]][[]][ 19 20 balanced [][][][][][][][][][] 20 24 balanced [][][][][][][][][][][][] 21 24 unbalanced []][[]][[]][[]][[]][[]][ 22 12 balanced [][][][][][] 23 32 balanced [][][][][][][][][][][][][][][][] 24 8 unbalanced []][[]][ 25 32 unbalanced ][[]][[]][[]][[]][[]][[]][[]][[] 26 4 unbalanced ][[] 27 28 unbalanced ][[]][[]][[]][[]][[]][[]][[] 28 32 unbalanced ][][][][][][][][][][][][][][][][ 29 28 unbalanced []][[]][[]][[]][[]][[]][[]][ 30 4 unbalanced []][  ### with over 125,000 permutations This REXX version generates over one hundred thousand unique permutations of strings that contain an equal amount of left [ and right ] brackets. All possible strings of twenty or less characters (legal bracket expressions) are generated. This eliminates the possibility of missing a particular character string permutation that may not be generated via a random generator. Use is made of the countstr function (which is a BIF for newer REXX interpreters), but a RYO version is included here for older REXXes that don't contain that BIF (Built In Function). Naturally, each of the one hundred thousand character strings aren't displayed (for balanced/not-balanced), but a count is displayed, as anyone can generate the same strings in other languages and compare results. /*REXX program checks for around 125,000 generated balanced brackets expressions [ ] */ bals=0 #=0; do j=1 until L>20 /*generate lots of bracket permutations*/ q=translate( strip( x2b( d2x(j) ), 'L', 0), "][", 01) /*convert ──► ][*/ L=length(q) if countStr(']', q) \== countstr('[', q) then iterate /*not compliant?*/ #=#+1 /*bump legal Q's*/ !=0; do k=1 for L; parse var q ? 2 q if ?=='[' then !=!+1 else do; !=!-1; if !<0 then iterate j; end end /*k*/ if !==0 then bals=bals+1 end /*j*/ /*done all 20─character possibilities? */ say # " expressions were checked, " bals ' were balanced, ' , #-bals " were unbalanced." exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ countStr: procedure; parse arg n,h,s; if s=='' then s=1; w=length(n) do r=0 until _==0; _=pos(n,h,s); s=_+w; end; return r output when using the default input: 125476 expressions were checked, 23713 were balanced, 101763 were unbalanced.  ## Ring nr = 0 while nr < 10 nr += 1 test=generate(random(9)+1) see "bracket string " + test + " is " + valid(test) + nl end func generate n l = 0 r = 0 output = "" while l<n and r<n switch random(2) on 1 l+=1 output+="[" on 2 r+=1 output+="]" off end if l=n output+=copy("]",n-r) else output+=copy("]",n-l) ok return output func valid q count = 0 if len(q)=0 return "ok." ok for x=1 to len(q) if substr(q,x,1)="[" count+=1 else count-=1 ok if count<0 return "not ok." ok next return "ok." Output: bracket string ]][[][[[[]]] is not ok. bracket string [[[]]] is ok. bracket string ]][[[[[[[]]]]] is not ok. bracket string [][[[][[][]]][]] is ok. bracket string [[]][][[][[][[]]]] is ok. bracket string ]] is not ok. bracket string [[[]]] is ok. bracket string [][[]] is ok. bracket string [[]] is ok. bracket string ]]]][]]]]]]]]] is not ok.  ## RPL Works with: Halcyon Calc version 4.2.7 ≪ 1 OVER SIZE WHILE DUP2 * 0 > REPEAT 3 PICK OVER DUP SUB IF "[]" SWAP POS THEN LAST 2 * 3 - ROT + SWAP END 1 - END DROP 1 SAME "" "Not " IFTE "OK" + ≫ 'BALBKT' STO ≪ { "" "[]" "[][]" "[[][]]" "][" "][][" "[]][[]" } → ts ≪ 1 ts SIZE FOR j ts j GET BALBKT " → " SWAP + + NEXT ≫ ≫ 'TASK' STO  Output: " → OK" "[] → OK" "[][] → OK" "[[][]] → OK" "][ → Not OK" "][][ → Not OK" "[]][[] → Not OK"  ## Ruby Translation of: D Works with: Ruby version 1.9 re = /\A # beginning of string (?<bb> # begin capture group <bb> \[ # literal [ \g<bb>* # zero or more <bb>$ # literal ] )* # end group, zero or more such groups \z/x # end of string 10.times do |i| s = (%w{[ ]} * i).shuffle.join puts (s =~ re ? " OK: " : "bad: ") + s end ["[[]", "[]]", "a[ letters[-1] ].xyz[0]"].each do |s| t = s.gsub(/[^]/, "") puts (t =~ re ? " OK: " : "bad: ") + s end One output:  OK: OK: [] bad: []][ OK: [[][]] bad: []]][][[ bad: ][]][[[[]] bad: []]][[]][[[] bad: ][[][]][][[]][ OK: [][[][[[]][]][]] bad: []][][]][[[[[][]]] bad: [[] bad: []] OK: a[ letters[-1] ].xyz[0]  ## Run BASIC dim brk$(10)
brk$(1) = "[[[][]]]" brk$(2)  = "[[[]][[[][[][]]]]]"
brk$(3) = "][][]][[" brk$(4)  = "[][][]"
brk$(5) = "[][]][]][[]]][[[" brk$(6)  = "]][[[[]]]][]]][[[["
brk$(7) = "[[][[[]]][]]" brk$(8)  = "[]][][][[[]]"
brk$(9) = "][]][[" brk$(10) = "[]][][][[]"

for i = 0 to 10
b$= brk$(i)
while instr(b$,"[]") <> 0 x = instr(b$,"[]")
if x > 0 then b$= left$(b$,x - 1) + mid$(b$,x + 2) wend if trim$(b$) = "" then print " OK "; else print "Not OK "; print brk$(i)
next i

One output:

    OK
OK [[[][]]]
OK [[[]][[[][[][]]]]]
Not OK ][][]][[
OK [][][]
Not OK [][]][]][[]]][[[
Not OK ]][[[[]]]][]]][[[[
OK [[][[[]]][]]
Not OK []][][][[[]]
Not OK ][]][[
Not OK []][][][[]


## Rust

Library: rand
extern crate rand;

trait Balanced {
/// Returns true if the brackets are balanced
fn is_balanced(&self) -> bool;
}

impl<'a> Balanced for str {
fn is_balanced(&self) -> bool {
let mut count = 0;

for bracket in self.chars() {
let change = match bracket {
'[' => 1,
']' => -1,
_ => panic!("Strings should only contain brackets")
};

count += change;
if count < 0 { return false; }
}

count == 0
}
}

/// Generates random brackets
fn generate_brackets(num: usize) -> String {
use rand::random;

(0..num).map(|_| if random() { '[' } else { ']' }).collect()
}

fn main() {
for i in (0..10) {
let brackets = generate_brackets(i);

println!("{}    {}", brackets, brackets.is_balanced())
}
}

Output:

    true
[    false
]]    false
][]    false
[[[[    false
]][[[    false
[][[]]    true
[]]][[]    false
[[[[[[][    false
][[[[][]]    false


## Scala

If you are new to Scala you might want to jump to Version 2.

### Scala Version 1

Works with: Scala version 2.9.1
import scala.collection.mutable.ListBuffer
import scala.util.Random

object BalancedBrackets extends App {

val random = new Random()
def generateRandom: List[String] = {
import scala.util.Random._
val shuffleIt: Int => String = i => shuffle(("["*i+"]"*i).toList).foldLeft("")(_+_)
(1 to 20).map(i=>(random.nextDouble*100).toInt).filter(_>2).map(shuffleIt(_)).toList
}

def generate(n: Int): List[String] = {
val base = "["*n+"]"*n
var lb = ListBuffer[String]()
base.permutations.foreach(s=>lb+=s)
lb.toList.sorted
}

def checkBalance(brackets: String):Boolean = {
def balI(brackets: String, depth: Int):Boolean = {
if (brackets == "") depth == 0
else brackets(0) match {
case '[' => ((brackets.size > 1) && balI(brackets.substring(1), depth + 1))
case ']' => (depth > 0) && ((brackets.size == 1) || balI(brackets.substring(1), depth -1))
case _   => false
}
}
balI(brackets, 0)
}

println("arbitrary random order:")
generateRandom.map(s=>Pair(s,checkBalance(s))).foreach(p=>println((if(p._2) "balanced:   " else "unbalanced: ")+p._1))
println("\n"+"check all permutations of given length:")
(1 to 5).map(generate(_)).flatten.map(s=>Pair(s,checkBalance(s))).foreach(p=>println((if(p._2) "balanced:   " else "unbalanced: ")+p._1))
}
arbitrary random order:
unbalanced: ][[[]][][[]]][][]]]][[]]]][[][]][[]]][[][]]][[[]][[][[]]][[]]]]][][]]][[][]]]][[][[][[][[][][][[][]][][[][[[][]]][[]]]][][]][[][]]][[][][[[][[[][[[[[][[]][[[[[[[][]][[]][]]][[[]][[][[]][][]]
unbalanced: [[][][[[[][]]][][[][]][][[[]]]][]][]][]][][]][[]]]][[][[[]][][[][[[[[][[][][[]]][]]]
unbalanced: [[]][][][[[[][][][[[[[[[][[[]]][[[[]]][[]]]][]][]]]][]][]]][]]]]][][][[]]][]][]][]]][[]][][]][]][[[[[[][[[[][[[]][[][[[][[]][]][[[][[][]]][]]][[[[][][[[]][][][[[[]]][]]][][]]]][][][][]][
unbalanced: []]][]][[]]][]][]]]][]]]][]]]][][[][[][[[[][][[[[[[[[][[[]
unbalanced: [][[[]]][]]][[]]]]]][[[[[][][][][]]][[]]]]]][][[[]][[[[][][[][]][]][[[[][[[[[[[[][]]]]]][]][][[][]]][[
unbalanced: []][[][[]]
unbalanced: []][[[[][]][][[]][][[[]]]][[]][[[[[][][[[[][]]]]][]][]]][[[]][[[[[]]][[]][][[][][][]]][]]]][][][[[[]]][[]][][]][[]]]][[[[][[][][[[]][[]]]]]]][[]][[[][[][]][][[]][[]][]]][][[][][][[[[]][]][][
unbalanced: ][][[]][[[][[]][[][[[]]]]]][
unbalanced: [][]][][]][[
unbalanced: [[[][[]]]][][][][][][][]]]][[][][]][]]]]][[]]][][[]][]]][[][[][[][]][[]]]]][[[[][[][[]]][]]][][]][]]][][[[[]]][][[[][[[[]]][][]][][[[[[][][[][[][[][[][[[]
unbalanced: ][][[]][]]]][[][[][[][]]]][[[[
balanced:   [[[]]][[[[]][]]][][[[]]][][]
unbalanced: [[[]][]]]][][[[[[[[[[[[[][[]][[[[[[]][]]]][[]]]][]]]]][]]]]][[][[][][][[][[]][]]][[][[]][[[][]]]][]]]]][]][[[[
unbalanced: [[]][[]][[[[][][][][]]]][]]][][[][]]]][[[[
unbalanced: [][[]]][]]][[]]][[[]]][[][[]]]]][[[][]][[[[[[[[][[]]][][][[[]]][[][[][][]][]]][][]][]][]]][]][]][[[[[][[][[]
unbalanced: ][][[][][[[[][][[][[[][]]]]]][][][[][][[][[][[]]][[[[]]]][][[][[]][]]][[[][[[][][[[][]][[]]]][[][[]]]]]][[[][]][[[]]]]]]
unbalanced: ][[][[][][]][]][][[][][]][][][[[[][]]][[]]][[]
unbalanced: ]][][[]]]]][][[[][][]][[[[]][]]][]][[[]]][]]][[[[][[]]]][]][]][]][][[][[[]]][][][[][][[[[]][]]][]][[[[][]]]][][[][[][[[[[][[][]][[]][]]][][[]][]]][[[[][]][][]][[][]][[][[[[][

check all permutations of given length:
balanced:   []
unbalanced: ][
balanced:   [[]]
balanced:   [][]
unbalanced: []][
unbalanced: ][[]
unbalanced: ][][
unbalanced: ]][[
balanced:   [[[]]]
balanced:   [[][]]
balanced:   [[]][]
unbalanced: [[]]][
balanced:   [][[]]
balanced:   [][][]
unbalanced: [][]][
unbalanced: []][[]
unbalanced: []][][
unbalanced: []]][[
unbalanced: ][[[]]
unbalanced: ][[][]
unbalanced: ][[]][
unbalanced: ][][[]
unbalanced: ][][][
unbalanced: ][]][[
unbalanced: ]][[[]
unbalanced: ]][[][
unbalanced: ]][][[
unbalanced: ]]][[[
balanced:   [[[[]]]]
balanced:   [[[][]]]
balanced:   [[[]][]]
balanced:   [[[]]][]
unbalanced: [[[]]]][
balanced:   [[][[]]]
balanced:   [[][][]]
balanced:   [[][]][]
unbalanced: [[][]]][
balanced:   [[]][[]]
balanced:   [[]][][]
unbalanced: [[]][]][
unbalanced: [[]]][[]
unbalanced: [[]]][][
unbalanced: [[]]]][[
balanced:   [][[[]]]
balanced:   [][[][]]
balanced:   [][[]][]
unbalanced: [][[]]][
balanced:   [][][[]]
balanced:   [][][][]
unbalanced: [][][]][
unbalanced: [][]][[]
unbalanced: [][]][][
unbalanced: [][]]][[
unbalanced: []][[[]]
unbalanced: []][[][]
unbalanced: []][[]][
unbalanced: []][][[]
unbalanced: []][][][
unbalanced: []][]][[
unbalanced: []]][[[]
unbalanced: []]][[][
unbalanced: []]][][[
unbalanced: []]]][[[
unbalanced: ][[[[]]]
unbalanced: ][[[][]]
unbalanced: ][[[]][]
unbalanced: ][[[]]][
unbalanced: ][[][[]]
unbalanced: ][[][][]
unbalanced: ][[][]][
unbalanced: ][[]][[]
unbalanced: ][[]][][
unbalanced: ][[]]][[
unbalanced: ][][[[]]
unbalanced: ][][[][]
unbalanced: ][][[]][
unbalanced: ][][][[]
unbalanced: ][][][][
unbalanced: ][][]][[
unbalanced: ][]][[[]
unbalanced: ][]][[][
unbalanced: ][]][][[
unbalanced: ][]]][[[
unbalanced: ]][[[[]]
unbalanced: ]][[[][]
unbalanced: ]][[[]][
unbalanced: ]][[][[]
unbalanced: ]][[][][
unbalanced: ]][[]][[
unbalanced: ]][][[[]
unbalanced: ]][][[][
unbalanced: ]][][][[
unbalanced: ]][]][[[
unbalanced: ]]][[[[]
unbalanced: ]]][[[][
unbalanced: ]]][[][[
unbalanced: ]]][][[[
unbalanced: ]]]][[[[
balanced:   [[[[[]]]]]
balanced:   [[[[][]]]]
balanced:   [[[[]][]]]
balanced:   [[[[]]][]]
balanced:   [[[[]]]][]
unbalanced: [[[[]]]]][
balanced:   [[[][[]]]]
balanced:   [[[][][]]]
balanced:   [[[][]][]]
balanced:   [[[][]]][]
unbalanced: [[[][]]]][
balanced:   [[[]][[]]]
balanced:   [[[]][][]]
balanced:   [[[]][]][]
unbalanced: [[[]][]]][
balanced:   [[[]]][[]]
balanced:   [[[]]][][]
unbalanced: [[[]]][]][
unbalanced: [[[]]]][[]
unbalanced: [[[]]]][][
unbalanced: [[[]]]]][[
balanced:   [[][[[]]]]
balanced:   [[][[][]]]
balanced:   [[][[]][]]
balanced:   [[][[]]][]
unbalanced: [[][[]]]][
balanced:   [[][][[]]]
balanced:   [[][][][]]
balanced:   [[][][]][]
unbalanced: [[][][]]][
balanced:   [[][]][[]]
balanced:   [[][]][][]
unbalanced: [[][]][]][
unbalanced: [[][]]][[]
unbalanced: [[][]]][][
unbalanced: [[][]]]][[
balanced:   [[]][[[]]]
balanced:   [[]][[][]]
balanced:   [[]][[]][]
unbalanced: [[]][[]]][
balanced:   [[]][][[]]
balanced:   [[]][][][]
unbalanced: [[]][][]][
unbalanced: [[]][]][[]
unbalanced: [[]][]][][
unbalanced: [[]][]]][[
unbalanced: [[]]][[[]]
unbalanced: [[]]][[][]
unbalanced: [[]]][[]][
unbalanced: [[]]][][[]
unbalanced: [[]]][][][
unbalanced: [[]]][]][[
unbalanced: [[]]]][[[]
unbalanced: [[]]]][[][
unbalanced: [[]]]][][[
unbalanced: [[]]]]][[[
balanced:   [][[[[]]]]
balanced:   [][[[][]]]
balanced:   [][[[]][]]
balanced:   [][[[]]][]
unbalanced: [][[[]]]][
balanced:   [][[][[]]]
balanced:   [][[][][]]
balanced:   [][[][]][]
unbalanced: [][[][]]][
balanced:   [][[]][[]]
balanced:   [][[]][][]
unbalanced: [][[]][]][
unbalanced: [][[]]][[]
unbalanced: [][[]]][][
unbalanced: [][[]]]][[
balanced:   [][][[[]]]
balanced:   [][][[][]]
balanced:   [][][[]][]
unbalanced: [][][[]]][
balanced:   [][][][[]]
balanced:   [][][][][]
unbalanced: [][][][]][
unbalanced: [][][]][[]
unbalanced: [][][]][][
unbalanced: [][][]]][[
unbalanced: [][]][[[]]
unbalanced: [][]][[][]
unbalanced: [][]][[]][
unbalanced: [][]][][[]
unbalanced: [][]][][][
unbalanced: [][]][]][[
unbalanced: [][]]][[[]
unbalanced: [][]]][[][
unbalanced: [][]]][][[
unbalanced: [][]]]][[[
unbalanced: []][[[[]]]
unbalanced: []][[[][]]
unbalanced: []][[[]][]
unbalanced: []][[[]]][
unbalanced: []][[][[]]
unbalanced: []][[][][]
unbalanced: []][[][]][
unbalanced: []][[]][[]
unbalanced: []][[]][][
unbalanced: []][[]]][[
unbalanced: []][][[[]]
unbalanced: []][][[][]
unbalanced: []][][[]][
unbalanced: []][][][[]
unbalanced: []][][][][
unbalanced: []][][]][[
unbalanced: []][]][[[]
unbalanced: []][]][[][
unbalanced: []][]][][[
unbalanced: []][]]][[[
unbalanced: []]][[[[]]
unbalanced: []]][[[][]
unbalanced: []]][[[]][
unbalanced: []]][[][[]
unbalanced: []]][[][][
unbalanced: []]][[]][[
unbalanced: []]][][[[]
unbalanced: []]][][[][
unbalanced: []]][][][[
unbalanced: []]][]][[[
unbalanced: []]]][[[[]
unbalanced: []]]][[[][
unbalanced: []]]][[][[
unbalanced: []]]][][[[
unbalanced: []]]]][[[[
unbalanced: ][[[[[]]]]
unbalanced: ][[[[][]]]
unbalanced: ][[[[]][]]
unbalanced: ][[[[]]][]
unbalanced: ][[[[]]]][
unbalanced: ][[[][[]]]
unbalanced: ][[[][][]]
unbalanced: ][[[][]][]
unbalanced: ][[[][]]][
unbalanced: ][[[]][[]]
unbalanced: ][[[]][][]
unbalanced: ][[[]][]][
unbalanced: ][[[]]][[]
unbalanced: ][[[]]][][
unbalanced: ][[[]]]][[
unbalanced: ][[][[[]]]
unbalanced: ][[][[][]]
unbalanced: ][[][[]][]
unbalanced: ][[][[]]][
unbalanced: ][[][][[]]
unbalanced: ][[][][][]
unbalanced: ][[][][]][
unbalanced: ][[][]][[]
unbalanced: ][[][]][][
unbalanced: ][[][]]][[
unbalanced: ][[]][[[]]
unbalanced: ][[]][[][]
unbalanced: ][[]][[]][
unbalanced: ][[]][][[]
unbalanced: ][[]][][][
unbalanced: ][[]][]][[
unbalanced: ][[]]][[[]
unbalanced: ][[]]][[][
unbalanced: ][[]]][][[
unbalanced: ][[]]]][[[
unbalanced: ][][[[[]]]
unbalanced: ][][[[][]]
unbalanced: ][][[[]][]
unbalanced: ][][[[]]][
unbalanced: ][][[][[]]
unbalanced: ][][[][][]
unbalanced: ][][[][]][
unbalanced: ][][[]][[]
unbalanced: ][][[]][][
unbalanced: ][][[]]][[
unbalanced: ][][][[[]]
unbalanced: ][][][[][]
unbalanced: ][][][[]][
unbalanced: ][][][][[]
unbalanced: ][][][][][
unbalanced: ][][][]][[
unbalanced: ][][]][[[]
unbalanced: ][][]][[][
unbalanced: ][][]][][[
unbalanced: ][][]]][[[
unbalanced: ][]][[[[]]
unbalanced: ][]][[[][]
unbalanced: ][]][[[]][
unbalanced: ][]][[][[]
unbalanced: ][]][[][][
unbalanced: ][]][[]][[
unbalanced: ][]][][[[]
unbalanced: ][]][][[][
unbalanced: ][]][][][[
unbalanced: ][]][]][[[
unbalanced: ][]]][[[[]
unbalanced: ][]]][[[][
unbalanced: ][]]][[][[
unbalanced: ][]]][][[[
unbalanced: ][]]]][[[[
unbalanced: ]][[[[[]]]
unbalanced: ]][[[[][]]
unbalanced: ]][[[[]][]
unbalanced: ]][[[[]]][
unbalanced: ]][[[][[]]
unbalanced: ]][[[][][]
unbalanced: ]][[[][]][
unbalanced: ]][[[]][[]
unbalanced: ]][[[]][][
unbalanced: ]][[[]]][[
unbalanced: ]][[][[[]]
unbalanced: ]][[][[][]
unbalanced: ]][[][[]][
unbalanced: ]][[][][[]
unbalanced: ]][[][][][
unbalanced: ]][[][]][[
unbalanced: ]][[]][[[]
unbalanced: ]][[]][[][
unbalanced: ]][[]][][[
unbalanced: ]][[]]][[[
unbalanced: ]][][[[[]]
unbalanced: ]][][[[][]
unbalanced: ]][][[[]][
unbalanced: ]][][[][[]
unbalanced: ]][][[][][
unbalanced: ]][][[]][[
unbalanced: ]][][][[[]
unbalanced: ]][][][[][
unbalanced: ]][][][][[
unbalanced: ]][][]][[[
unbalanced: ]][]][[[[]
unbalanced: ]][]][[[][
unbalanced: ]][]][[][[
unbalanced: ]][]][][[[
unbalanced: ]][]]][[[[
unbalanced: ]]][[[[[]]
unbalanced: ]]][[[[][]
unbalanced: ]]][[[[]][
unbalanced: ]]][[[][[]
unbalanced: ]]][[[][][
unbalanced: ]]][[[]][[
unbalanced: ]]][[][[[]
unbalanced: ]]][[][[][
unbalanced: ]]][[][][[
unbalanced: ]]][[]][[[
unbalanced: ]]][][[[[]
unbalanced: ]]][][[[][
unbalanced: ]]][][[][[
unbalanced: ]]][][][[[
unbalanced: ]]][]][[[[
unbalanced: ]]]][[[[[]
unbalanced: ]]]][[[[][
unbalanced: ]]]][[[][[
unbalanced: ]]]][[][[[
unbalanced: ]]]][][[[[
unbalanced: ]]]]][[[[[

### Scala Version 2

Works with: Scala version 2.10.1
import scala.util.Random.shuffle

object BalancedBracketsApp extends App {

for (length <- 0 until 10) {
val str = randomBrackets(length)
if (is_balanced(str))
println(s"$str - ok") else println(s"$str - NOT ok")
}

def randomBrackets(length: Int): String =
shuffle(("[]" * length).toSeq).mkString

def isBalanced(bracketString: String): Boolean = {
var balance = 0
for (char <- bracketString) {
char match {
case '[' => balance += 1
case ']' => balance -= 1
}
if (balance < 0) return false;
}
balance == 0
}

}

Alternate implementation of "isBalanced" using tail-recursion instead of var and return:

import scala.util.Random.shuffle
import scala.annotation.tailrec

// ...

def isBalanced(str: String): Boolean = isBalanced(str.toList, balance = 0)

@tailrec
def isBalanced(str: List[Char], balance: Int = 0): Boolean =
str match {
case _ if (balance < 0) => false
case Nil => balance == 0
case char :: rest =>
val newBalance = char match {
case '[' => balance + 1
case ']' => balance -1
}
isBalanced(rest, newBalance)
}

Slightly modified implementation of "isBalanced" using tail-recursion

Works with: Scala version 2.11.7
@scala.annotation.tailrec
final def isBalanced(
str: List[Char],
// accumulator|indicator|flag
balance: Int = 0,
options_Map: Map[Char, Int] = Map(('[' -> 1), (']' -> -1))
): Boolean = if (balance < 0) {
// base case
false
} else {
if (str.isEmpty){
// base case
balance == 0
} else {
// recursive step
}
}

Sample output:

 - ok
[ - NOT ok
[] - ok
[][ - NOT ok
][][ - NOT ok
[][][ - NOT ok
[][][] - ok
[[[]][] - NOT ok
[[][][]] - ok
[[[][]][] - NOT ok


## Scheme

(define (balanced-brackets string)
(define (b chars sum)
(cond ((< sum 0)
#f)
((and (null? chars) (= 0 sum))
#t)
((null? chars)
#f)
((char=? #$(car chars)) (b (cdr chars) (+ sum 1))) ((char=? #$ (car chars))
(b (cdr chars) (- sum 1)))
(else
(#f)))
(b (string->list string) 0))

(balanced-brackets "")

(balanced-brackets "[]")
(balanced-brackets "[][]")
(balanced-brackets "[[][]]")

(balanced-brackets "][")
(balanced-brackets "][][")
(balanced-brackets "[]][[]")

## Scilab

Translation of: MATLAB
function varargout=isbb(s)
st=strsplit(s);
t=cumsum((st=='[')-(st==']'));
balanced=and(t>=0) & t(length(t))==0;
varargout=list(balanced)
endfunction
Output:

The following code was used to generate random strings of length 5, 16, and 22 chars. It also displays the generated string, and the output (true of false) of isbb().

for j=[5 16 22]
s=[];
for i=1:j
p=rand();
if p>0.5 then
s=s+"[";
else
s=s+"]";
end
end
disp(s);
x=isbb(s);
disp(x);
end

Console output:

 ][]][

F

[[[[][[[][]]]]]]

T

][[][]]]][]][[]][][]]]

F

$include "seed7_05.s7i"; const func string: generateBrackets (in integer: count) is func result var string: stri is ""; local var integer: index is 0; var integer: pos is 0; var char: ch is ' '; begin stri := "[" mult count & "]" mult count; for index range 1 to length(stri) do pos := rand(1, length(stri)); ch := stri[index]; stri @:= [index] stri[pos]; stri @:= [pos] ch; end for; end func; const func boolean: checkBrackets (in string: test) is func result var boolean: okay is TRUE; local var char: ch is ' '; var integer: open is 0; begin for ch range test do if ch = '[' then incr(open); elsif ch = ']' then if open = 0 then okay := FALSE; else decr(open); end if; end if; end for; okay := open = 0; end func; const proc: main is func local var integer: n is 0; var integer: count is 0; var string: stri is ""; begin for n range 0 to 4 do for count range 1 to 3 do stri := generateBrackets(n); writeln(stri <& ": " <& checkBrackets(stri)); end for; end for; end func; Output: : TRUE : TRUE : TRUE []: TRUE ][: FALSE ][: FALSE ][[]: FALSE [[]]: TRUE [[]]: TRUE [][][]: TRUE [[][]]: TRUE []]][[: FALSE [][][]][: FALSE [][][][]: TRUE ]][][[][: FALSE  ## SETL program balanced_brackets; setrandom(0); loop for length in [1..10] do s := generate length; print(balanced s, s); end loop; op generate(n); s := "["*n + "]"*n; loop for i in [n*2, n*2-1..2] do j := 1 + random(i - 1); [s(i), s(j)] := [s(j), s(i)]; end loop; return s; end op; op balanced(s); depth := 0; loop for c in s do case c of ("["): depth +:= 1; ("]"): depth -:= 1; if depth<0 then return false; end if; end case; end loop; return depth = 0; end op; end program; Output: #F ][ #F ]][[ #T [[]][] #F [[]]][][ #F ][[][][]][ #F ]][]]]][[[[[ #F ]]][[]]][[[[[] #T [[][][[][[]][]]] #F []][[]]]][][][[][[ #F []][]]][]][][[[][[][ ## Sidef func balanced (str) { var depth = 0 str.each { |c| if(c=='['){ ++depth } elsif(c==']'){ --depth < 0 && return false } } return !depth } for str [']','[','[[]','][]','[[]]','[[]]]][][]]','x[ y [ [] z ]][ 1 ][]abcd'] { printf("%sbalanced\t: %s\n", balanced(str) ? "" : "NOT ", str) } Output: NOT balanced : ] NOT balanced : [ NOT balanced : [[] NOT balanced : ][] balanced : [[]] NOT balanced : [[]]]][][]] balanced : x[ y [ [] z ]][ 1 ][]abcd  ## Simula BEGIN INTEGER U; U := ININT; BEGIN TEXT PROCEDURE GENERATE(N); INTEGER N; BEGIN INTEGER R; TEXT T; T :- NOTEXT; WHILE N > 0 DO BEGIN R := RANDINT(1,2,U); T :- T & (IF R = 1 THEN "[" ELSE "]"); N := N - 1; END; GENERATE :- T; END GENERATE; BOOLEAN PROCEDURE BALANCED(T); TEXT T; BEGIN INTEGER LEVEL; CHARACTER BRACE; BOOLEAN DONE; T.SETPOS(1); WHILE T.MORE AND NOT DONE DO BEGIN BRACE := T.GETCHAR; IF BRACE = '[' THEN LEVEL := LEVEL + 1; IF BRACE = ']' THEN LEVEL := LEVEL - 1; IF LEVEL < 0 THEN DONE := TRUE; END; BALANCED := LEVEL = 0; END BALANCED; INTEGER I,M; TEXT T; FOR I := 1 STEP 1 UNTIL 40 DO BEGIN M := RANDINT(0,10,U); T :- GENERATE(M); IF BALANCED(T) THEN OUTTEXT(" ") ELSE OUTTEXT(" NOT"); OUTTEXT(" BALANCED: "); OUTTEXT(T); OUTIMAGE; END; END; END Input: 710 Output:  NOT BALANCED: [[[[[[][ NOT BALANCED: [[[[] NOT BALANCED: ][ NOT BALANCED: [][[[[ BALANCED: [][[]] NOT BALANCED: [[] NOT BALANCED: ][ NOT BALANCED: ]][[] NOT BALANCED: []]] NOT BALANCED: ][]][[] NOT BALANCED: ]]][ NOT BALANCED: ]][ NOT BALANCED: ][]]]]][] NOT BALANCED: [[][[[]][[ NOT BALANCED: ]][]][]] BALANCED: NOT BALANCED: ][[ NOT BALANCED: []]][[] NOT BALANCED: ]]]][[]]][ NOT BALANCED: ]] BALANCED: [[][[[]]]] NOT BALANCED: ][][]] BALANCED: NOT BALANCED: [[[[[]][[] NOT BALANCED: []][[[][ NOT BALANCED: []]]][][] NOT BALANCED: ][]][][ NOT BALANCED: []] NOT BALANCED: ]]][[ NOT BALANCED: [ BALANCED: [] NOT BALANCED: ][]]] NOT BALANCED: [[[[[[]][ NOT BALANCED: [][[][ NOT BALANCED: ]] NOT BALANCED: ]][ NOT BALANCED: [[[[[[ NOT BALANCED: ]]]]] NOT BALANCED: ]][[] NOT BALANCED: ][][][][  ## Standard ML Works with: PolyML fun isBalanced s = checkBrackets 0 (String.explode s) and checkBrackets 0 [] = true | checkBrackets _ [] = false | checkBrackets ~1 _ = false | checkBrackets counter (#"["::rest) = checkBrackets (counter + 1) rest | checkBrackets counter (#"]"::rest) = checkBrackets (counter - 1) rest | checkBrackets counter (_::rest) = checkBrackets counter rest An example of usage val () = List.app print (List.map (* Turn true' and false' to OK' and NOT OK' respectively *) (fn s => if isBalanced s then s ^ "\t\tOK\n" else s ^ "\t\tNOT OK\n" ) (* A set of strings to test *) ["", "[]", "[][]", "[[][]]", "][", "][][", "[]][[]"] ) Output:  OK [] OK [][] OK [[][]] OK ][ NOT OK ][][ NOT OK []][[] NOT OK  ## Stata mata function random_brackets(n) { return(invtokens(("[","]")[runiformint(1,2*n,1,2)],"")) } function is_balanced(s) { n = strlen(s) if (n==0) return(1) a = runningsum(92:-ascii(s)) return(all(a:>=0) & a[n]==0) } end Test : is_balanced("") 1 : is_balanced("[]") 1 : is_balanced("[][]") 1 : is_balanced("[[][]]") 1 : is_balanced("][") 0 : is_balanced("][][") 0 : is_balanced("[]][[]") ## Swift Checks balance function: import Foundation func isBal(str: String) -> Bool { var count = 0 return !str.characters.contains { ($0 == "["  ? ++count : --count) < 0 } && count == 0

}

output:

isBal("[[[]]]") // true

isBal("[]][[]") // false

Random Bracket function:

func randBrack(n: Int) -> String {

var bracks: [Character] = Array(Repeat(count: n, repeatedValue: "["))

for i in UInt32(n+1)...UInt32(n + n) {

bracks.insert("]", atIndex: Int(arc4random_uniform(i)))

}

return String(bracks)

}

output:

randBrack(2) // "]][["

Random check balance function:

func randIsBal(n: Int) {

let (bal, un) = ("", "un")

for str in (1...n).map(randBrack) {

print("$$str) is \(isBal(str) ? bal : un)balanced\n") } } randIsBal(4) output: // ][ is unbalanced // // ]][[ is unbalanced // // []][[] is unbalanced // // [][][[]] is balanced ## Tcl proc generate {n} { if {!n} return set l [lrepeat n "$" "$"] set len [llength l] while {len} { set tmp [lindex l [set i [expr {int(len * rand())}]]] lset l i [lindex l [incr len -1]] lset l len tmp } return [join l ""] } proc balanced s { set n 0 foreach c [split s ""] { # Everything unmatched is ignored, which is what we want switch -exact -- c { "$" {incr n} "$" {if {[incr n -1] < 0} {return false}} } } expr {!n} } for {set i 0} {i < 15} {incr i} { set s [generate i] puts "\"s\"\t-> [expr {[balanced s] ? {OK} : {NOT OK}}]" } Sample output: "" -> OK "][" -> NOT OK "]][[" -> NOT OK "]]][[[" -> NOT OK "[][][[]]" -> OK "[[[][[]]]]" -> OK "[][][[][]][]" -> OK "[[]][]]]][[[][" -> NOT OK "][][[][][][[]]][" -> NOT OK "][[[][]][]]][][[][" -> NOT OK "]][][]][[][[][[]][][" -> NOT OK "[[[][[][]]][]]][[]]][[" -> NOT OK "[[]]][]][[[[]]][[][][[]]" -> NOT OK "][[][][]][[[]][[[[][]]]][]" -> NOT OK "]][[][[][[[[]][[][]][[]]]]][" -> NOT OK  ### Constructing correctly balanced strings It is, of course, possible to directly construct such a balanced string, this being much more useful as the length of the string to generate grows longer. This is done by conceptually building a random tree (or forest) and then walking the tree, with open brackets being appended when a node is entered from its root and close brackets being appended when a node is left for its root. This is equivalent to inserting a balanced pair of brackets at a random place in an initially-empty string ${\displaystyle n}$ times, which might be done like this: proc constructBalancedString {n} { set s "" for {set i 0} {i < n} {incr i} { set x [expr {int(rand() * ([string length s] + 1))}] set s "[string range s 0 [expr {x-1}]][string range s x end]" } return s } As noted, because the generated string is guaranteed to be balanced, it requires no further filtering and this results in much more efficient generation of balanced strings at longer lengths (because there's no need to backtrack). ## TMG Unix TMG is designed to process and generate files rather than process text in memory. Therefore generation and analysis parts can only be done in separate programs. Generation program in Unix TMG: program: readint(n) [n>0] readint(seed) loop: parse(render) [--n>0?]/done loop; render: random(i, 15) [i = (i+1)*2] loop2 = { 1 * }; loop2: random(b, 2) ( [b&1?] ={<[>} | ={<]>} ) [--i>0?]/done loop2 = { 2 1 }; done: ; /* Reads decimal integer */ readint: proc(n;i) string(spaces) [n=0] inta int1: [n = n*12+i] inta\int1; inta: char(i) [i<72?] [(i =- 60)>=0?]; /* LCG params: a = 29989, c = 28411, m = 35521 */ random: proc(r,mod) [seed = (seed*72445 + 67373) % 105301] [r = seed % mod] [r = r<0 ? -r : r]; spaces: << >>; n: 0; i: 0; b: 0; seed: 0; Sample output: [][] ][]][]][[[]]]]][]][] [[][]][[[]]]][[[ []][[[[]][[]][]]][][]] ]]]][[[[ Analysis can be done easily using grammar specification, rather than counting brackets: loop: parse(corr)\loop parse(incorr)\loop; corr: brkts * = { < OK: > 1 * }; brkts: brkt/null brkts = { 2 1 }; brkt: <[> brkts <]> = { <[> 1 <]> }; null: = {}; incorr: smark ignore(<<>>) any(!<<>>) string(nonl) scopy ( * | () ) = { <NOT OK: > 1 * }; nonl: !<< >>; Sample output: NOT OK: ][][ NOT OK: ]][][[ OK: [[]][][] NOT OK: [[][]]][][]][] OK: [[[]][[]][][]][] OK: [[]][[[][]]][[[]]] NOT OK: [[[[][[][[][[[]]][[[[[][]] OK: [[[][[[][][[[[[]]][[][]][]][][[[]]]]]]]] ## TUSCRIPT  MODE TUSCRIPT SECTION gen_brackets values="[']",brackets="" LOOP n=1,12 brackets=APPEND (brackets,"","~") LOOP m=1,n a=RANDOM_NUMBERS (1,2,1),br=SELECT(values,#a) brackets=APPEND(brackets,"",br) b=RANDOM_NUMBERS (1,2,1),br=SELECT(values,#b) brackets=APPEND(brackets,"",br) ENDLOOP ENDLOOP brackets=SPLIT (brackets,":~:") ENDSECTION MODE DATA  BUILD X_TABLE brackets=* [[[[ (4 ]]]] )4 [[[ (3 ]]] )3 [[ (2 ]] )2 [ (1 ] )1  MODE TUSCRIPT DO gen_brackets LOOP b=brackets status=CHECK_BRACKETS (b,brackets,a1,e1,a2,e2) PRINT b," ",status ENDLOOP Output:  OK ]] ERROR [[]] OK [][[]] OK []]]][[] ERROR []][]][][[ ERROR [[]][][]]]]] ERROR []][[][[]][[][ ERROR [][[[][[[[[[]][[ ERROR ]]][[]][]][[[][][[ ERROR ][][[]]][[[[[]]][[][ ERROR [[[][][]][]]]][[[[[[]] ERROR ][[[]][[][[[[[[[[[[[]]]] ERROR  ## TXR @(define paren)@(maybe)[@(coll)@(paren)@(until)]@(end)]@(end)@(end) @(do (defvar r (make-random-state nil)) (defun generate-1 (count) (let ((bkt (repeat "[]" count))) (cat-str (shuffle bkt)))) (defun generate-list (num count) [[generate tf (op generate-1 count)] 0..num])) @(next :list @(generate-list 22 6)) @(output) INPUT MATCHED REST @(end) @ (collect) @ (all) @parens @ (and) @{matched (paren)}@mismatched @ (end) @ (output) @{parens 15} @{matched 15} @{mismatched 15} @ (end) @(end) The recursive pattern function @(paren) gives rise to a grammar which matches parentheses: @(define paren)@(maybe)[@(coll)@(paren)@(until)]@(end)]@(end)@(end) A string of balanced parentheses is an optional unit (@(maybe) ... @(end)) that begins with [, followed by zero or more such balanced strings, followed by ]. Sample run:  ./txr paren.txr INPUT MATCHED REST ][[[]][][[]] ][[[]][][[]] []][[]][][[] [] ][[]][][[] [][[[[]]]]][ [] [[[[]]]]][ ][[][[]]][][ ][[][[]]][][ [[[][[]]][]] [[[][[]]][]] ]][]][[[][[] ]][]][[[][[] [[]][]][[[]] [[]] []][[[]] ]][]][]][[[[ ]][]][]][[[[ ]][[]]][][[[ ]][[]]][][[[ ]]]][[]][[[[ ]]]][[]][[[[ ][[[[][[]]]] ][[[[][[]]]] ][]][]]][[[[ ][]][]]][[[[ ]][][[][][[] ]][][[][][[] ]][][]][[][[ ]][][]][[][[ [][[]][]]][[ [] [[]][]]][[ [[]]]]][[[[] [[]] ]]][[[[] ]][[[[[[]]]] ]][[[[[[]]]] ][][][[[]][] ][][][[[]][] []][]][][][[ [] ][]][][][[ ]][[[][]][[] ]][[[][]][[] ][[[[]]]][][ ][[[[]]]][][ [[]]]]][[][[ [[]] ]]][[][[  ## TypeScript Translation of: JavaScript // Balanced brackets function isStringBalanced(str: string): bool { var paired = 0; for (var i = 0; i < str.length && paired >= 0; i++) { var c = str.charAt(i); if (c == '[') paired++; else if (c == ']') paired--; } return (paired == 0); } function generate(n: number): string { var opensCount = 0, closesCount = 0; // Choose at random until n of one type generated var generated: string[] = new Array(); // Works like StringBuilder while (opensCount < n && closesCount < n) { if (Math.floor(Math.random() * 2) == 0) { ++opensCount; generated.push("["); } else { ++closesCount; generated.push("]"); } } // Now pad with the remaining other brackets generated.push(opensCount == n ? "]".repeat(n - closesCount) : "[".repeat(n - opensCount)); return generated.join(""); } console.log("Supplied examples"); var tests: string[] = ["", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"]; for (var test of tests) console.log(The string '{test}' is {(isStringBalanced(test) ? "OK." : "not OK.")); console.log(); console.log("Random generated examples"); for (var example = 0; example < 10; example++) { var test = generate(Math.floor(Math.random() * 10) + 1); console.log(The string '{test}' is {(isStringBalanced(test) ? "OK." : "not OK.")}); } Output: Supplied examples The string '' is OK. The string '[]' is OK. The string '][' is not OK. The string '[][]' is OK. The string '][][' is not OK. The string '[[][]]' is OK. The string '[]][[]' is not OK. Random generated examples The string ']]][[[][' is not OK. The string '][][][[[[]]]' is not OK. The string ']][[[[]]' is not OK. The string '][]]]]]][][][][[[[[[' is not OK. The string '][[[][][[[]]]]' is not OK. The string '[[[]]]' is OK. The string ']]]][[[[[]' is not OK. The string '][[]]]]][[[][[]]][[[' is not OK. The string ']]]][]][[[[[' is not OK. The string '[[[[[[]]]]]]' is OK.  ## UNIX Shell Works with: bash generate() { local b=() local i j tmp for ((i=1; i<=1; i++)); do b+=( '[' ']') done for ((i={#b[@]}-1; i>0; i--)); do j=(rand i) tmp={b[j]} b[j]={b[i]} b[i]=tmp done local IFS= echo "{b[*]}" } # a random number in the range [0,n) rand() { echo (( RANDOM % 1 )) } balanced() { local -i lvl=0 local i for ((i=0; i<{#1}; i++)); do case {1:i:1} in '[') ((lvl++));; ']') (( --lvl < 0 )) && return 1;; esac done (( lvl == 0 )); return ? } for ((i=0; i<=10; i++)); do test=(generate i) balanced "test" && result=OK || result="NOT OK" printf "%s\t%s\n" "test" "result" done Output:  OK ][ NOT OK []][ NOT OK [[][]] OK ]][[]][[ NOT OK [[]][[][]] OK []][[[[]]]][ NOT OK [[]][]][]][[[] NOT OK [][][[[[][][]]]] OK [][][[[[]]][[][]]] OK ][[]][][][[[]]][[]][ NOT OK ## Ursala #import std #import nat balanced = @NiX ~&irB->ilZB ~&rh?/~&lbtPB ~&NlCrtPX #cast %bm main = ^(2-'[]'*,balanced)* eql@ZFiFX*~ iota64 output: < '': true, '[]': true, '][[]': false, '[][]': true, '[[]]': true, ']][[[]': false, '][][[]': false, '[]][[]': false, '][[][]': false, '[][][]': true, '[[]][]': true, '][[[]]': false, '[][[]]': true, '[[][]]': true, '[[[]]]': true> ## VBA Public Function checkBrackets(s As String) As Boolean 'function checks strings for balanced brackets Dim Depth As Integer Dim ch As String * 1 Depth = 0 For i = 1 To Len(s) ch = Mid(s, i, 1) If ch = "[" Then Depth = Depth + 1 If ch = "]" Then If Depth = 0 Then 'not balanced checkBrackets = False Exit Function Else Depth = Depth - 1 End If End If Next checkBrackets = (Depth = 0) End Function Public Function GenerateBrackets(N As Integer) As String 'generate a string with N opening and N closing brackets in random order Dim s As String Dim N2 As Integer, j As Integer Dim Brackets() As String * 1 Dim temp As String * 1 'catch trivial value If N <= 0 Then GenerateBrackets = "" Exit Function End If N2 = N + N ReDim Brackets(1 To N2) For i = 1 To N2 Step 2 Brackets(i) = "[" Brackets(i + 1) = "]" Next i 'shuffle. For i = 1 To N2 j = 1 + Int(Rnd() * N2) 'swap brackets i and j temp = Brackets(i) Brackets(i) = Brackets(j) Brackets(j) = temp Next i 'generate string s = "" For i = 1 To N2 s = s & Brackets(i) Next i GenerateBrackets = s End Function Public Sub BracketsTest() Dim s As String Dim i As Integer For i = 0 To 10 s = GenerateBrackets(i) Debug.Print """" & s & """: "; If checkBrackets(s) Then Debug.Print " OK" Else Debug.Print " Not OK" Next End Sub sample output: BracketsTest "": OK "][": Not OK "[][]": OK "][[]][": Not OK "][]][[[]": Not OK "[[][]]][[]": Not OK "]][[[[[]]]][": Not OK "[[[]][][][][]]": OK "]][[[]][[[]][]][": Not OK "[[][]][]]][[[[]][]": Not OK "]][][[[][]]][][[][][": Not OK  ## VBScript For n = 1 To 10 sequence = Generate_Sequence(n) WScript.Echo sequence & " is " & Check_Balance(sequence) & "." Next Function Generate_Sequence(n) For i = 1 To n j = Round(Rnd()) If j = 0 Then Generate_Sequence = Generate_Sequence & "[" Else Generate_Sequence = Generate_Sequence & "]" End If Next End Function Function Check_Balance(s) Set Stack = CreateObject("System.Collections.Stack") For i = 1 To Len(s) char = Mid(s,i,1) If i = 1 Or char = "[" Then Stack.Push(char) ElseIf Stack.Count <> 0 Then If char = "]" And Stack.Peek = "[" Then Stack.Pop End If Else Stack.Push(char) End If Next If Stack.Count > 0 Then Check_Balance = "Not Balanced" Else Check_Balance = "Balanced" End If End Function Output: Note: For some reason, the function to generate the bracket sequence, Generate_Sequence, does not produce a balanced one. But the function to check if it is balanced or not, Check_Balance, works if a balanced argument is passed manually. ] is Not Balanced. ]] is Not Balanced. [[] is Not Balanced. []]] is Not Balanced. [[]][ is Not Balanced. ]][][] is Not Balanced. ][][[]] is Not Balanced. [[]]]]][ is Not Balanced. ]][][]][] is Not Balanced. [[][[[[[]] is Not Balanced. Antother version not using libraries. The generator works as intended (more difficult to do than the checking) option explicit function do_brackets(bal) dim s,i,cnt,r if bal then s="[":cnt=1 else s="":cnt=0 for i=1 to 20 if (rnd>0.7) then r=not r if not r then s=s+"[" :cnt=cnt+1 else if not bal or (bal and cnt>0) then s=s+"]":cnt=cnt-1 end if next if bal and cnt<>0 then s=s&string(cnt,"]") if not bal and cnt=0 then s=s&"]" do_brackets=s end function function isbalanced(s) dim s1,i,cnt: cnt=0 for i=1 to len(s) s1=mid(s,i,1) if s1="[" then cnt=cnt+1 if s1="]" then cnt=cnt-1 if cnt<0 then isbalanced=false:exit function next isbalanced=(cnt=0) end function function iif(a,b,c): if a then iif=b else iif=c end if : end function randomize timer dim i,s,bal,bb for i=1 to 10 bal=(rnd>.5) s=do_brackets(bal) bb=isbalanced(s) wscript.echo iif (bal,"","un")& "balanced string " &vbtab _ & s & vbtab & " Checks as " & iif(bb,"","un")&"balanced" next Sample run unbalanced string [[[[[[[[][[][[[[[]][ Checks as unbalanced balanced string [[[]]][[[[[[[]][]]]]]] Checks as balanced balanced string [[[]][]][[[[[]]]]] Checks as balanced unbalanced string ][][]][[[[]]][]]]]]] Checks as unbalanced balanced string [[][[[[[[[[]]][[[[[[[]]]]]]]]]]]]] Checks as balanced balanced string [[]][][[[[[]]]]] Checks as balanced balanced string [][[]][][][[[[[[]]]]]] Checks as balanced balanced string [[[[[[[]][[[[[[[[[][[]]]]]]]]]]]]]]] Checks as balanced unbalanced string [[]]][[[[[[]]]]]][][] Checks as unbalanced balanced string [[[[[[][[[[[]]]]]]]]]] Checks as balanced  ## Visual Basic .NET Module Module1 Private rand As New Random Sub Main() For numInputs As Integer = 1 To 10 '10 is the number of bracket sequences to test. Dim input As String = GenerateBrackets(rand.Next(0, 5)) '5 represents the number of pairs of brackets (n) Console.WriteLine(String.Format("{0} : {1}", input.PadLeft(10, CChar(" ")), If(IsBalanced(input) = True, "OK", "NOT OK"))) Next Console.ReadLine() End Sub Private Function GenerateBrackets(n As Integer) As String Dim randomString As String = "" Dim numOpen, numClosed As Integer Do Until numOpen = n And numClosed = n If rand.Next(0, 501) Mod 2 = 0 AndAlso numOpen < n Then randomString = String.Format("{0}{1}", randomString, "[") numOpen += 1 ElseIf rand.Next(0, 501) Mod 2 <> 0 AndAlso numClosed < n Then randomString = String.Format("{0}{1}", randomString, "]") numClosed += 1 End If Loop Return randomString End Function Private Function IsBalanced(brackets As String) As Boolean Dim numOpen As Integer = 0 Dim numClosed As Integer = 0 For Each character As Char In brackets If character = "["c Then numOpen += 1 If character = "]"c Then numClosed += 1 If numClosed > numOpen Then Return False End If Next Return numOpen = numClosed End Function End Module Output:  ][[][]][ : NOT OK []]][[[] : NOT OK [[]][] : OK [] : OK [[[]]] : OK [] : OK []][][ : NOT OK ]][[[] : NOT OK : OK [] : OK  ## V (Vlang) import datatypes as dt fn is_valid(bracket string) bool { mut s := dt.Stack<string>{} for b in bracket.split('') { if b == '[' { s.push(b) } else { if s.peek() or {''} == '[' { s.pop() or {panic("WON'T GET HERE EVER")} } else { return false } } } return true } fn main() { brackets := ['','[]','[][]','[[][]]','][','][][','[]][[]','[][[][[]][][[][]]]'] for b in brackets { println('b {is_valid(b)}') } } Output:  true [] true [][] true [[][]] true ][ false ][][ false []][[] false [][[][[]][][[][]]] true  ## Wren Translation of: Kotlin import "random" for Random var isBalanced = Fn.new { |s| if (s.isEmpty) return true var countLeft = 0 // number of left brackets so far unmatched for (c in s) { if (c == "[") { countLeft = countLeft + 1 } else if (countLeft > 0) { countLeft = countLeft - 1 } else { return false } } return countLeft == 0 } System.print("Checking examples in task description:") var brackets = ["", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"] for (b in brackets) { System.write((b != "") ? b : "(empty)") System.print("\t %(isBalanced.call(b) ? "OK" : "NOT OK")") } System.print("\nChecking 7 random strings of brackets of length 8:") var rand = Random.new() for (i in 1..7) { var s = "" for (j in 1..8) s = s + ((rand.int(2) == 0) ? "[" : "]") System.print("%(s) %(isBalanced.call(s) ? "OK" : "NOT OK")") } Output: Checking examples in task description: (empty) OK [] OK ][ NOT OK [][] OK ][][ NOT OK [[][]] OK []][[] NOT OK Checking 7 random strings of brackets of length 8: [][][][[ NOT OK [[][][]] OK [[[[]]]] OK [[]]]][[ NOT OK ]][][[]] NOT OK ][]][[[] NOT OK [][][[][ NOT OK  ## X86 Assembly section .data MsgBalanced: db "OK", 10 MsgBalancedLen: equ 3 MsgUnbalanced: db "NOT OK", 10 MsgUnbalancedLen: equ 7 MsgBadInput: db "BAD INPUT", 10 MsgBadInputLen: equ 10 Open: equ '[' Closed: equ ']' section .text BalancedBrackets: xor rcx, rcx mov rsi, rdi cld processBracket: lodsb cmp al, 0 je determineBalance cmp al, Open je processOpenBracket cmp al, Closed je processClosedBracket mov rsi, MsgBadInput mov rdx, MsgBadInputLen jmp displayResult processOpenBracket: add rcx, 1 jmp processBracket processClosedBracket: cmp rcx, 0 je unbalanced sub rcx, 1 jmp processBracket determineBalance: cmp rcx, 0 jne unbalanced mov rsi, MsgBalanced mov rdx, MsgBalancedLen jmp displayResult unbalanced: mov rsi, MsgUnbalanced mov rdx, MsgUnbalancedLen displayResult: mov rax, 1 mov rdi, 1 syscall ret ## XBasic Translation of: JavaScript Works with: Windows XBasic ' Balanced brackets PROGRAM "balancedbrackets" VERSION "0.001" IMPORT "xst" DECLARE FUNCTION Entry() INTERNAL FUNCTION IsStringBalanced(str) INTERNAL FUNCTION Generate(n%%) ' Pseudo-random number generator ' Based on the rand, srand functions from Kernighan & Ritchie's book ' 'The C Programming Language' DECLARE FUNCTION Rand() DECLARE FUNCTION SRand(seed%%) FUNCTION Entry() PRINT "Supplied examples" DIM tests[6] tests[0] = "" tests[1] = "[]" tests[2] = "][" tests[3] = "[][]" tests[4] = "][][" tests[5] = "[[][]]" tests[6] = "[]][[]" FOR example@@ = 0 TO UBOUND(tests[]) test = tests[example@@] PRINT "The string '"; test; "' is "; IFT IsStringBalanced(test) THEN PRINT "OK." ELSE PRINT "not OK." END IF NEXT example@@ PRINT PRINT "Random generated examples" XstGetSystemTime (@msec) SRand(INT(msec) MOD 32768) FOR example@@ = 1 TO 10 test = Generate(INT(Rand() / 32768.0 * 10.0) + 1) PRINT "The string '"; test; "' is "; IFT IsStringBalanced(test) THEN PRINT "OK." ELSE PRINT "not OK." END IF NEXT example@@ END FUNCTION FUNCTION IsStringBalanced(s) paired& = 0 i%% = 1 DO WHILE i%% <= LEN(s) && paired& >= 0 c = MID(s, i%%, 1) SELECT CASE c CASE "[": INC paired& CASE "]": DEC paired& END SELECT INC i%% LOOP END FUNCTION (paired& = 0) FUNCTION Generate(n%%) opensCount%% = 0 closesCount%% = 0 ' Choose at random until n%% of one type generated generated = "" DO WHILE opensCount%% < n%% && closesCount%% < n%% SELECT CASE (INT(Rand() / 32768.0 * 2.0) + 1) CASE 1: INC opensCount%% generated = generated + "[" CASE 2: INC closesCount%% generated = generated + "]" END SELECT LOOP ' Now pad with the remaining other brackets IF opensCount%% = n%% THEN generated = generated + CHR(']', n%% - closesCount%%) ELSE generated = generated + CHR('[', n%% - opensCount%%) END IF END FUNCTION generated ' Return pseudo-random integer on 0..32767 FUNCTION Rand() #next&& = #next&& * 1103515245 + 12345 END FUNCTION USHORT(#next&& / 65536) MOD 32768 ' Set seed for Rand() FUNCTION SRand(seed%%) #next&& = seed%% END FUNCTION END PROGRAM Output: Supplied examples The string '' is OK. The string '[]' is OK. The string '][' is not OK. The string '[][]' is OK. The string '][][' is not OK. The string '[[][]]' is OK. The string '[]][[]' is not OK. Random generated examples The string '[[]][][[[]]]' is OK. The string '[]' is OK. The string '[]]][[' is not OK. The string ']]][][[]][][[[' is not OK. The string ']]]]]][[[][[][[[' is not OK. The string '[]][' is not OK. The string ']]][[][][[' is not OK. The string '][' is not OK. The string '[[]][][]' is OK. The string '[[[][[]]]]' is OK.  ## XBS const Chars:[string] = ["[","]"]; func GenerateString(Amount:number=4):string{ set Result:string = ""; <|(*1..Amount)=>Result+=Chars[math.random(0,?Chars-1)]; send Result; } func IsBalanced(String:string):boolean{ set Pairs:number = 0; <|(*(0..(?String-1)))=>(String::at(_)=="[")?(Pairs<0)?=>send false,Pairs++,=>Pairs--; send (Opens==Closes)&(Pairs==0); } repeat 10 { set s = GenerateString(math.random(2,4)*2); log({s}: {IsBalanced(s)}); } Output: ][]][]: false ][]]]]: false ][][: false [[[[]][]: false [[][]]: true [[]]: true ]][][][[: false [][]: true ][[[[]: false []]][]: false  ## XPL0 include c:\cxpl\codes; \intrinsic code declarations int N, I, C, Nest; char Str; [\Generate a string with N open brackets and N close brackets in arbitrary order N:= IntIn(0); \get number of brackets/2 from keyboard Str:= Reserve(2*N); for I:= 0 to 2*N-1 do Str(I):= ^[; C:= 0; \initialize count of "]" repeat I:= Ran(2*N); \change N random locations to "]" if Str(I) # ^] then [Str(I):= ^]; C:= C+1]; until C>=N; \Determine whether string consists of nested pairs of open/close brackets I:= 0; C:= 0; Nest:= false; while I<2*N do [if Str(I) = ^[ then C:= C+1 else C:= C-1; if C<0 then Nest:= true; ChOut(0,Str(I)); I:= I+1; ]; ChOut(0,9\tab$$;
if Nest then Text(0,"NOT ");
Text(0,"OK
");
]

Example output:

2
[]][    NOT OK
[][]    OK
3
[[][]]  OK


## Ya

@Balanced[]s // each source must be started by specifying its file name; std extension .Ya could be ommitted and auto added by compiler

// all types are prefixed by 
// definition of anything new is prefixed by \, like \MakeNew_[]s and \len
// MakeNew_[]s is Ok ident in Ya: _ starts sign part of ident, which must be ended by _ or alphanum
Char[^] \MakeNew_[]s(Int+ \len) // Char[^] and Char[=] are arrays that owns their items, like it's usally in other langs;
// yet in assignment of Char[^] to Char[=] the allocated memory is moved from old to new owner, and old string becomes empty
// there are tabs at starts of many lines; these tabs specify what in C++ is {} blocks, just like in Python
len & 1 ==0 ! // it's a call to postfix function '!' which is an assert: len must be even
Char[=] \r(len) // allocate new string of length len
// most statements are analogous to C++ but written starting by capital letter: For If Switch Ret
For Char[] \eye = r; eye // // Char[] is a simplest array of chars, which does not hold a memory used by array items; inc part of For loop is missed: it's Ok, and condition and init could also be missed
*eye++ = '['; *eye++ = '[' // fill r by "[][][]...". The only place with ; as statement delemiter: required because the statement is not started at new line.
// below is a shuffle of "[][][]..." array
For Char[] \eye = r; ++eye // var eye is already defined, but being the same Char[] it's Ok by using already exisiting var. ++eye is used: it allows use of eye[-1] inside
Int+ \at = Random(eye/Length) // Int+ is C++'s unsigned int. eye/Length: / is used for access to field, like in file path
eye[-1],eye[at] = eye[at],eye[-1] // swap using tuples; eye[-1] accesses char that is out of current array, yet it's allowed
Ret r // Ret is C's return
Bool \AreBalanced(Char[] \brackets)
Int+ \extra = 0
For ;brackets ;++brackets
Switch *brackets
'[' // it's a C++'s 'case': both 'case' and ':' are skipped being of no value; but the code for a case should be in block, which is here specifyed by tabs at next line start
++extra
']'
If !!extra // '!!' is Bool not, like all other Bool ops: && || ^^
Ret No // No and False are C's false; Yes and True are C's true
--extra
// There is no default case, which is written as ':' - so if no case is Ok then it will fail just like if being written as on the next line
//	: { 0! } // C's default: assert(0);
Ret extra == 0
// function ala 'main' is not used: all global code from all modules are executed; so below is what typically is in ala 'main'
For Int \n=10; n; --n
// below note that new var 'brackets' is created inside args of func call
//@Std/StdIO/ is used here to use Print function; else it maybe changed to Use @Std/StdIO at global level before this For loop
@Std/StdIO/Print(; "%s : %s\n" ;Char[=] \brackets = MakeNew_[]s(10) /* all bracket strings are of length 10 */; AreBalanced(brackets) ? "Ok" : "bad")
// note that starting arg of Print is missed by using ';' - default arg value is allowed to use for any arg, even if next args are written

## Yabasic

sub check_brackets(s$) local level, i for i = 1 to len(s$)
switch mid$(s$, i, 1)
case "[": level = level + 1 : break
case "]": level = level - 1 : if level < 0 break 2
end switch
next i
return level = 0
end sub

s$= "[[]][]" print s$, " = ";

if not check_brackets(s$) print "not "; print "ok" ## zkl fcn bb(bs){ while(a:=bs.span("[","]")) {bs=bs[a[1],*]} (Void!=a) } The span method finds the start and length of a balanced span. This algorithm assumes the string only contains brackets; a matched span is chopped off the front of the string and a new balanced span is searched for. Stops when the string is empty or unbalanced (span returns Void). zkl: bb("") True zkl: bb("[]") True zkl: bb("[][]") True zkl: bb("[[][]]") True zkl: bb("][") False zkl: bb("][][") False zkl: bb("[]][[]") False  ## ZX Spectrum Basic Translation of: AWK 10 FOR n=1 TO 7 20 READ s$
25 PRINT "The sequence ";s$;" is "; 30 GO SUB 1000 40 NEXT n 50 STOP 1000 LET s=0 1010 FOR k=1 TO LEN s$
1020 LET c$=s$(k)
1030 IF c$="[" THEN LET s=s+1 1040 IF c$="]" THEN LET s=s-1
1050 IF s<0 THEN PRINT "Bad!": RETURN
1060 NEXT k
1070 IF s=0 THEN PRINT "Good!": RETURN
2000 DATA "[]","][","][][","[][]","[][][]","[]][[]","[[[[[]]]]][][][]][]["