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.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to determine whether the delimiters in a given string are […]
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 = [('(', ')'), ('[', ']'), ('{', '}'), ('\'', '\''), ('"', '"')]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 tThe 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).
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'") == FalseHum, 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) '()))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 stackHere 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;
}
Tried using a modified algorithm. Will post it.
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"); }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'))"))Better late than never, another Python version
#!/usr/bin/env python # Balanced Delimiters # https://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("\\")Here is my C version:
#include #include bool match(char *string) { int length = strlen(string); int index = 1; char *stack = calloc(length + 1, sizeof(char)); if (stack == NULL) return false; for (int i = 0; i < length; ++i) { switch (string[i]) { case '{': stack[index++] = '}'; break; case '(': stack[index++] = ')'; break; case '[': stack[index++] = ']'; break; case '}': case ')': case ']': if (stack[--index] != string[i]) return false; } } free(stack); return index == 1; } int main(int argc, char *argv[]) { bool ret; char *strings[] = { "123{abc(def[ghi]jkl)mno}456", "}{{abc(def[ghi]jkl)mno}", "{abc(def[gh}i]jkl)mno}", "123{abc(def[][ghi]jkl)mno}456", "123{abc(def[][ghi]jkl)mno}456}}}}", }; for (int i = 0; i < 5; ++i) { ret = match(strings[i]); printf("%s: %s\n", strings[i], ret ? "true" : "false"); } return 0; }[…] was trying to solve the following Programming Praxis […]