Balanced Delimiters
March 2, 2012
This exercise is easy if your language has a parser generator, harder if it doesn’t; whatever you do, it’s not a task for a regular expression. The basic algorithm is to keep a stack of delimiters, push an expected ending delimiter on the stack when a starting delimiter is seen, pop the stack and compare when an ending delimiter is seen, and complain if the stack isn’t empty at the end; quoted strings are handled separately, ignoring everything until the matching quote is seen. Here’s the code:
(define (balanced? str) ; () [] {} '' "" escape with \
(let ((delims '((#\( . #\)) (#\[ . #\]) (#\{ . #\}) (#\))))
(let loop ((cs (string->list str)) (stack (list)) (single? #f) (double? #f))
(cond ((null? cs) (and (null? stack) (not single?) (not double?)))
((char=? #\ (car cs))
(if (null? (cdr cs)) (null? stack)
(loop (cddr cs) stack single? double?)))
((and single? (null? cs)) #f)
((and single? (char=? (car cs) #\')) (loop (cdr cs) stack #f #f))
(single? (loop (cdr cs) stack #t #f))
((and double? (null? cs)) #f)
((and double? (char=? (car cs) #\")) (loop (cdr cs) stack #f #f))
(double? (loop (cdr cs) stack #f #t))
((char=? #\' (car cs)) (loop (cdr cs) stack #t #f))
((char=? #\" (car cs)) (loop (cdr cs) stack #f #t))
((assoc (car cs) delims) =>
(lambda (xs) (loop (cdr cs) (cons (cdr xs) stack) #f #f)))
((member (car cs) (map cdr delims))
(if (null? stack) #f
(if (not (char=? (car cs) (car stack))) #f
(loop (cdr cs) (cdr stack) #f #f))))
(else (loop (cdr cs) stack #f #f))))))
Variables single
and double
are #t
within the appropriate quoted strings and #f
otherwise. The stack contains closing delimiters, rather than opening delimiters, making it easier to compare when a closing delimiter is seen.
You can run the program at http://programmingpraxis.codepad.org/pIbthRad, which includes several examples.
[…] 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):
Unless the job description includes knowledge of regular expressions, I wouldn’t use this answer at the interview ;-).
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).
A Python 2.7 solution that is not as concise as Mike’s but should hopefully be more debuggable when things go wrong :)
Hum, not very sexy code…
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.
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;
}
Tried using a modified algorithm. Will post it.
Here’s the C solution to the problem:
Here’s a not-too-lispy Common Lisp solution:
Better late than never, another Python version
Here is my C version:
[…] was trying to solve the following Programming Praxis […]