pyret solution to https://www.rosettacode.org/wiki/Balanced_brackets

balance.arr

fun is-balanced-int-list(lst :: List, start_sum :: Number) -> Boolean:
  doc:
  "returns true iff the running sum of a list of " 
  "integers stays nonnegative and finishes at zero."
  
  # Perhaps overly abstracting a bit, we model the balanced
  # parentheses problem in terms of a list of integers and
  # their running sum.
  #
  # For the concrete case of balancing parentheses, this effectively
  # tells us that we don't encounter a surplus of closed parentheses
  # anywhere during expression evaluation.  We could generalize this
  # function for things like making sure your account balance for
  # a bank never overdraws and eventually settles out to even.
  if start_sum < 0:
    false
  else:
    cases (List) lst:
      | empty =>
        start_sum == 0
      | link(n, rest) => 
        is-balanced-int-list(rest, start_sum + n)
    end
  end
where:
  is-balanced-int-list([list:], 0) is true
  is-balanced-int-list([list:], 1) is false
  is-balanced-int-list([list:], -1) is false
  is-balanced-int-list([list: 1, -1], 0) is true
  is-balanced-int-list([list: -1, 1], 0) is false
end

fun convert-enclosing-chars-to-ints(
    str :: String,
    open-char :: String,
    open-val :: Number,
    close-char :: String,
    close-val :: Number) -> List:
  doc: "convert a string of braces/parentheses to a list of ints"
  open-cp = string-to-code-point(open-char)
  close-cp = string-to-code-point(close-char)
  fun convert-cp(cp):
    if cp == open-cp:
      open-val
    else if cp == close-cp:
      close-val
    end
  end
  code-points = string-to-code-points(str)
  code-points.map(convert-cp)
where:
  convert-enclosing-chars-to-ints("", "[", 1, "]", -1) is [list:]
  convert-enclosing-chars-to-ints("[]", "[", 1, "]", -1) is [list: 1, -1]
  convert-enclosing-chars-to-ints("{}", "{", 2, "}", -2) is [list: 2, -2]
end
  
fun are-braces-balanced(str  :: String) -> Boolean:
  doc: "say whether a string has balanced braces similar to [[]][]"
  start-sum = 0
  ints = convert-enclosing-chars-to-ints(str, "[", 1, "]", -1)
  is-balanced-int-list(ints, start-sum)
where:
  are-braces-balanced("") is true
  are-braces-balanced("[]") is true
  are-braces-balanced("[") is false
  are-braces-balanced("]") is false
  are-braces-balanced("[[][]]") is true
  are-braces-balanced("[]][") is false
end

fun generate-test-examples(num-open :: Number, num-close :: Number) -> List:
  doc: "generate a list of strings with num-open '[' chars and num-close ']' chars"
  if (num-close == 0):
    [list: string-repeat("[", num-open)]
  else if (num-open == 0):
    [list: string-repeat("]", num-close)]
  else:
    open-prepend = lam(s): "[" + s;
    close-prepend = lam(s): "]" + s;
    open-substrs = generate-test-examples(num-open - 1, num-close)
    close-substrs = generate-test-examples(num-open, num-close - 1)
    open-substrs.map(open-prepend) + close-substrs.map(close-prepend)
  end
where:
  generate-test-examples(0, 0) is [list: ""]
  generate-test-examples(1, 0) is [list: "["]
  generate-test-examples(2, 0) is [list: "[["]
  generate-test-examples(0, 1) is [list: "]"]
  generate-test-examples(0, 2) is [list: "]]"]
  generate-test-examples(1, 1) is [list: "[]", "]["]
end

fun bool-to-str(b):
  if b:
    "Y"
  else:
    "N"
  end
end
    
check:
  for map(str from generate-test-examples(3, 3)):
    balanced = bool-to-str(are-braces-balanced(str))
    print(balanced + " " + str)
  end
end