Balanced brackets

Task:

Generate a string with $N opening brackets ("[") and $N closing brackets ("]"), in some arbitrary order.
Determine whether the string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest.

Examples:

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

D

<lang d>import std.stdio, std.algorithm, std.string,

      std.range, std.random, std.conv;

auto generate(int n) {

   return text(map!((i){ return "[]"[uniform(0,2)]; })(iota(n)));

}

void main() {

   foreach (i; 0 .. 14) {
       auto s = generate(i);
       writefln("%-15s is%s balanced", '"' ~ s ~ '"',
                s.balancedParens('[', ']') ? "" : " not");
   }

}</lang> Output:

""              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
"][]][][[]"     is not balanced
"[]][[]][[]"    is not balanced
"][[]]][]]]["   is not balanced
"[[]][[[[]]]]"  is balanced
"[[]][][]]]][[" is not balanced

Solution: <lang j>genBracketPairs =: ?~@+: { #&'[]' NB. bracket pairs in arbitrary order bracketDepth =: '[]' -&(+/\)/@:(=/) ] checkBalanced =: _1 -.@e. bracketDepth</lang> Examples:<lang j> 'TESTS EXPECTED'=:( a:"_`0:`[} ,&< (<'OK') = ])/ |: cut;._2 noun define (empty) OK [] OK ][ BAD [][] OK ][][ BAD ]][[ BAD [[][]] OK []][[] BAD ]]][[[ BAD [][][[]] OK [[[][[]]]] OK [][][[][]][] OK [[]][]]]][[[][ BAD ][][[][][][[]]][ BAD ][[[][]][]]][][[][ BAD ]][][]][[][[][[]][][ BAD [[[][[][]]][]]][[]]][[ BAD [[]]][]][[[[]]][[][][[]] BAD ][[][][]][[[]][[[[][]]]][] BAD ]][[][[][[[[]][[][]][[]]]]][ BAD )

  EXPECTED -: checkBalanced &> TESTS

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

The checkBalanced verb would need modification if the task was extended to include uneven numbers of opening and closing brackets.

Perl 6

<lang perl6>sub balanced($s) {

   my $l = 0;
   for $s.comb {
       when "]" {
           --$l;
           return False if $l < 0;
       }
       when "[" {
           ++$l;
       }
   }
   return $l == 0;

}

my $N = get; my $s = (<[ ]> xx $N).pick(*).join; say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</lang>

PureBasic

<lang 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 ballanced.")
 Else
   PrintN(" is not ballanced")
 EndIf

Next</lang> Output sample

[] is ballanced.
[[]] is ballanced.
[[[]]] is ballanced.
[][]]][[ is not ballanced
[][][][]][ is not ballanced

Python

<lang python>>>> def gen(N): ... txt = ['['] * N + [']'] * 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</lang>

Tcl

<lang 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}}]"

}</lang> 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

TUSCRIPT

<lang tuscript> $$ MODE DATA $$ SET brackets=*

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

[[]][][]]]][[ _____________ $$ BUILD X_TABLE brackets=*

[[(4 ]] )4
[[[ (3 ]]] )3
(2  )2
[ (1 ] )1

$$ MODE TUSCRIPT LOOP b=brackets status=CHECK_BRACKETS (b,brackets,a1,e1,a2,e2) PRINT b," ",status ENDLOOP </lang> Output:

            [ ERROR
           [] OK
           ][ ERROR
          []] ERROR
         ][][ ERROR
        ][][] ERROR
       [[[]][ ERROR
      []][[[] ERROR
     ][][][[] ERROR
    ][]][][[] ERROR
   []][[]][[] ERROR
  ][[]]][]]][ ERROR
 [[]][[[[]]]] OK
         [[]] OK
     [[[[]]]] OK
[[]][][]]]][[ ERROR
_____________ OK