extra/rosetta-code/balanced-brackets/balanced-brackets.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators kernel math sequences ;
   4 IN: rosetta-code.balanced-brackets
   5
   6 ! http://rosettacode.org/wiki/Balanced_brackets
   7
   8 ! Task:
   9
  10 ! Generate a string with N opening brackets (“[”) and N closing
  11 ! brackets (“]”), in some arbitrary order.
  12
  13 ! Determine whether the generated string is balanced; that is,
  14 ! whether it consists entirely of pairs of opening/closing
  15 ! brackets (in that order), none of which mis-nest.
  16
  17 ! Examples:
  18
  19 ! (empty)   OK
  20 ! []        OK   ][        NOT OK
  21 ! [][]      OK   ][][      NOT OK
  22 ! [[][]]    OK   []][[]    NOT OK
  23
  24 :: balanced? ( str -- ? )
  25     0 :> counter!
  26     t :> ok!
  27     str [
  28         {
  29             { CHAR: [ [ 1 ] }
  30             { CHAR: ] [ -1 ] }
  31             [ drop 0 ]
  32         } case counter + counter!
  33         counter 0 < [ f ok! ] when
  34     ] each
  35     ok [ counter 0 <= ] [ f ] if ;