Balanced brackets

From Rosetta Code
Jump to: navigation, search
Task
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 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.

Examples:

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

Contents

[edit] Ada

brackets.adb:

with Ada.Numerics.Discrete_Random;
with Ada.Text_IO;
with Ada.Strings.Fixed;
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
use Ada.Strings.Fixed;
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);
Ada.Text_IO.Put_Line ("Brackets");
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

[edit] Aime

integer
unbalanced(text s)
{
integer b, i;
 
b = 0;
i = 0;
while (i < length(s)) {
if (character(s, i) == '[') {
b += 1;
} else {
b -= 1;
if (b < 0) {
break;
}
}
 
i += 1;
}
 
return b;
}
 
text
generate(integer d)
{
integer i;
text s;
 
i = d;
while (i) {
s = insert(s, 0, '[');
i -= 1;
}
 
i = d;
while (i) {
s = insert(s, drand(length(s)), ']');
i -= 1;
}
 
return s;
}
 
integer
main(void)
{
integer i;
 
i = 0;
while (i < 10) {
text s;
 
s = generate(i);
o_text(s);
o_text(" is ");
if (unbalanced(s)) {
o_text("un");
}
o_text("balanced\n");
 
i += 1;
}
 
return 0;
}

Sample output:

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

[edit] ANTLR

BalancedBrackets
BalancedBrackets


[edit] 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 ']'

[edit] 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

[edit] 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
 

[edit] 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

[edit] 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

Sample output:

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

[edit] 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.

[edit] 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
\ $
^ < <$<

[edit] 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&
| 11^123+13^666+17^321:?someNumber
& (!arg:?n)+1:?N
& :?S
& whl
' (!n+-1:~<0:?n&"[" "]" !S:?S)
& whl
' ( !someNumber:>0
& 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

[edit] 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

[edit] 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

[edit] 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
string input = Console.ReadLine();
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");
 
 

[edit] 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: [][]
bad: []][[]
 ok: [[[]][]]
bad: ][[[[]][]]
 ok: [[[]][[]][]]
bad: ]][[]][[[[][]]
bad: [[]]]][]][[][[[]

[edit] 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)))))

Output:

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

[edit] 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.

[edit] 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
 


[edit] Common Lisp

 
(defun string-of-brackets (n)
(let ((result (make-string (* 2 n)))
(opening n)
(closing n))
(dotimes (i (* 2 n) result)
(setf (aref result 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: ]][[[[][]][[[[]]]]

[edit] 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

[edit] D

[edit] 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: ][]]][[[[][][][]

[edit] Imperative Version

Translation of: Perl 6
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.

[edit] Functional Style

Translation of: Haskell
import std.stdio, std.random, std.range, std.algorithm;
 
bool isBalanced(in string s, in string pars="[]") pure nothrow {
bool bal(in string t, in int nb = 0) pure nothrow {
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);
}
}

[edit] 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

[edit] 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

[edit] Elena

#define system.
#define system'routines.
#define extensions.
 
#symbol randomBrackets = &&:aLength
[
#var aBrackets := Array new &type'length:aLength &function: &&:i[ CharValue new:91 ] + Array new &type'length:aLength &function: &&:i[ CharValue new:93 ].
 
randomControl randomize:(aLength * 2) &array:aBrackets.
 
^ Summing new:(String new) foreach:aBrackets Literal.
].
 
#symbol isBalanced = &&:aLiteral
[
#var aCounter := Integer new:0.
 
control foreach:aLiteral &until: &&:aChar [ aCounter append:(aChar => "[" ? [ 1 ] "]" ? [ -1 ]) < 0 ].
 
^ (0 == aCounter).
].
 
#symbol program =
[
control from:0 &till:10 &do: &&:aLength
[
#var anStr := randomBrackets:aLength.
#var balanced := isBalanced:anStr.
 
console write:"""" write:anStr write:"""" writeLine:(balanced => true ? [ " is balanced" ] false ? [ " is not balanced" ]).
].
 
console readChar.
].
 

[edit] Erlang

 
-module( balanced_brackets ).
-export( [generate/1, is_balanced/1, task/0] ).
 
generate( N ) ->
[generate_bracket(random:uniform()) || _X <- lists:seq(1, 2*N)].
 
is_balanced( String ) -> is_balanced_loop( String, 0 ).
 
task() ->
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( true ) -> "OK";
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

[edit] 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

[edit] 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

[edit] Factor

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.

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 ;
 
readln
balanced

[edit] 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

[edit] 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

[edit] 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
 

[edit] 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

[edit] 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.Printf("%s: ", s)
var open int
for i := 0; i < len(s); i++ {
switch s[i] {
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

[edit] 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:  [[[[]]]]]][][][[

[edit] Haskell

 
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 s = printf "Good \"%s\"\n" s
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 Control.Monad.ST
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  "]]][[[][][][[][]]["
      ^

[edit] 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

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

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.

[edit] Java

Works with: Java version 1.5+
public class Brackets {
public static boolean checkBrackets(String str){
int mismatchedBrackets = 0;
for(char ch:str.toCharArray()){
if(ch == '['){
mismatchedBrackets++;
}else if(ch == ']'){
mismatchedBrackets--;
}else{
return false; //non-bracket chars
}
if(mismatchedBrackets < 0){ //close bracket before open bracket
return false;
}
}
return mismatchedBrackets == 0;
}
 
public static String generate(int n){
if(n % 2 == 1){ //if n is odd we can't match brackets
return null;
}
String ans = "";
int openBracketsLeft = n / 2;
int unclosed = 0;
while(ans.length() < n){
if(Math.random() >= .5 && openBracketsLeft > 0 || unclosed == 0){
ans += '[';
openBracketsLeft--;
unclosed++;
}else{
ans += ']';
unclosed--;
}
}
return ans;
}
 
public static void main(String[] args){
String[] tests = {"", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"};
for(int i = 0; i <= 16; i+=2){
String bracks = generate(i);
System.out.println(bracks + ": " + checkBrackets(bracks));
}
 
for(String test: tests){
System.out.println(test + ": " + checkBrackets(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

[edit] JavaScript

 
function createRandomBracketSequence(maxlen)
{
var chars = { '0' : '[' , '1' : ']' };
function getRandomInteger(to)
{
return Math.floor(Math.random() * (to+1));
}
var n = getRandomInteger(maxlen);
var result = [];
for(var i = 0; i < n; i++)
{
result.push(chars[getRandomInteger(1)]);
}
return result.join("");
}
 
function bracketsAreBalanced(s)
{
var open = (arguments.length > 1) ? arguments[1] : '[';
var close = (arguments.length > 2) ? arguments[2] : ']';
var c = 0;
for(var i = 0; i < s.length; i++)
{
var ch = s.charAt(i);
if ( ch == open )
{
c++;
}
else if ( ch == close )
{
c--;
if ( c < 0 ) return false;
}
}
return c == 0;
}
 
var c = 0;
while ( c < 5 ) {
var seq = createRandomBracketSequence(8);
alert(seq + ':\t' + bracketsAreBalanced(seq));
c++;
}
 

Output:

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


Recursively remove occurrences of '[]':

 
function checkBalance(i) {
while (i.length % 2 == 0) {
j = i.replace('{}','');
if (j == i)
break;
i = j;
}
return (i?false:true);
}
 
var g = 10;
while (g--) {
var N = 10 - Math.floor(g/2), n=N, o='';
while (n || N) {
if (N == 0 || n == 0) {
o+=Array(++N).join('}') + Array(++n).join('{');
break;
}
if (Math.round(Math.random()) == 1) {
o+='}';
N--;
}
else {
o+='{';
n--;
}
}
alert(o+": "+checkBalance(o));
}
 

[edit] Julia

function balanced(str)
i = 0
for c in str
if c == '[' i +=1 elseif c == ']' i -=1 end
if i < 0 return false end
end
i == 0 ? true : false
end
 
brackets(n) = CharString(shuffle([("[]"^n)...]))
 
print(map(x -> (x, balanced(x)), [brackets(i) for i = 0:8]))
 
Output:
("",true)
("][",false)
("][[]",false)
("[[][]]",true)
("]][[[]][",false)
("[[]]][[][]",false)
("[[][[]][]][]",true)
("]]][][[[][][[]",false)
("[[[[[][]]]]]][[]",false)

Starting with Julia v0.3, a foldl function is available, so that balanced may be written shortly (but not as efficiently) as follows:

balanced(str) = foldl((x,y)->x<0? -1: x+y, 0, [(x=='[')-(x==']') for x=str])==0

[edit] 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

[edit] 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.


[edit] 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))
 

[edit] 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
 

[edit] Mathematica

 
(* 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."]])
 

[edit] 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

[edit] 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

[edit] 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

[edit] 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

[edit] 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

[edit] 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
 

[edit] 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")))

[edit] Pascal

See Delphi

[edit] 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;
}

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
}

[edit] Perl 6

There's More Than One Way To Do It.

[edit] Depth counter

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).pick(*).join;
say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"

[edit] 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;
}
 
my $n = prompt "Number of bracket pairs: ";
my $s = <[ ]>.roll($n*2).join;
say "$s { balanced($s) ?? "is" !! "is not" } well-balanced"

[edit] String munging

Of course, a Perl 5 programmer might just remove as many inner balanced pairs as possible and then see what's left.

sub balanced($_ is copy) {
() while s:g/'[]'//;
$_ eq '';
}
 
my $n = prompt "Number of bracket pairs: ";
my $s = <[ ]>.roll($n*2).join;
say "$s is", ' not' xx not balanced($s)), " well-balanced";

[edit] Parsing with a grammar

grammar BalBrack { token TOP { '[' <TOP>* ']' } }
 
my $n = prompt "Number of bracket pairs: ";
my $s = ('[' xx $n, ']' xx $n).pick(*).join;
say "$s { BalBrack.parse($s) ?? "is" !! "is not" } well-balanced";

[edit] 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

[edit] 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 '][[][[[[[]'

[edit] 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.

[edit] 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

[edit] Python

>>> 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

[edit] 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 "[]][[]")
 
 


[edit] 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(permute(c(rep('[',n),rep(']',n))),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 []

[edit] 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))
 

[edit] REXX

[edit] Version 1

/*REXX program to check for balanced brackets   []                      */
@.=0
yesno.0 = left('',40) 'unbalanced'
yesno.1 = 'balanced'
 
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
 
do j=1 for 40
q=translate(rand(random(1,8)),'[]',01)
call checkBal q; if result=='-1' then iterate
say yesno.result q
end
exit
/*───────────────────────────────────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 subroutine────────────────*/
checkBal: procedure expose @.; arg y /*check for balanced brackets [] */
nest=0; if @.y then return '-1' /*already done this expression ? */
@.y=1 /*indicate expression processed. */
do j=1 for length(y); _=substr(y,j,1) /*pick off character.*/
if _=='[' then nest=nest+1
else do; nest=nest-1; if nest<0 then return 0; end
end /*j*/
return nest==0

output (not repeatable due to the use of RANDOM:

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

[edit] Version 2

 
/*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 */
 

[edit] version 3

This REXX version (in addition to some standard examples), 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 (brackets) 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.

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 to check for balanced brackets    [ ]                    */
count=0
nested=0
yesno.0 = left('',40) 'unbalanced'
yesno.1 = 'balanced'
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
q=']]][[[[]'  ; call checkBal q; say yesno.result q
call teller
count=0
nested=0
do j=1 /*generate lots of permutations. */
q=translate(strip(x2b(d2x(j)),'L',0),"][",01) /*convert──►[].*/
if countstr(']',q)\==countstr('[',q) then iterate /*compliant?*/
call checkBal q
if length(q)>20 then leave /*done all 20-char possibilities?*/
end
/*───────────────────────────────────TELLER subroutine──────────────────*/
teller: say
say count " expressions were checked, " nested ' were balanced, ',
count-nested " were unbalanced."
return
/*───────────────────────────────────CHECKBAL subroutine────────────────*/
checkBal: procedure expose nested count; parse arg y; count=count+1
nest=0
do j=1 for length(y); _=substr(y,j,1) /*pick off character.*/
select
when _=='[' then nest=nest+1 /*opening bracket ...*/
when _==']' then do; nest=nest-1; if nest<0 then leave; end
otherwise nop /*ignore any chaff. */
end /*select*/
end /*j*/
nested=nested + (nest==0)
return nest==0
/* ┌──────────────────────────────────────────────────────────────────┐
│ COUNTSTR counts the number of occurances of a string (or char)│
│ within another string (haystack) without overlap. If either arg │
│ is null, 0 (zero) is returned. To make the subroutine case │
│ insensative, change the PARSE ARG ... statement to ARG ... │
│ Example: yyy = 'The quick brown fox jumped over the lazy dog.' │
│ zz = countstr('o',yyy) /*ZZ will be set to 4 */

│ Note that COUNTSTR is also a built-in function of the newer │
│ REXX interpreters, and the result should be identical. Checks │
│ could be added to validate if 2 or 3 arguments are passed.
└──────────────────────────────────────────────────────────────────┘ */
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

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

14  expressions were checked,  6  were balanced,  8  were unbalanced.

125477  expressions were checked,  23713  were balanced,  101764  were unbalanced.

[edit] 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]

[edit] 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 []][][][[]

[edit] Scala

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

[edit] 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: ]]]]][[[[[

[edit] Scala Version 2

Works with: Scala version 2.10.1
import scala.util.Random
 
object BalancedParensApp extends App {
 
val triesCount = 10
 
(0 until triesCount).foreach { i =>
val str = randomString(length = i)
val msg = if (isBalanced(str)) "ok" else "NOT ok"
println(s"$str - $msg")
}
 
def randomString(length: Int) = {
val parensPairs = ("[]" * length).toSeq
val parensOfGivenLength = parensPairs.take(length)
val shuffledParens = Random.shuffle(parensOfGivenLength)
shuffledParens.mkString
}
 
def isBalanced(parensString: String): Boolean = {
var balance = 0
parensString.foreach { char =>
char match {
case '[' => balance += 1
case ']' => balance -= 1
}
if (balance < 0) return false;
}
balance == 0
}
 
}

Sample output:

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

[edit] Scheme

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

[edit] Seed7

$ 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

[edit] Sidef

func balanced (str) {
 
var depth = 0;
str.each { |c|
if(c=='['){ depth++ }
elsif(c==']'){ depth-- < 0 && (return(false)) }
};
 
return (!depth);
}
 
[']','[','[[]','][]','[[]]','[[]]]][][]]','x[ y [ [] z ]][ 1 ][]abcd'].each {
|str|
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

[edit] 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

[edit] 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 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).

[edit] 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 

[edit] TXR

@(define paren)@(maybe)[@(coll)@(paren)@(until)]@(end)]@(end)@(end)
@(do (defvar r (make-random-state nil))
(defun shuffle (list)
(for* ((vec (vector-list list))
(len (length vec))
(i 0))
((< i len) (list-vector vec))
((inc i))
(let ((j (random r len))
(temp (vecref vec i)))
(set (vecref vec i) (vecref vec j))
(set (vecref vec j) temp))))
(defun generate-1 (count)
(for ((i 0) chars) ((< i count) (cat-str (shuffle chars) "")) ((inc i))
(push #\[ chars)
(push #\] chars)))
(defun generate-list (num count)
(for ((i 0) list) ((< i num) list) ((inc i))
(push (generate-1 count) list))))
@(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
][[[]][][[]]                    ][[[]][][[]]   
[]][[]][][[]    []              ][[]][][[]     
[][[[[]]]]][    []              [[[[]]]]][     
][[][[]]][][                    ][[][[]]][][   
[[[][[]]][]]    [[[][[]]][]]                   
]][]][[[][[]                    ]][]][[[][[]   
[[]][]][[[]]    [[]]            []][[[]]       
]][]][]][[[[                    ]][]][]][[[[   
]][[]]][][[[                    ]][[]]][][[[   
]]]][[]][[[[                    ]]]][[]][[[[   
][[[[][[]]]]                    ][[[[][[]]]]   
][]][]]][[[[                    ][]][]]][[[[   
]][][[][][[]                    ]][][[][][[]   
]][][]][[][[                    ]][][]][[][[   
[][[]][]]][[    []              [[]][]]][[     
[[]]]]][[[[]    [[]]            ]]][[[[]       
]][[[[[[]]]]                    ]][[[[[[]]]]   
][][][[[]][]                    ][][][[[]][]   
[]][]][][][[    []              ][]][][][[     
]][[[][]][[]                    ]][[[][]][[]   
][[[[]]]][][                    ][[[[]]]][][   
[[]]]]][[][[    [[]]            ]]][[][[       

[edit] 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>

[edit] 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

[edit] 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

[edit] 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
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox