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 BalancedBrackets;
IMPORT 
  Object,
  Object:Boxed,
  ADT:LinkedList,
  ADT:Storable,
  IO,
  Out := NPCT:Console;
 
TYPE
  (* CHAR is not boxed in the standard lib *)
  (* so make a boxed char *)
  Character* = POINTER TO CharacterDesc;
  CharacterDesc* = RECORD
    (Boxed.ObjectDesc)
    c: CHAR;
  END;
 
(* Method for a boxed char *)
PROCEDURE (c: Character) INIT*(x: CHAR);
BEGIN
  c.c := x;
END INIT;
 
PROCEDURE NewCharacter*(c: CHAR): Character;
VAR
  x: Character;
BEGIN
    NEW(x);x.INIT(c);RETURN x
END NewCharacter;
 
PROCEDURE (c: Character) ToString*(): STRING;
BEGIN
  RETURN Object.NewLatin1Char(c.c);
END ToString;
 
PROCEDURE (c: Character) Load*(r: Storable.Reader) RAISES IO.Error;
BEGIN
  r.ReadChar(c.c);
END Load;
 
PROCEDURE (c: Character) Store*(w: Storable.Writer) RAISES IO.Error;
BEGIN
  w.WriteChar(c.c);
END Store;
 
PROCEDURE (c: Character) Cmp*(o: Object.Object): LONGINT;
BEGIN
  IF c.c < o(Character).c THEN RETURN -1
  ELSIF c.c = o(Character).c THEN RETURN 0
  ELSE RETURN 1
  END
END Cmp;
(* end of methods for a boxed char *)
 
PROCEDURE CheckBalance(str: STRING): BOOLEAN;
VAR
  s: LinkedList.LinkedList(Character);
  chars: Object.CharsLatin1;
  n, x: Boxed.Object;
  i,len: LONGINT;
BEGIN
  i := 0;
  chars := str(Object.String8).CharsLatin1();
  len := str.length;
  s := NEW(LinkedList.LinkedList(Character));
  WHILE (i < len) & (chars[i] # 0X) DO
    IF s.IsEmpty() THEN
      s.Append(NewCharacter(chars[i]))  (* Push character *)
    ELSE
      n := s.GetLast(); (* top character *)
      WITH 
        n: Character DO
          IF (chars[i] = ']') & (n.c = '[') THEN
            x := s.RemoveLast(); (* Pop character *)
            x := NIL
          ELSE
            s.Append(NewCharacter(chars[i]))
          END
        ELSE RETURN FALSE
      END (* WITH *)
    END;
    INC(i)
  END;
  RETURN s.IsEmpty()
END CheckBalance;
 
PROCEDURE Do;
VAR
  str: STRING;
BEGIN
  str := "[]";Out.String(str + ":> "); Out.Bool(CheckBalance(str));Out.Ln;
  str := "[][]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
  str := "[[][]]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
  str := "][";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
  str := "][][";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
  str := "[]][[]";Out.String(str + ":> ");Out.Bool(CheckBalance(str));Out.Ln;
END Do;
 
BEGIN
  Do
END BalancedBrackets.
 