Balanced brackets

Balanced brackets
You are encouraged to solve this task according to the task description, using any language you may know.

Task:

• Generate a string with $\mathrm {N}$ opening brackets (“[”) and $\mathrm {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

C++

<lang cpp>#include <algorithm>

1. include <iostream>
2. 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";
   }

}</lang> Output:

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

D

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

auto generate(int n) {

 auto r = "[]".repeat(n).dup;
 randomShuffle(r);
 return r;

}

void main() {

 foreach (i; 0 .. 9) {
   auto s = generate(i);
   writefln("%-16s %s", s, s.balancedParens('[',']') ? "OK" : "bad");
 }

}</lang> One output:

                 OK
[]               OK
[[]]             OK
]][[][           bad
]][[][[]         bad
[[[][]][]]       OK
[[]][[][]][]     OK
[]]]][[[[[]]][   bad
[[[[][[]][]]]][] OK

J

Solution: <lang j>genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order bracketDepth =: '[]' -&(+/\)/@:(=/) ] checkBalanced =: _1 -.@e. bracketDepth</lang> Examples:<lang j> (,&' ' , ('bad';'OK') {::~ checkBalanced)"1 genBracketPairs i. 10

                  OK 

][ bad ][[] bad [[[]]] OK [][[]][] OK [][[[][]]] OK []][]][]][[[ bad [[]][[][][]][] OK ]]]][[][][[[[]][ bad []]][][][[[[]][[]] bad</lang> 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 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