Task:

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


Examples

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



 
MODULE Brackets;
IMPORT IO, Lib;
 
CONST MaxN = 4;
 
PROCEDURE DoTest( N : CARDINAL);
VAR
  brStr : ARRAY [0..2*MaxN] OF CHAR; (* string of brackets *)
  verdict : ARRAY [0..2] OF CHAR;
  br : CHAR;
  k, nL, nR, randNum : CARDINAL;
  count : INTEGER;
BEGIN
  k := 0; (* index into brStr *)
  nL := N; nR := N; (* number of left/right brackets remaining *)
  WHILE (nL > 0) AND (nR > 0) DO
    randNum := Lib.RANDOM( nL + nR);
    IF (randNum < nL) THEN brStr[k] := '['; DEC(nL);
                      ELSE brStr[k] := ']'; DEC(nR); END;
    INC(k);
  END;
  (* Here when only one kind of bracket is possible *)
  IF (nL = 0) THEN br := ']' ELSE br := '['; END;
  WHILE (k < 2*N) DO brStr[k] := br; INC(k); END;
  brStr[k] := 0C; (* null to mark end of string *)
 
  (* Test for balance *)
  count := 0;
  k := 0;
  REPEAT
    IF brStr[k] = '[' THEN INC( count) ELSE DEC( count) END;
    INC( k);
  UNTIL (count < 0) OR (k = 2*N);
  IF (count < 0) THEN verdict := 'no' ELSE verdict := 'yes' END;
  IO.WrStr( brStr); IO.WrStr(' '); IO.WrStr( verdict);
  IO.WrLn;
END DoTest;
 
(* Main routine *)
VAR
  j : CARDINAL;
BEGIN
  Lib.RANDOMIZE;
  FOR j := 1 TO 10 DO
    DoTest( Lib.RANDOM(MaxN) + 1);
  END;
END Brackets.
 