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

Pages: 1 2

### 12 Responses to “Balanced Delimiters”

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

```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,input;
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'?"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
# 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 for str in delimiters)
closing = tuple(str 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("\\")
```
12. tom said

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;
}
```