Check Matching Brackets in OCaml Example

In OCaml, implement a tail-recursive function check_brackets : string -> bool such that check_brackets s is true if and only if the brackets (), {} and [] are paired up properly in s.

Solution

To solve this problem, we need to traverse the input string and check whether each opening and closing bracket is valid. When an opening bracket (, { or [ is encountered, it must be closed by ), } and ] respectively. That is, whenever a closing bracket is encountered, it must have been preceeded by the corresponding opening bracket.

The string traversal is handled using an index i ranging from 0 to String.length s. A stack of characters is leveraged to keep track of the opening brackets encountered, in first in, first out order. When a closing bracket is encountered, this stack can be peeked at to check if the latest opening bracket is indeed the correct one. Once the input string is fully traversed, we need to ensure that there are no leftover opening brackets in the stack.

let check_brackets : string -> bool =
  let rec aux : string -> int -> int -> char list -> bool =
    fun s i n bs ->
      if i < n then
        match bs, s.[i] with
        | _, ('(' as b)
        | _, ('{' as b)
        | _, ('[' as b) ->
          (* Encountered a new opening bracket *)
          aux s (i + 1) n (b :: bs)
        | '(' :: bs', ')'
        | '{' :: bs', '}'
        | '[' :: bs', ']' ->
          (* Encountered a valid closing bracket *)
          aux s (i + 1) n bs'
        | _, ')'
        | _, '}'
        | _, ']' ->
          (* Encountered an invalid closing bracket *)
          false
        | _ ->
          (* Fallback to continuing the string traversal *)
          aux s (i + 1) n bs
      else
        match bs with
        | [] ->
          (* There are no leftover opening brackets *)
          true
        | _ :: _ ->
          (* There are leftover opening brackets *)
          false
  in
  fun s -> aux s 0 (String.length s) []