A typical bracket balanced problem in ocaml

Question

I'm trying to create a function which returns a boolean value to see if the string is balanced. But the result is just not what I expect. Can someone point out what I did wrong?

For example:

false = is_balanced")("
false = is_balanced "(a)b)"
true = is_balanced "fo"
true = is_balanced "a(b(c)d)e"

let rec list_car ch = match ch with
  | "" -> []
  | ch -> (String.get ch 0 ) :: (list_car (String.sub ch 1 ( (String.length ch)-1) ) )  ;;

let is_balanced klm =
  let brk = list_car klm in
  let rec left = function
    | x::xs, 0 -> 
      if x = ')' then false 
      else left (xs, 0)
    | x::xs, level -> 
      if x = '(' then left (xs, succ level) 
      else if x = ')' then left (xs, pred level) 
      else left (xs, level)
    | [], level -> if level = 0 then true else false
  in 
  left (brk, 0) ;;

But I got the following results:

is_balanced "(((";;
- : bool = true
 is_balanced "()";;
- : bool = false

Answer 1

Presented as an alternative, this is a good opportunity to gain experience with folds. They work well in any situation where you are iterating over something one element at a time and need to evaluate that element in conjunction with an initial state to generate a new value.

The state we'll keep track of is the nesting level. It'll start out as 0. Each iteration, if it's less than 0, the nesting is obviously unbalanced. No further elements from the string will balance the parens, so we'll simply propagate this value to the end of the fold, resulting in a false return.

Otherwise we'll increment or decrement the levels as we encounter open and close parens. Or take no action for non-paren characters.

let balanced str =
  let f level ch =
    if level < 0 then 
      level
    else 
      match ch with
      | '(' -> level + 1
      | ')' -> level - 1
      | _   -> level
  in
  String.fold_left f 0 str = 0

# balanced ")(";;
- : bool = false
# balanced "(a)b)";;
- : bool = false
# balanced "fo";;
- : bool = true
# balanced "a(b(c)d)e";;
- : bool = true

Consider how this operates on "(a)b)":

balanced "(a)b)"
String.fold_left f 0 "(a)b)"
String.fold_left f 1 "a)b)"
String.fold_left f 1 ")b)"
String.fold_left f 0 "b)"
String.fold_left f 0 ")"
String.fold_left f -1 ""
-1
-1 = 0
false

If we look at "a(b(c)d)e":

balanced "a(b(c)d)e"
String.fold_left f 0 "a(b(c)d)e"
String.fold_left f 0 "(b(c)d)e"
String.fold_left f 1 "b(c)d)e"
String.fold_left f 1 "(c)d)e"
String.fold_left f 2 "c)d)e"
String.fold_left f 2 ")d)e"
String.fold_left f 1 "d)e"
String.fold_left f 1 ")e"
String.fold_left f 0 "e"
String.fold_left f 0 ""
0
0 = 0
true

The propagation of the negative level value can be seen if we test "())hello()":

balanced "())hello()"
String.fold_left f 0 "())hello()"
String.fold_left f 1 "))hello()"
String.fold_left f 0 ")hello()"
String.fold_left f -1 "hello()"
String.fold_left f -1 "ello()"
String.fold_left f -1 "llo()"
String.fold_left f -1 "lo()"
String.fold_left f -1 "o()"
String.fold_left f -1 "()"
String.fold_left f -1 ")"
String.fold_left f -1 ""
-1
-1 = 0
false

One note about this approach: it does not short circuit. A string that starts with ) will clearly result in false but the entire string will need to be iterated over.

One way around this would be to have our locally scoped f function raise an exception on level being negative, and then to handle this exception by returning false.

exception Unbalanced_parens

let balanced str =
  let f level ch =
    if level < 0 then 
      raise Unbalanced_parens
    else 
      match ch with
      | '(' -> level + 1
      | ')' -> level - 1
      | _   -> level
  in
  match String.fold_left f 0 str with
  | 0 -> true
  | _ | exception Unbalanced_parens -> false

Now, if we test "())hello()":

balanced "())hello()"
String.fold_left f 0 "())hello()"
String.fold_left f 1 "))hello()"
String.fold_left f 0 ")hello()"
String.fold_left f -1 "hello()"
raise Unbalanced_parens
false

We can make this function much more generic by having it accept a first class module which must describe an ordered type which can be used to create a map, a sequence of values of that type, and a sequence of open and close tokens.

let balanced 
    (type a) 
    (module S : Map.OrderedType with type t = a) 
    seq 
    tokens =
  let exception Unbalanced in
  let module M = Map.Make (S) in
  let open_map = 
    tokens |> M.of_seq
  in
  let close_map =
    tokens |> Seq.map (fun (a, b) -> (b, a)) |> M.of_seq
  in
  seq
  |> Seq.filter (fun x -> M.mem x open_map || M.mem x close_map)
  |> Seq.fold_left 
       (fun prev tok -> 
          let is_open_tok = M.mem tok open_map in
          let is_close_tok = not is_open_tok in
          match prev with 
          | _ when is_open_tok -> tok :: prev
          | x::xs when is_close_tok && M.find tok close_map = x -> xs
          | _ -> raise Unbalanced)
       []
  |> (=) []

Your version is then simply an application of this function:

let balanced str =
  balanced 
    (module Char) 
    (String.to_seq str) 
    (List.to_seq [('(', ')')])

Answer 2

Now I fixed mt code,and it works!Thanks a lot for the tipps

let rec list_car ch = 
  match ch with
  | "" -> []
  | ch -> String.get ch 0 :: list_car (String.sub ch 1 (String.length ch - 1))

let is_balanced klm =
  let brk = list_car klm in
  let rec left = function
    | ')'::xs, level ->
      if level > 0 then left (xs, pred level) else false
    | '('::xs, level -> left (xs, succ level)
    | _::xs, level -> left (xs, level)
    | [], level -> if level = 0 then true else false
  in 
  left (brk, 0)

Answer 3

When learning to program, it's important not only to learn programming techniques (such as algorithms) and programming languages, but also tools.

You're confronted with a problem: you've written some code that takes some input and returns the wrong input, but you don't understand why. There are two main approaches to this kind of problem:

• Break down the code into smaller pieces, and test them separately, until you find one (or more) that doesn't return the outputs you wanted.
• Use debugging tools to look at what's happening inside the program.

Here you can test list_car independently and see that it's not the source of the problem. There's not much you can do to break down is_balanced, but you can take out left and make it a top-level function.

let rec left = function
    | x::xs, 0 -> 
      if x = ')' then false 
      else left (xs, 0)
    | x::xs, level -> 
      if x = '(' then left (xs, succ level) 
      else if x = ')' then left (xs, pred level) 
      else left (xs, level)
    | [], level -> if level = 0 then true else false
;;
let is_balanced klm =
  let brk = list_car klm in
  left (brk, 0) ;;

That's not going to help directly, because the problem is inside left and it's all one thing that can't really be broken down into smaller pieces. However, making left a toplevel function allows you to use a simple debugging tool: tracing in the toplevel. (A function doesn't have to be at the top level to debug it, but it does to use the toplevel's simple tracing function.)

# #trace left;;
left is now traced.
# is_balanced "()";;
left <-- (['('; ')'], 0)
left <-- ([')'], 0)
left --> false
left --> false

Now you can see where the code is going wrong: the second call to left is made with the level 0, but it should be 1 since the previous call opened a parenthesis. So the problem is that left (['('; ')'], 0) is passing the wrong level value when it makes its recursive call.

    | x::xs, 0 -> 
      if x = ')' then false 
      else left (xs, 0)
                     ^

Now that you've located the problem, the correction should be obvious: in the recursive call, you need to remember the number of opening parentheses somehow — that's what level is for. So level here should be 1, not 0.

let rec left = function
    | x::xs, 0 -> 
      if x = ')' then false 
      else left (xs, 1)
    | x::xs, level -> 
      if x = '(' then left (xs, succ level) 
      else if x = ')' then left (xs, pred level) 
      else left (xs, level)
    | [], level -> if level = 0 then true else false
;;
let is_balanced klm =
  let brk = list_car klm in
  left (brk, 0) ;;

(Remember that in the toplevel, after redefining left, you need to redefine is_balanced as well, even if its textual definition hasn't changed: the old definition refers to the old definition of left.)

I think is_balanced is now correct for inputs that consists solely of parentheses. It doesn't properly ignore other characters, but I'll let you debug that on your own. It may help to write the code in a simpler way, taking advantage of the fact that you can match on the first element of the list, on the level, or both. For example, the incorrect case above was actually unnecessary: you could have made the first case

    | ')'::xs, 0 -> false

and the second case already handles lists starting with ( correctly: when the first character is (, the logic is the same regardless of the value of the level.

Answer 4

I believe the problem is with this line:

  |x::xs,0-> if x =')'then false else left(xs,0)

Here, if x is not ), the character is simply ignored. Hence, if it is instead (, level will not be incremented.

The quick fix is to instead match the character directly:

  | ')'::xs, 0 -> false

But I fully agree with @octachron's advice, and that the problem would have been avoided by not mixing list iteration and level counting.

Also, note that you can use when to attach a condition to a branch. For example, if you match on just the list, you could instead do:

  | ')'::xs when level = 0 -> false

And you could also do

  | ')'::xs when level < 0 -> false

which is unnecessary in this case, but serves to demonstrate a case that cannot be covered by pattern matching on level directly.

Answer 5

Exploding a string into a list of char by using String.sub is inefficient and unnecessary. Your code can be rewritten as

let is_balanced s =
  let rec count pos level =
    if (* termination condition *) ... then level = 0 
    else match s.[pos] with
     | '(' -> ...
     | ')' -> ...
     | _  -> ...
   in
   count 0 0

With this variant, your mistake should disappear by itself.

Indeed one possible root issue with your previous code is that you are matching on both the list of chars and the level and end up mixing the logic of the termination condition with the logic of the level counting.

In particular, should the level at position n influence the effect of characters on the level at the position n+1?