Avatar of barisere

barisere's solution

to Matching Brackets in the OCaml Track

Published at Sep 22 2019 · 0 comments
Instructions
Test suite
Solution

Given a string containing brackets [], braces {}, parentheses (), or any combination thereof, verify that any and all pairs are matched and nested correctly.

Getting Started

  1. Install the Exercism CLI.

  2. Install OCaml.

  3. For library documentation, follow Useful OCaml resources.

Running Tests

A Makefile is provided with a default target to compile your solution and run the tests. At the command line, type:

make

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

Feedback, Issues, Pull Requests

The exercism/ocaml repository on GitHub is the home for all of the Ocaml exercises.

If you have feedback about an exercise, or want to help implementing a new one, head over there and create an issue or submit a PR. We welcome new contributors!

Source

Ginna Baker

test.ml

open Base
open OUnit2
open Matching_brackets

let ae exp got _test_ctxt =
  assert_equal exp got ~printer:Bool.to_string

let tests = [
  "paired square brackets" >::
  ae true (are_balanced "[]");
  "empty string" >::
  ae true (are_balanced "");
  "unpaired brackets" >::
  ae false (are_balanced "[[");
  "wrong ordered brackets" >::
  ae false (are_balanced "}{");
  "wrong closing bracket" >::
  ae false (are_balanced "{]");
  "paired with whitespace" >::
  ae true (are_balanced "{ }");
  "partially paired brackets" >::
  ae false (are_balanced "{[])");
  "simple nested brackets" >::
  ae true (are_balanced "{[]}");
  "several paired brackets" >::
  ae true (are_balanced "{}[]");
  "paired and nested brackets" >::
  ae true (are_balanced "([{}({}[])])");
  "unopened closing brackets" >::
  ae false (are_balanced "{[)][]}");
  "unpaired and nested brackets" >::
  ae false (are_balanced "([{])");
  "paired and wrong nested brackets" >::
  ae false (are_balanced "[({]})");
  "paired and incomplete brackets" >::
  ae false (are_balanced "{}[");
  "too many closing brackets" >::
  ae false (are_balanced "[]]");
  "math expression" >::
  ae true (are_balanced "(((185 + 223.85) * 15) - 543)/2");
  "complex latex expression" >::
  ae true (are_balanced "\\left(\\begin{array}{cc} \\frac{1}{3} & x\\\\ \\mathrm{e}^{x} &... x^2 \\end{array}\\right)");
]

let () =
  run_test_tt_main ("matching-brackets tests" >::: tests)
open Base
;;

let try_pop_char stack c =
  match Stack.pop stack with
  | Some c' when Char.(c' = c) -> Some c
  | Some c' -> Stack.push stack c'; None
  | _ -> None
;;

let lex_brackets s =
  let consume_tokens stack s =
    String.foldi ~init:(Ok s) ~f:(fun i acc c ->
        let map_pop_error = function
          | Some _ -> acc
          | None -> Error(i, c)
        in
        if Result.is_error acc then acc else
          match c with
          | '(' | '{' | '[' -> Stack.push stack c; acc
          | ')' -> try_pop_char stack '(' |> map_pop_error
          | '}' -> try_pop_char stack '{' |> map_pop_error
          | ']' -> try_pop_char stack '[' |> map_pop_error
          | _ -> acc
      ) s
  in
  let symbols = Stack.create () in
  Result.(consume_tokens symbols s >>= (fun s' -> match Stack.top symbols with
      | Some s -> Error(0, s)
      | None -> Ok s'))
;;

let are_balanced s = Result.is_ok (lex_brackets s)
;;

Community comments

Find this solution interesting? Ask the author a question to learn more.

barisere's Reflection

Starting the solution by drawing a state machine for it helped keep the strategy clear in my head. I suspect this solution can be made simpler, but I've moved on from it.