Balanced Delimiters

March 2, 2012

These interview questions are addicting; I have to stop with them and get on something else. But one more won’t hurt:

Write a function that takes a string and determines if the delimiters in the string are balanced. The pairs of delimiters are (), [], {}, and <>, and delimiters may be nested. In addition, determine that string delimiters ‘ and ” are properly matched; other delimiters lose their magical delimiter-ness property within quoted strings. Any delimiter is escaped if it follows a backslash.

Your task is to write the function to determine if a string has balanced delimiters. 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

11 Responses to “Balanced Delimiters”

  1. […] today’s Programming Praxis exercise, our goal is to determine whether the delimiters in a given string are […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/03/02/programming-praxis-balanced-delimiters/ for a version with comments):

    balanced :: String -> Bool
    balanced = f [] where
        f bs       []                                               = null bs
        f bs       ('\\':_:cs)                                      = f bs cs
        f (b:bs)   (c   :  cs) | lookup b pairs == Just c           = f bs cs
                               | elem b "'\""                       = f (b:bs) cs
        f bs       (c   :  cs) | any (\(a,b) -> elem c [a,b]) pairs = f (c:bs) cs 
                               | otherwise                          = f bs cs
        pairs = [('(', ')'), ('[', ']'), ('{', '}'), ('\'', '\''), ('"', '"')]
    
  3. Mike said

    Unless the job description includes knowledge of regular expressions, I wouldn’t use this answer at the interview ;-).

    import re
    
    def is_balanced(s):
    	t = re.sub(r"\\.|[^][}{)(\"'\\]+", '', s)
    	t = re.sub(r"""([^'"]*?)(['"]).*?\2""", r"\1", t)
    
    	m = 1
    	while m:
    		t,m = re.subn(r"\[\]|\(\)|\{\}", '', t)
    
    	return not t
    
    

    The first regex removes all escaped characters and anything that isn’t a paired delimiter, i.e., “, ‘, [, ], (, ), {, and }.
    The second regex removes all quoted strings.
    The loop removes matched pairs of delimiters until no replacements are made (m == 0).

  4. Philip G said

    A Python 2.7 solution that is not as concise as Mike’s but should hopefully be more debuggable when things go wrong :)

    open_set = ['(', '{', '[']
    close_set = [')', '}', ']']
    string_set = ['"', "'"]
    
    def is_balanced(s):
        print s
        delim_stack = []
        string_mode = False
        balanced = True
        for c in s:
            #~ print "Evaluating ", c        
            if c in string_set:
                if (len(delim_stack) > 0 and 
                    string_mode and 
                    delim_stack[-1] == c):
                    #~ print "End of string"
                    delim_stack.pop()
                    balanced = True                
                    string_mode = False
                elif not string_mode:
                    #~ print "Start of string"
                    delim_stack.append(c)
                    balanced = False
                    string_mode = True                
            elif c in open_set and not string_mode:            
                #~ print "Is open delimiter"
                balanced = False    
                delim_stack.append(c)   
            elif c in close_set and not string_mode:
                #~ print "Is close delimiter"                
                try:
                    p = delim_stack.pop()
                    if close_set.index(c) != open_set.index(p):
                        #~ print "%s doesn't match %s" % (p, c)
                        balanced = False
                        break
                    else:
                        balanced = True
                except IndexError as e:
                    #~ print "Extra close delimiter"
                    balanced = False
                    break
        
        return balanced
        
    if __name__=="__main__":
        assert is_balanced("") == True
        assert is_balanced("Test string") == True
        assert is_balanced("[Test string]") == True
        assert is_balanced("{Test string}") == True
        assert is_balanced("(Test string)") == True
        assert is_balanced("'Test string'") == True
        assert is_balanced("\"Test string\"") == True
        assert is_balanced("[{(Test string)}]") == True
        assert is_balanced("\"'Test string\'\"") == True
        assert is_balanced("[{(\"'Test string\'\")}]") == True
            
        assert is_balanced("\"Test String") == False
        assert is_balanced("[Test String") == False
        assert is_balanced("[Test String}") == False
        assert is_balanced("[Test String]]") == False
        assert is_balanced("{([Test String]})") == False
        assert is_balanced("\"Test String'") == False
    
  5. Axio said

    Hum, not very sexy codeā€¦

    (define (bal l st #!optional (str #f))
      (if (null? l)
        ;; Open strings are not well balanced 
        (and (not str) (null? st))
        (if str ;; String-parse mode
          (case (car l)
            ;; Close string
            ((#\') (bal (cdr l) st))
            ;; Strings are escaped too, so I can escape the string-closing quote.
            ((#\\) (and (not (null? (cdr l))) (bal (cddr l) st str)))
            ;; O nom nom
            (else (bal (cdr l) st str)))
          (case (car l)
            ;; Escape cannot be last character
            ((#\\) (or (null? (cdr l)) (bal (cddr l) st)))
            ;; Push the closing char on the stack
            ((#\( #\[ #\{) (bal (cdr l)
                                (cons
                                  (cdr (assoc
                                         (car l)
                                         '((#\( . #\)) (#\[ . #\]) (#\{ . #\}))))
                                  st)))
            ;; Check if the char is on the stack
            ((#\) #\] #\}) (and (not (null? st)) (eq? (car l) (car st))
                                (bal (cdr st))))
            ;; Go into string-parse mode
            ((#\`) (bal (cdr l) st #t))
            ;; O nom nom
            (else (bal (cdr l) st))))))
    
    (define (balanced? str)
      (bal (string->list str) '()))
    
  6. Mike said

    Here is an alternative python 2.7 version.

    The overarching idea is the same as the regex version above:
    1. Escaped chars are removed first, because escaped chars lose any bracket-like properties.
    2. Quoted strings are removed, because they also can’t change the balance unless a close-quote is missing.
    – a lone quote is used to flag a missing close quote.
    3. A stack is used to track matched open- and close-delimiters.

    from itertools import dropwhile
    
    def skip_escapes(s):
        '''generator that returns chars in s, but elides escaped chars'''
        
        chars = iter(s)
        for ch in chars:
            if ch == '\\':
                next(chars)
            else:
                yield ch
    
    def skip_quotes(s):
        '''A generator that returns chars in s, but elides quoted strings.
           It yields " or ' if missing a matching close quote.'''
        
        chars = iter(s)
        for ch in chars:
            if ch in "\"'":
                if next(dropwhile(ch.__ne__, chars), False):
                    continue
                
            yield ch
        
    def is_balanced(s):
        '''returns Boolean indicating if delimiters are balanced.
        Delims inside quoted strings and escaped chars are ignored.'''
        
        stack = []
        chars = skip_quotes(skip_escapes(s))
        
        for ch in chars:
            if ch  in "([{\"'":
                stack.append(ch)
                
            elif ch in ")]}":
                if not stack or stack.pop() != {')':'(', ']':'[', '}':'{'}[ch]:
                    return False
                
        return not stack
    
  7. Brikesh said

    Here is a C# version
    The alogorithm used is
    1. Input character array [An]
    Flag = true
    For j<–0 to j<–n-1
    if [Aj] = (,,],}
    if Aj = pop () // compare the dilimiters
    else
    Flag = false
    Next j
    2. Return Flag

    char[] openingDilimiters = new char[]{‘(‘,'[‘,'{‘,” };

    public bool Algorithm1(string input)
    {
    bool rv = true;
    Stack dilimiters = new Stack();
    Stopwatch watch = new Stopwatch();
    watch.Start();
    for (int count = 0; count 0)
    {
    char opening = dilimiters.Pop();
    rv = _IsinPair(opening, closing);
    }
    else
    rv = false;
    if (!rv)
    break;
    }
    }
    //At the end of iteration there should not be any value left in stack
    if (rv && dilimiters.Count > 0)
    rv = false;
    watch.Stop();
    Console.WriteLine(“Time elapsed in algorithm1 : ” + watch.Elapsed);
    return rv;
    }

    private bool _IsinPair(char opening, char closing)
    {
    if (opening == ‘(‘ && closing == ‘)’)
    return true;
    else if (opening == ‘[‘ && closing == ‘]’)
    return true;
    else if (opening == ‘{‘ && closing == ‘}’)
    return true;
    else if (opening == ”)
    return true;
    else
    return false;
    }

  8. Brikesh said

    Tried using a modified algorithm. Will post it.

  9. Here’s the C solution to the problem:

    #include<stdio.h>
    #include<string.h>
    int main()
    {
            char stack[100],input[500];
            int i,top=-1,flag=0;
            scanf("%s",input);
            for(i=0;i<100;i++)
                    stack[i]='\0';
            for(i=0;i<strlen(input);i++)
            {
                    if((input[i]=='\'' || input[i]=='\"')&&stack[top]!=input[i])
                    {
                            flag=1;
                            stack[++top]=input[i];
                    }
                    else if((input[i]=='\'' || input[i]=='\"')&&stack[top]==input[i])
                    {
                            flag=0;
                            stack[top--]='\0';
                    }
                    else if((input[i]=='('||input[i]=='['||input[i]=='{'||input[i]=='<') && !flag)
                            stack[++top]=input[i];
                    else if((input[i]==']'||input[i]=='}'||input[i]=='>')&& input[i]==stack[top]+2)
                            stack[top--]='\0';
                    else if(input[i]==')' && input[i]==stack[top]+1)
                            stack[top--]='\0';
                    printf("\nIteration %d: %s\n",i,stack);
            }
            printf("%s",stack[0]=='\0'?"Balanced":"Unbalanced");
    }
    
  10. jonathanjohansen said

    Here’s a not-too-lispy Common Lisp solution:

    (defun balanced-delimiters? (string &key (strings '(#\' #\"))
            (delimiters '((#\{ #\}) (#\( #\)) (#\[ #\]) (#\< #\>)))
            (escape #\\))
        (loop with nest = ()
              with escaped = nil
              with instring = nil
              for c across string
            do (cond
                ((and (not escaped) (char= c escape))
                    (setf escaped t)); Escape the next character...
                (escaped (setf escaped nil)); Just ignore one character.
                (instring (if (char= c instring)
                        (setf instring nil)
                        (when (member c strings) (return-from balanced-delimiters? nil))))
                ((member c strings) (setf instring c)); Assuming open char = close char
                ((member c delimiters :key #'cadr); End of nesting delimiter
                    (if (and nest (char= c (car nest)))
                        (pop nest)
                        (return-from balanced-delimiters? nil)))
                ((member c delimiters :key #'car); Un-escaped opener not in a string
                    (push (cadr (find c delimiters :key #'car)) nest)))
            finally (return (not (or escaped instring nest)))))
    
    (list; Balanced delimiters (I've got to escape my escape chars ...)
        (balanced-delimiters? "abcd")
        (balanced-delimiters? "a\"bc\"d")
        (balanced-delimiters? "a'bcd'")
        (balanced-delimiters? "(abcd)")
        (balanced-delimiters? "[abcd]")
        (balanced-delimiters? "{abcd}")
        (balanced-delimiters? "<abcd>")
        (balanced-delimiters? "((()))")
        (balanced-delimiters? "[[[[]]]]")
        (balanced-delimiters? "{([((\"{{{\"))])}")
        (balanced-delimiters? "(pre) 'str}}}ing' <post>")
        (balanced-delimiters? "(\\(\\{)")
        (balanced-delimiters? "(\\)\\]\\'\\\")")
        (balanced-delimiters? "as\\\"ohoh"))
    
    (list; Unbalanced delimiters
        (balanced-delimiters? "(")
        (balanced-delimiters? ")")
        (balanced-delimiters? "a[")
        (balanced-delimiters? "a]")
        (balanced-delimiters? "{a")
        (balanced-delimiters? "}a")
        (balanced-delimiters? "<[>]")
        (balanced-delimiters? "this 'is\" wonky")
        (balanced-delimiters? "and (so (is \"this'))"))
    
  11. Better late than never, another Python version

    #!/usr/bin/env python
    # Balanced Delimiters
    # http://programmingpraxis.com/2012/03/02/balanced-delimiters/
    
    delimiters = ( '()', '[]', '{}', "''", '""' )
    esc = '\\'
    
    def is_balanced(s, delimiters=delimiters, esc=esc):
        '''
        Returns Boolean indicating if delimiters are balanced.
        Delimiters with the same opening and closing char are considered quotes.       
        Delimiters inside quoted strings and escaped chars are ignored.
        '''
    
        stack = []
        opening = tuple(str[0] for str in delimiters)
        closing = tuple(str[1] for str in delimiters)
        for i, c in enumerate(s):
            if len(stack) and stack[-1] == -1:
                stack.pop()
            elif c in esc:
                stack.append(-1)
            elif c in opening and 
                    (not len(stack) or opening[stack[-1]] != closing[stack[-1]]):
                stack.append(opening.index(c))
            elif c in closing:
                if len(stack) == 0 or closing.index(c) != stack[-1]:
                    return False
                stack.pop()
    
        return len(stack) == 0
    
    print "These True: "
    print is_balanced("")
    print is_balanced("abc")
    print is_balanced("()")
    print is_balanced("[[[]]]")
    print is_balanced("'('")
    print is_balanced("\\(()")
    
    print "These False: "
    print is_balanced("(")
    print is_balanced("([)]")
    print is_balanced("'{'}")
    print is_balanced("\\()")
    print is_balanced("\\")
    

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 636 other followers

%d bloggers like this: