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.
:- interface.
 
:- import_module io.
 
:- pred main(io::di, io::uo) is det.
 
 
:- import_module list, random, char.
 
:- pred brackets(int::in,list(char)::out,supply::mdi,supply::muo) is det.
 
:- pred imbalance(list(char)::in,int::out) is semidet.
:- pred balanced(list(char)::in) is semidet.
 
:- implementation.
 
:- import_module int.
 
imbalance([],0).
imbalance(['['|T],N) :- imbalance(T,N+1).
imbalance([']'|T],N) :- N > 0, imbalance(T,N-1).
 
balanced(S) :- imbalance(S,0).
 
brackets(N,S,!RS) :-
    (
	N < 1 -> S is []
    ;   random(0,2,R,!RS),
	( R is 0 -> S is ['['|T], brackets(N-1,T,!RS)
	; S is [']'|T], brackets(N-1,T,!RS))).
 
main(!IO) :-
    random.init(0,RS),
    brackets(4,S,RS,_),
    print(S,!IO),
    (
	balanced(S) -> print(" is balanced\n",!IO)
    ;   print(" is unbalanced\n", !IO)
    ).
 