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.
[…] 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 […]