text: Balanced Delimiters
  June 10, 2014
  Although the interviewer didn’t say so explicitly, the task is to write a function that determines if the parentheses, brackets and braces are properly balanced in a string. Here’s our solution, which copies opening parentheses, brackets and braces into a stack and matches the corresponding closing parentheses, brackets and braces, discarding everything else:
  (define (balanced? str) (let ((starters '(#\( #\[ #\{)) (enders '(#\) #\] #\}))) (let loop ((cs (string->list str)) (xs (list))) (cond ((null? cs) (null? xs)) ; #t if stack is empty, or #f ((member (car cs) starters) ; push starter on stack (loop (cdr cs) (cons (car cs) xs))) ((member (car cs) enders) ; pop matching ender from stack, or #f (and (pair? xs) (or (and (char=? (car xs) #\() (char=? (car cs) #\))) (and (char=? (car xs) #\[) (char=? (car cs) #\])) (and (char=? (car xs) #\{) (char=? (car cs) #\}))) (loop (cdr cs) (cdr xs)))) (else (loop (cdr cs) xs)))))) ; neither starter nor ender
  A programmer with a recent computer science degree will immediately recognize the problem of balanced delimiters and know to use a stack; the self-taught programmer, or one who didn’t pay attention at school, or one who’s been out of school for a while, will have more trouble answering the interviewer.
  You can run the program at, where you will also see that it passes all of the interviewer’s test cases.
  The previous exercise used a finite state machine to match consecutive identical characters. Although today’s exercise seems similar, it can’t be solved by a simple finite state machine because matches are permitted to be nested; a finite state machine can’t count the matches. That’s why we need the stack.
  […] all programming interview questions, this one is contrived… and it is also succinct, precise, pleasant, and […]
  You can simplify the code by starting with a sentinel character (e.g. #\*) on the stack instead of an empty stack. Then you can skip the null stack check when you encounter a closing character. After the last character instead of checking for an empty stack you then need to check that the top of the stack is the sentinel character.
  And using an association list to associate the closing character to the opening character would be more elegant than the two parallel lists and three branches of the or.
  The following code incorporates those ideas:
  I remember implementing a similar algorithms while writing a compiler for my master thesis.
  Here is my suggestion in C#, just copied from LinqPAD:
  —————));
  }
  ——————
  Some code got clipped out, sorry, here is the complete version:
  —–));
  }
  Use the call stack as the bracket matching stack:
  The iterative solution seems simplest, but a recursive solution can also be written. Here’s a comparison of the two in Python:
  Why would you implement this recursively if the result is more difficult to understand and cannot be optimized using tail-recursion to provide the same performance as the iterative version? Good question.
  A side-note is that the above can be used with any sequence and appropriately typed delimiters, not just string/characters.
  Pattern-matching ML-style is nice (this only does the brackets, not other symbols):
  And a very simple Markov program:
  Now for something completely different.
  @Mike – nice, but not that different to my Markov program.
  Actually, I don’t need all those silly rules for termination – Markov programs terminate if no rules apply, so we can just have:
  An imperative Python solution:
  1 def pop(s, x):
  2 y = s.pop()
  3 return x == y
  4
  5 def is_balanced(xs):
  6 s = ['b']
  7 for x in xs:
  8 if x in '{([': s.append(x)
  9 elif x == '}':
  10 if not pop(s, '{'): return False
  11 elif x == ')':
  12 if not pop(s, '('): return False
  13 elif x == ']':
  14 if not pop(s, '['): return False
  15 return s == ['b']
  A solution in Haskell:
  1 isBalanced xs = scan xs "b" where
  2 scan [] ys = ys == "b"
  3 scan (x:xs) ys
  4 | x `elem` "{([" = scan xs (x:ys)
  5 | x `elem` "})]" = case (head ys) of
  6 '{' -> x == '}'
  7 '(' -> x == ')'
  8 '[' -> x == ']'
  9 'b' -> False
  10 && scan xs (tail ys)
  11 | otherwise = scan xs ys
  Not the shortest code, but I tried to make it very readable. In Perl, as usual :).
  Tested with the input given:
  A Haskell solution to add to the list:
  import Control.Arrow ((&&&))
  import Data.Maybe (fromJust)
  import qualified Data.Map as M
  import qualified Data.Set as S
  pairs :: M.Map Char Char
  pairs = M.fromList [(‘)’, ‘(‘), (‘]’, ‘[‘), (‘}’, ‘{‘)]
  open :: S.Set Char
  open = S.fromList . M.elems $ pairs
  shut :: S.Set Char
  shut = M.keysSet pairs
  ok :: String -> Bool
  ok = f []
  where
  f s [] = null s
  f s (c:cs) | S.member c open = f (c:s) cs
  | S.member c shut && g s c = f (tail s) cs
  | otherwise = f s cs
  g s c = not (null s) && (head s == fromJust (M.lookup c pairs))
  main :: IO ()
  main = mapM_ (print . (id &&& ok)) . words $
  “{} [] () a(b)c abc[d] a(b)c{d[e]} {] (] a(b]c abc[d} a(b)c{d[e}]”
  [/sourcecocde]
  Apologies for the typo! It’s been a while since I posted here, apparently.
  #A solution in `Ruby`
  “`ruby
  def balanced?(string)
  delim_pairs = [[“(“, “)”], [“[“, “]”], [“{“, “}”]]
  stack = []
  string.split(“”).each do |char|
  head = stack.empty? ? nil : stack[-1]
  delim_pairs.each do |pair|
  if char == pair[0]
  stack < [true, true, true, true, true, true]
  fails = [“{]”, “(]”, “a(b]c”, “abc[d}”, “a(b)c{d[e}]”].map { |x| balanced? x }
  puts fails.inspect #==> [false, false, false, false, false]
  “`
  def balanced?(string)
  delim_pairs = [[“(“, “)”], [“[“, “]”], [“{“, “}”]]
  stack = []
  string.split(“”).each do |char|
  head = stack.empty? ? nil : stack[-1]
  delim_pairs.each do |pair|
  if char == pair[0]
  stack << char
  elsif char == pair[1] && head == pair[0]
  stack.pop
  end
  end
  end
  stack.empty?
  end
  # a test
  passes = ["{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}"].map { |x| balanced? x }
  puts passes.inspect
  fails = ["{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"].map { |x| balanced? x }
  puts fails.inspect
  “`
  A solution in Ruby.
  Apologies for the two fodder comments. I thought this used markdown.
  Here’s a Haskell version, also doing non-delimiters properly, of my ML function (borrowing from John’s solution – though this one uses hard-wired delimiters):
  I meant Graham there, not John. Can’t tell the difference between Ruby and Haskell.
  A slightly different Perl solution, simplified by having each opening and closer delimiter map to themselves.
  outputs:
  Some C(99 I think) stuff.
  I have a doubt for the stack allocation (when s==NULL or s==””), you may go malloc/free instead.
  (Note: this is not c++, this is C.)
  in main: int i = 0; (shame on me)
  C++
  Nice couple of C(++) solutions, here’s another one that doesn’t use a stack, instead, for each opener we scan forwards to find the closer, then we overwrite both – now if we find an unerased closer, the string is unbalanced – not very efficient, but the output is pretty:
  Output:
  That should be r[strlen()+1] of course.
  A beautifully simple perl version!
  use strict;
  use warnings;
  ## Run test….
  my @to_test = ( ‘{}’, ‘[]’, ‘()’, ‘a(b)c’, ‘abc[d]’, ‘a(b)c{d[e]}’, ‘{]’, ‘(]’, ‘a(b]c’, ‘abc[d}’, ‘a(b)c{d[e}]’ )
  printf ” %1s %s\n”, is_balanced($_)?’T’:’F’, $_ foreach @to_test;
  ## Returns 1 if strings is balanced – don’t you just love perl
  sub is_balanced {
  ( local $_ = shift ) =~ s{[^{}[\]()]}{}g; ## Remove non-brackets…
  0 while s{(\[\]|\{\}|\(\))}{}g; ## Remove pairs if we find them until there are none left
  return !$_; ## If we have left any brackets this will be non-empty or true!
  }
  Try that again with source code highlighting…