Balanced Delimiters

June 10, 2014

I heard today’s exercise as an interview question — you have five minutes to solve this task, while I watch — but it could equally be a homework problem:

Write a function to return true/false after looking at a string. Examples of strings that pass:

{}, [], (), a(b)c, abc[d], a(b)c{d[e]}

Examples of strings that don’t pass:

{], (], a(b]c, abc[d}, a(b)c{d[e}]

Your task is to write the function described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below:

About these ads

Pages: 1 2

29 Responses to “Balanced Delimiters”

  1. […] all programming interview questions, this one is contrived… and it is also succinct, precise, pleasant, and […]

  2. jc said

    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:

    (define (balanced? str)
      (let* ((sentinel #\*)
             (closers '((#\} . #\{)
                        (#\) . #\()
                        (#\] . #\[)))
             (openers (map cdr closers)))
        (let loop ((cs (string->list str))
                   (stack (list sentinel)))
          (if (null? cs)
              (char=? (car stack) sentinel)
              (let* ((c (car cs))
                     (pair (assv c closers)))
                (cond ((pair? pair)
                       (and (char=? (cdr pair) (car stack))
                            (loop (cdr cs) (cdr stack))))
                      ((member c openers)
                       (loop (cdr cs) (cons c stack)))
                      (else
                       (loop (cdr cs) stack))))))))
    
  3. I remember implementing a similar algorithms while writing a compiler for my master thesis.

    Here is my suggestion in C#, just copied from LinqPAD:

    —————
    var itests = new string[] { “{}”, “[]”, “()”, “a(b)c”, “abc[d]“, “a(b)c{d[e]}”, “{]”, “(]”, “a(b]c”, “abc[d}”, “a(b)c{d[e}]” };

    var delims = new Dictionary { { ‘{‘, ‘}’ }, { ‘(‘, ‘)’ }, { ‘[', ']‘ } };

    Func BalancedDelimiters = new Func( (input) =>
    {
    var shunt = new Stack();
    for(int i = 0; i 0) return false;

    return true;
    }
    );

    foreach(string test in itests)
    {
    Console.WriteLine(BalancedDelimiters(test));
    }
    ——————

  4. Some code got clipped out, sorry, here is the complete version:

    —–

    var itests = new string[] { “{}”, “[]”, “()”, “a(b)c”, “abc[d]“, “a(b)c{d[e]}”, “{]”, “(]”, “a(b]c”, “abc[d}”, “a(b)c{d[e}]” };

    var delims = new Dictionary { { ‘{‘, ‘}’ }, { ‘(‘, ‘)’ }, { ‘[', ']‘ } };

    Func BalancedDelimiters = new Func( (input) =>
    {
    var shunt = new Stack();
    for(int i = 0; i 0) return false;

    return true;
    }
    );

    foreach(string test in itests)
    {
    Console.WriteLine(BalancedDelimiters(test));
    }

  5. JP said

    Use the call stack as the bracket matching stack:

    (define (match-brackets [matching #f])
      (define pairs '((#\( . #\)) (#\{ . #\}) (#\[ . #\])))
      (define c (read-char))
      (cond
        [(eof-object? c)            #t]
        [(assoc c pairs)            => (λ (pair) (and (match-brackets (cdr pair)) (match-brackets matching)))]
        [(eq? c matching)           #t]
        [(member c (map cdr pairs)) #f]
        [else                       (match-brackets matching)]))
    
  6. Lev Lozhkin said

    The iterative solution seems simplest, but a recursive solution can also be written. Here’s a comparison of the two in Python:

    # Iterative solution
    def imatcher(s, delims={"{": "}", "[": "]", "(": ")"}):
        closing_delims = delims.values()
        expected = []
    
        for c in s:
            if c in delims:  # Opening delim
                expected.append(delims[c])
            elif c in closing_delims:
                if expected and c == expected[-1]:  # Closing delim of proper kind
                    expected.pop()
                else:  # Mismatched delim or closing delim before opening one
                    return False
    
        return not expected  # All expected delims should have been matched
    
    # Recursive solution
    def rmatcher(s, delims={"{": "}", "[": "]", "(": ")"}):
        closing_delims = delims.values()
    
        # Returns index of first unmatched closing delim and error boolean
        # signifying if an unmatched delim was found deeper in this branch.
        def matcher(i=0):
            while i < len(s):
                c = s[i]
                if c in delims:
                    j, err = matcher(i+1)
                    if not err and j < len(s) and delims[c] == s[j]:
                        i = j  # Skip properly delimited substring
                    else:
                        return j, True
                elif c in closing_delims:
                    return i, False
                i += 1
            return i, False
    
        k, err = matcher()
        return not err and k == len(s)
    

    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.

  7. matthew said

    Pattern-matching ML-style is nice (this only does the brackets, not other symbols):

    fun f s (#"("::t) = f (#"("::s) t
      | f s (#"["::t) = f (#"["::s) t
      | f s (#"{"::t) = f (#"{"::s) t
      | f (#"("::s) (#")"::t) = f s t
      | f (#"["::s) (#"]"::t) = f s t
      | f (#"{"::s) (#"}"::t) = f s t
      | f [] [] = true
      | f _ _ = false
    
    val parse = f [] o explode
    
    - map parse ["[]","{[()]}","(({}{}())[])","[}","}{","((("];
    val it = [true,true,true,false,false,false] : bool list
    
  8. matthew said

    And a very simple Markov program:

    $ cat delim.mkv
    () =>
    [] =>
    {} =>
    ( =>. (
    [ =>. [
    { =>. {
    ) =>. )
    ] =>. ]
    } =>. }
    $ ./markov "((({()[(([{}][]){})]{}})))" < delim.mkv
    ((({()[(([{}][]){})]{}})))
    ((({[(([{}][]){})]{}})))
    ((({[(([{}]){})]{}})))
    ((({[(([]){})]{}})))
    ((({[((){})]{}})))
    ((({[({})]{}})))
    ((({[()]{}})))
    ((({[]{}})))
    ((({{}})))
    ((({})))
    ((()))
    (())
    ()
    
    $ ./markov "(()(])" < delim.mkv
    (()(])
    ((])
    ((])
    
  9. Mike said

    Now for something completely different.

    import re
    
    def balanced(s):
        # Remove everything that's not a delimiter.
        t = re.sub(r'[^]})[{(]', '', s)
    
        while t:
            # remove matched, adjacent delimiters
            u = re.sub(r'\(\)|\[\]|\{\}', '' , t)
    
            if u == t:
                # no more balanced delimiters
                return False
            t = u
    
        return True
    
    
  10. matthew said

    @Mike – nice, but not that different to my Markov program.

  11. matthew said

    Actually, I don’t need all those silly rules for termination – Markov programs terminate if no rules apply, so we can just have:

    () =>
    [] =>
    {} =>
    
  12. Peter said

    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

  13. Not the shortest code, but I tried to make it very readable. In Perl, as usual :).

    #!/usr/bin/perl -w
    
    # Reads from STDIN a series of input strings
    # Outputs to STDOUT true/false and the series
    
    use strict;
    use warnings;
    use Data::Dumper;
    
    while(my $string = <STDIN>) {
        chomp($string);
        print "".(isBalanced($string) ? 'true ' : 'false')." : $string\n";
    }
    
    sub isBalanced {
        my $string = shift;
    
        my @parts = split "", $string;
        my $delimiters = { '{' => '}', '[' => ']', '(' => ')' };
        my $delimiters_r = { map { ($delimiters->{$_}, $_) } (keys %{$delimiters}) };
    
        my @stack = ();
        while(my $item = shift @parts) {
            my $last_delim = pop @stack;
            if(defined $last_delim && defined $delimiters->{$last_delim} and $delimiters->{$last_delim} eq $item) {
                # Item closes the last parenthesis that had been opened => continue
                next;
            }
            else {
                # Item closes a parenthesis, but it is not the expected one => not balanced
                return 0 if defined $delimiters_r->{$item};
    
                # Put the last opened parenthesis back on the stack (if any)
                push @stack, $last_delim if defined $last_delim;
    
                # If the current item opens a new parenthesis, add it to the stack
                push @stack, $item if defined $delimiters->{$item};
            }
        }
    
        # Once the loop is over, the expression is balanced if and only if the stack is empty
        return scalar(@{stack}) == 0;
    }
    

    Tested with the input given:

    true  : {}
    true  : []
    true  : ()
    true  : a(b)c
    true  : abc[d]
    true  : a(b)c{d[e]}
    false : {]
    false : (]
    false : a(b]c
    false : abc[d}
    false : a(b)c{d[e}]
    
  14. Graham said

    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]

  15. Graham said

    Apologies for the typo! It’s been a while since I posted here, apparently.

  16. John Lekberg said

    #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]

  17. John Lekberg said

    “`
    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
    “`

  18. John Lekberg said

    A solution in 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 << 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
    

    Apologies for the two fodder comments. I thought this used markdown.

  19. matthew said

    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):

    import Control.Arrow ((&&&))
    
    f s ('(':t) = f ('(':s) t
    f s ('[':t) = f ('[':s) t
    f s ('{':t) = f ('{':s) t
    f ('(':s) (')':t) = f s t
    f ('[':s) (']':t) = f s t
    f ('{':s) ('}':t) = f s t
    f _ (')':t) = False
    f _ (']':t) = False
    f _ ('}':t) = False
    f s (_:t) = f s t
    f [] [] = True
    f _ _ = False
    
    main :: IO ()
    main = mapM_ (print . (id &&& f [])) . words $
     "{} [] () a(b)c abc[d] a(b)c{d[e]} {] (] a(b]c abc[d} a(b)c{d[e}]"
    
  20. matthew said

    I meant Graham there, not John. Can’t tell the difference between Ruby and Haskell.

  21. mcmillhj said

    A slightly different Perl solution, simplified by having each opening and closer delimiter map to themselves.

    #!/usr/bin/perl
    
    use strict; 
    use warnings; 
    
    my @openers = qw|( { [|;
    my @closers = qw|) } ]|;
    my %delims;
    @delims{@openers} = @closers;
    @delims{@closers} = @openers;
    
    sub check_balanced { 
       my ($s) = @_;
    
       my @stack;
       foreach my $c ( split //, $s ) {
          if (grep { $c eq $_ } @openers) {
             push @stack, $c; 
          }
          elsif (grep { $c eq $_ } @closers) {
             my $top = pop @stack; 
             return 0
                unless $top eq $delims{$c};         
          }
       }
       
       return scalar @stack == 0;
    }
    
    foreach my $test ('{}', '[]','()', 'a(b)c', 'abc[d]', 'a(b)c{d[e]}', '{]', '(]', 'a(b]c', 'abc[d}', 'a(b)c{d[e}]') {
       printf "%-12s is%s balanced\n", $test, (!check_balanced($test) ? " not" : "");
    }
    

    outputs:

    {}           is balanced
    []           is balanced
    ()           is balanced
    a(b)c        is balanced
    abc[d]       is balanced
    a(b)c{d[e]}  is balanced
    {]           is not balanced
    (]           is not balanced
    a(b]c        is not balanced
    abc[d}       is not balanced
    a(b)c{d[e}]  is not balanced
    
  22. sed said

    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.)

    #include <string.h>
    #include <stdbool.h>
    
    _Bool balanced(char *s)
    {
            int stack[strlen(s)];
            int stack_pointer = 0;
            char opener;
            while (*s) {
                    switch (*s++) {
                            case '(':
                            case '[':
                            case '{': stack[stack_pointer++] = s[-1]; continue;
                            case '}': opener = '{'; break;
                            case ']': opener = '['; break;
                            case ')': opener = '('; break;
                            default: continue;
                    }
                    if (!stack_pointer || stack[--stack_pointer] != opener)
                            return false;
            }
            return !stack_pointer;
    }
    
    #include <stdio.h>
    
    int main(void)
    {
            char *tests[] = {
                    "{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}",
                    "{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]",
                    NULL
            };
            int i;
    
            while (tests[i] != NULL) {
                    printf("%s: %d\n", tests[i], balanced(tests[i]));
                    i++;
            }
    
            return 0;
    }
    
  23. Sed said

    in main: int i = 0; (shame on me)

  24. fisherro said

    C++

    #include <algorithm>
    #include <functional>
    #include <iostream>
    #include <stack>
    #include <string>
    #include <vector>
    //http://programmingpraxis.com/2014/06/10/balanced-delimiters-2/
    
    bool check_brackets(const std::string& in)
    {
    	std::stack<char> stk;
    	for (auto c: in) {
    		if ((c == '{') || (c == '[') || (c == '(')) {
    			stk.push(c);
    		} else if ((c == '}') || (c == ']') || (c == ')')) {
    			if (stk.empty()) return false;
    			if ((c == '}') && (stk.top() != '{')) return false;
    			if ((c == ']') && (stk.top() != '[')) return false;
    			if ((c == ')') && (stk.top() != '(')) return false;
    			stk.pop();
    		}
    	}
    	if (!stk.empty()) return false;
    	return true;
    }
    
    int main(int argc, char *argv[])
    {
    	std::vector<std::string> true_tests = {"{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}"};
    	std::vector<std::string> false_tests = {"{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"};
    	std::cout << "True tests: " << std::all_of(true_tests.begin(), true_tests.end(), &check_brackets)
    			<< std::endl;
    	std::cout << "False tests: " << std::all_of(false_tests.begin(), false_tests.end(),
    			std::not1(std::function<bool(const std::string&)>(&check_brackets))) << std::endl;
    }
    
  25. matthew said

    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:

    #include <stdio.h>
    #include <string.h>
    
    bool balanced(const char *s)
    {
      char r[strlen(s)];
      strcpy(r,s);
      char *p = r;
      for ( ; *p; p++) {
        if (strchr(")]}",*p)) {
          return false;
        } else if (strchr("([{",*p)) {
          int n = 1;
          char *q = p+1;
          for ( ; *q; q++) {
            if (strchr("([{",*q)) n++;
            else if (strchr(")]}",*q)) n--;
            if (n == 0) break;
          }
          if ( n != 0 || 
               (*p == '(' && *q != ')') ||
               (*p == '[' && *q != ']') ||
               (*p == '{' && *q != '}') ) {
            return false;
          } else {
            *p = *q = '*';
            fprintf(stderr,"%s\n", r);
          }
        }
      }
      return true;
    }
    
    int main(void)
    {
      const char *tests[] = {
        "{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}",
        "{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]",
        "(((()())())())", "(((()())(])())", 
        "(((()())())()", "((())))))",
        NULL
      };
      int i = 0;
      
      while (tests[i] != NULL) {
        printf("%s: %d\n", tests[i], balanced(tests[i]));
        i++;
      }
    
      return 0;
    }
    

    Output:

    **
    {}: 1
    **
    []: 1
    **
    (): 1
    a*b*c
    a(b)c: 1
    abc*d*
    abc[d]: 1
    a*b*c{d[e]}
    a*b*c*d[e]*
    a*b*c*d*e**
    a(b)c{d[e]}: 1
    {]: 0
    (]: 0
    a(b]c: 0
    abc[d}: 0
    a*b*c{d[e}]
    a(b)c{d[e}]: 0
    *((()())())()*
    **(()())()*()*
    ***()()*()*()*
    *****()*()*()*
    ********()*()*
    ***********()*
    **************
    (((()())())()): 1
    *((()())(])()*
    **(()())(]*()*
    ***()()*(]*()*
    *****()*(]*()*
    ********(]*()*
    (((()())(])()): 0
    (((()())())(): 0
    *(())*)))
    **()**)))
    ******)))
    ((()))))): 0
    
  26. matthew said

    That should be r[strlen()+1] of course.

  27. Rutger said
    
    def valid_balanced_string(test, opening_brackets = "[{(", closing_brackets = "]})"):
    	stack = []
    	for c in test:
    		try:
    			i = opening_brackets.index(c)
    			stack.append(closing_brackets[i])
    		except:
    			pass
    
    		try:
    			i = closing_brackets.index(c)
    			if stack.pop() != closing_brackets[i]:
    				return False
    		except:
    			pass
    
    	return True
    
    test_input = ["{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}", "{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"]
    
    for test in test_input:
    	print "testing: ", test, "result = ", valid_balanced_string(test)
    
  28. 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!
    }

  29. Try that again with source code highlighting…

    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!
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: