## Balanced Delimiters

### June 10, 2014

I heard today’s exercise as an interview question — you have five minutes to solve this task, while I watch — but it could equally be a homework problem:

Write a function to return true/false after looking at a string. Examples of strings that pass:

`{}, [], (), a(b)c, abc[d], a(b)c{d[e]}`

Examples of strings that don’t pass:

`{], (], a(b]c, abc[d}, a(b)c{d[e}]`

Your task is to write the function described above. 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

### 29 Responses to “Balanced Delimiters”

1. […] all programming interview questions, this one is contrived… and it is also succinct, precise, pleasant, and […]

2. jc said

You can simplify the code by starting with a sentinel character (e.g. #\*) on the stack instead of an empty stack. Then you can skip the null stack check when you encounter a closing character. After the last character instead of checking for an empty stack you then need to check that the top of the stack is the sentinel character.

And using an association list to associate the closing character to the opening character would be more elegant than the two parallel lists and three branches of the or.

The following code incorporates those ideas:

```(define (balanced? str)
(let* ((sentinel #\*)
(closers '((#\} . #\{)
(#\) . #\()
(#\] . #\[)))
(openers (map cdr closers)))
(let loop ((cs (string->list str))
(stack (list sentinel)))
(if (null? cs)
(char=? (car stack) sentinel)
(let* ((c (car cs))
(pair (assv c closers)))
(cond ((pair? pair)
(and (char=? (cdr pair) (car stack))
(loop (cdr cs) (cdr stack))))
((member c openers)
(loop (cdr cs) (cons c stack)))
(else
(loop (cdr cs) stack))))))))
```
3. I remember implementing a similar algorithms while writing a compiler for my master thesis.

Here is my suggestion in C#, just copied from LinqPAD:

—————
var itests = new string[] { “{}”, “[]”, “()”, “a(b)c”, “abc[d]”, “a(b)c{d[e]}”, “{]”, “(]”, “a(b]c”, “abc[d}”, “a(b)c{d[e}]” };

var delims = new Dictionary { { ‘{‘, ‘}’ }, { ‘(‘, ‘)’ }, { ‘[‘, ‘]’ } };

Func BalancedDelimiters = new Func( (input) =>
{
var shunt = new Stack();
for(int i = 0; i 0) return false;

return true;
}
);

foreach(string test in itests)
{
Console.WriteLine(BalancedDelimiters(test));
}
——————

4. Some code got clipped out, sorry, here is the complete version:

—–

var itests = new string[] { “{}”, “[]”, “()”, “a(b)c”, “abc[d]”, “a(b)c{d[e]}”, “{]”, “(]”, “a(b]c”, “abc[d}”, “a(b)c{d[e}]” };

var delims = new Dictionary { { ‘{‘, ‘}’ }, { ‘(‘, ‘)’ }, { ‘[‘, ‘]’ } };

Func BalancedDelimiters = new Func( (input) =>
{
var shunt = new Stack();
for(int i = 0; i 0) return false;

return true;
}
);

foreach(string test in itests)
{
Console.WriteLine(BalancedDelimiters(test));
}

5. JP said

Use the call stack as the bracket matching stack:

```(define (match-brackets [matching #f])
(define pairs '((#\( . #\)) (#\{ . #\}) (#\[ . #\])))
(cond
[(eof-object? c)            #t]
[(assoc c pairs)            => (λ (pair) (and (match-brackets (cdr pair)) (match-brackets matching)))]
[(eq? c matching)           #t]
[(member c (map cdr pairs)) #f]
[else                       (match-brackets matching)]))
```
6. Lev Lozhkin said

The iterative solution seems simplest, but a recursive solution can also be written. Here’s a comparison of the two in Python:

```# Iterative solution
def imatcher(s, delims={"{": "}", "[": "]", "(": ")"}):
closing_delims = delims.values()
expected = []

for c in s:
if c in delims:  # Opening delim
expected.append(delims[c])
elif c in closing_delims:
if expected and c == expected[-1]:  # Closing delim of proper kind
expected.pop()
else:  # Mismatched delim or closing delim before opening one
return False

return not expected  # All expected delims should have been matched

# Recursive solution
def rmatcher(s, delims={"{": "}", "[": "]", "(": ")"}):
closing_delims = delims.values()

# Returns index of first unmatched closing delim and error boolean
# signifying if an unmatched delim was found deeper in this branch.
def matcher(i=0):
while i < len(s):
c = s[i]
if c in delims:
j, err = matcher(i+1)
if not err and j < len(s) and delims[c] == s[j]:
i = j  # Skip properly delimited substring
else:
return j, True
elif c in closing_delims:
return i, False
i += 1
return i, False

k, err = matcher()
return not err and k == len(s)
```

Why would you implement this recursively if the result is more difficult to understand and cannot be optimized using tail-recursion to provide the same performance as the iterative version? Good question.

A side-note is that the above can be used with any sequence and appropriately typed delimiters, not just string/characters.

7. matthew said

Pattern-matching ML-style is nice (this only does the brackets, not other symbols):

```fun f s (#"("::t) = f (#"("::s) t
| f s (#"["::t) = f (#"["::s) t
| f s (#"{"::t) = f (#"{"::s) t
| f (#"("::s) (#")"::t) = f s t
| f (#"["::s) (#"]"::t) = f s t
| f (#"{"::s) (#"}"::t) = f s t
| f [] [] = true
| f _ _ = false

val parse = f [] o explode

- map parse ["[]","{[()]}","(({}{}())[])","[}","}{","((("];
val it = [true,true,true,false,false,false] : bool list
```
8. matthew said

And a very simple Markov program:

```\$ cat delim.mkv
() =>
[] =>
{} =>
( =>. (
[ =>. [
{ =>. {
) =>. )
] =>. ]
} =>. }
\$ ./markov "((({()[(([{}][]){})]{}})))" < delim.mkv
((({()[(([{}][]){})]{}})))
((({[(([{}][]){})]{}})))
((({[(([{}]){})]{}})))
((({[(([]){})]{}})))
((({[((){})]{}})))
((({[({})]{}})))
((({[()]{}})))
((({[]{}})))
((({{}})))
((({})))
((()))
(())
()

\$ ./markov "(()(])" < delim.mkv
(()(])
((])
((])
```
9. Mike said

Now for something completely different.

```import re

def balanced(s):
# Remove everything that's not a delimiter.
t = re.sub(r'[^]})[{(]', '', s)

while t:
u = re.sub(r'\(\)|\[\]|\{\}', '' , t)

if u == t:
# no more balanced delimiters
return False
t = u

return True

```
10. matthew said

@Mike – nice, but not that different to my Markov program.

11. matthew said

Actually, I don’t need all those silly rules for termination – Markov programs terminate if no rules apply, so we can just have:

```() =>
[] =>
{} =>
```
12. Peter said

An imperative Python solution:

```    1   def pop(s, x):    2       y = s.pop()    3       return x == y    4       5   def is_balanced(xs):    6       s = ['b']    7       for x in xs:    8           if x in '{([': s.append(x)    9           elif x == '}':   10               if not pop(s, '{'): return False   11           elif x == ')':   12               if not pop(s, '('): return False   13           elif x == ']':   14               if not pop(s, '['): return False   15       return s == ['b'] ```

```    1   isBalanced xs = scan xs "b" where    2       scan [] ys = ys == "b"     3       scan (x:xs) ys    4           | x `elem` "{([" = scan xs (x:ys)    5           | x `elem` "})]" = case (head ys) of    6                                  '{' -> x == '}'    7                                  '(' -> x == ')'    8                                  '[' -> x == ']'    9                                  'b' -> False   10                              && scan xs (tail ys)   11           | otherwise = scan xs ys ```

13. Not the shortest code, but I tried to make it very readable. In Perl, as usual :).

```#!/usr/bin/perl -w

# Reads from STDIN a series of input strings
# Outputs to STDOUT true/false and the series

use strict;
use warnings;
use Data::Dumper;

while(my \$string = <STDIN>) {
chomp(\$string);
print "".(isBalanced(\$string) ? 'true ' : 'false')." : \$string\n";
}

sub isBalanced {
my \$string = shift;

my @parts = split "", \$string;
my \$delimiters = { '{' => '}', '[' => ']', '(' => ')' };
my \$delimiters_r = { map { (\$delimiters->{\$_}, \$_) } (keys %{\$delimiters}) };

my @stack = ();
while(my \$item = shift @parts) {
my \$last_delim = pop @stack;
if(defined \$last_delim && defined \$delimiters->{\$last_delim} and \$delimiters->{\$last_delim} eq \$item) {
# Item closes the last parenthesis that had been opened => continue
next;
}
else {
# Item closes a parenthesis, but it is not the expected one => not balanced
return 0 if defined \$delimiters_r->{\$item};

# Put the last opened parenthesis back on the stack (if any)
push @stack, \$last_delim if defined \$last_delim;

# If the current item opens a new parenthesis, add it to the stack
push @stack, \$item if defined \$delimiters->{\$item};
}
}

# Once the loop is over, the expression is balanced if and only if the stack is empty
return scalar(@{stack}) == 0;
}
```

Tested with the input given:

```true  : {}
true  : []
true  : ()
true  : a(b)c
true  : abc[d]
true  : a(b)c{d[e]}
false : {]
false : (]
false : a(b]c
false : abc[d}
false : a(b)c{d[e}]
```
14. Graham said

import Control.Arrow ((&&&))
import Data.Maybe (fromJust)
import qualified Data.Map as M
import qualified Data.Set as S

pairs :: M.Map Char Char
pairs = M.fromList [(‘)’, ‘(‘), (‘]’, ‘[‘), (‘}’, ‘{‘)]

open :: S.Set Char
open = S.fromList . M.elems \$ pairs

shut :: S.Set Char
shut = M.keysSet pairs

ok :: String -> Bool
ok = f []
where
f s [] = null s
f s (c:cs) | S.member c open = f (c:s) cs
| S.member c shut && g s c = f (tail s) cs
| otherwise = f s cs
g s c = not (null s) && (head s == fromJust (M.lookup c pairs))

main :: IO ()
main = mapM_ (print . (id &&& ok)) . words \$
“{} [] () a(b)c abc[d] a(b)c{d[e]} {] (] a(b]c abc[d} a(b)c{d[e}]”
[/sourcecocde]

15. Graham said

Apologies for the typo! It’s been a while since I posted here, apparently.

16. John Lekberg said

#A solution in `Ruby`

“`ruby
def balanced?(string)
delim_pairs = [[“(“, “)”], [“[“, “]”], [“{“, “}”]]
stack = []
string.split(“”).each do |char|
head = stack.empty? ? nil : stack[-1]
delim_pairs.each do |pair|
if char == pair
stack < [true, true, true, true, true, true]
fails = [“{]”, “(]”, “a(b]c”, “abc[d}”, “a(b)c{d[e}]”].map { |x| balanced? x }
puts fails.inspect #==> [false, false, false, false, false]

17. John Lekberg said

“`
def balanced?(string)
delim_pairs = [[“(“, “)”], [“[“, “]”], [“{“, “}”]]
stack = []
string.split(“”).each do |char|
head = stack.empty? ? nil : stack[-1]
delim_pairs.each do |pair|
if char == pair
stack << char
elsif char == pair && head == pair
stack.pop
end
end
end
stack.empty?
end

# a test
passes = ["{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}"].map { |x| balanced? x }
puts passes.inspect
fails = ["{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"].map { |x| balanced? x }
puts fails.inspect
“`

18. John Lekberg said

A solution in Ruby.

```def balanced?(string)
delim_pairs = [["(", ")"], ["[", "]"], ["{", "}"]]
stack = []
string.split("").each do |char|
head = stack.empty? ? nil : stack[-1]
delim_pairs.each do |pair|
if char == pair
stack << char
elsif char == pair && head == pair
stack.pop
end
end
end
stack.empty?
end

# a test
passes = ["{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}"].map { |x| balanced? x }
puts passes.inspect
fails = ["{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"].map { |x| balanced? x }
puts fails.inspect
```

Apologies for the two fodder comments. I thought this used markdown.

19. matthew said

Here’s a Haskell version, also doing non-delimiters properly, of my ML function (borrowing from John’s solution – though this one uses hard-wired delimiters):

```import Control.Arrow ((&&&))

f s ('(':t) = f ('(':s) t
f s ('[':t) = f ('[':s) t
f s ('{':t) = f ('{':s) t
f ('(':s) (')':t) = f s t
f ('[':s) (']':t) = f s t
f ('{':s) ('}':t) = f s t
f _ (')':t) = False
f _ (']':t) = False
f _ ('}':t) = False
f s (_:t) = f s t
f [] [] = True
f _ _ = False

main :: IO ()
main = mapM_ (print . (id &&& f [])) . words \$
"{} [] () a(b)c abc[d] a(b)c{d[e]} {] (] a(b]c abc[d} a(b)c{d[e}]"
```
20. matthew said

I meant Graham there, not John. Can’t tell the difference between Ruby and Haskell.

21. mcmillhj said

A slightly different Perl solution, simplified by having each opening and closer delimiter map to themselves.

```#!/usr/bin/perl

use strict;
use warnings;

my @openers = qw|( { [|;
my @closers = qw|) } ]|;
my %delims;
@delims{@openers} = @closers;
@delims{@closers} = @openers;

sub check_balanced {
my (\$s) = @_;

my @stack;
foreach my \$c ( split //, \$s ) {
if (grep { \$c eq \$_ } @openers) {
push @stack, \$c;
}
elsif (grep { \$c eq \$_ } @closers) {
my \$top = pop @stack;
return 0
unless \$top eq \$delims{\$c};
}
}

return scalar @stack == 0;
}

foreach my \$test ('{}', '[]','()', 'a(b)c', 'abc[d]', 'a(b)c{d[e]}', '{]', '(]', 'a(b]c', 'abc[d}', 'a(b)c{d[e}]') {
printf "%-12s is%s balanced\n", \$test, (!check_balanced(\$test) ? " not" : "");
}
```

outputs:

```{}           is balanced
[]           is balanced
()           is balanced
a(b)c        is balanced
abc[d]       is balanced
a(b)c{d[e]}  is balanced
{]           is not balanced
(]           is not balanced
a(b]c        is not balanced
abc[d}       is not balanced
a(b)c{d[e}]  is not balanced
```
22. sed said

Some C(99 I think) stuff.
I have a doubt for the stack allocation (when s==NULL or s==””), you may go malloc/free instead.
(Note: this is not c++, this is C.)

```#include <string.h>
#include <stdbool.h>

_Bool balanced(char *s)
{
int stack[strlen(s)];
int stack_pointer = 0;
char opener;
while (*s) {
switch (*s++) {
case '(':
case '[':
case '{': stack[stack_pointer++] = s[-1]; continue;
case '}': opener = '{'; break;
case ']': opener = '['; break;
case ')': opener = '('; break;
default: continue;
}
if (!stack_pointer || stack[--stack_pointer] != opener)
return false;
}
return !stack_pointer;
}

#include <stdio.h>

int main(void)
{
char *tests[] = {
"{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}",
"{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]",
NULL
};
int i;

while (tests[i] != NULL) {
printf("%s: %d\n", tests[i], balanced(tests[i]));
i++;
}

return 0;
}
```
23. Sed said

in main: int i = 0; (shame on me)

24. fisherro said

C++

```#include <algorithm>
#include <functional>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
//https://programmingpraxis.com/2014/06/10/balanced-delimiters-2/

bool check_brackets(const std::string& in)
{
std::stack<char> stk;
for (auto c: in) {
if ((c == '{') || (c == '[') || (c == '(')) {
stk.push(c);
} else if ((c == '}') || (c == ']') || (c == ')')) {
if (stk.empty()) return false;
if ((c == '}') && (stk.top() != '{')) return false;
if ((c == ']') && (stk.top() != '[')) return false;
if ((c == ')') && (stk.top() != '(')) return false;
stk.pop();
}
}
if (!stk.empty()) return false;
return true;
}

int main(int argc, char *argv[])
{
std::vector<std::string> true_tests = {"{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}"};
std::vector<std::string> false_tests = {"{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"};
std::cout << "True tests: " << std::all_of(true_tests.begin(), true_tests.end(), &check_brackets)
<< std::endl;
std::cout << "False tests: " << std::all_of(false_tests.begin(), false_tests.end(),
std::not1(std::function<bool(const std::string&)>(&check_brackets))) << std::endl;
}
```
25. matthew said

Nice couple of C(++) solutions, here’s another one that doesn’t use a stack, instead, for each opener we scan forwards to find the closer, then we overwrite both – now if we find an unerased closer, the string is unbalanced – not very efficient, but the output is pretty:

```#include <stdio.h>
#include <string.h>

bool balanced(const char *s)
{
char r[strlen(s)];
strcpy(r,s);
char *p = r;
for ( ; *p; p++) {
if (strchr(")]}",*p)) {
return false;
} else if (strchr("([{",*p)) {
int n = 1;
char *q = p+1;
for ( ; *q; q++) {
if (strchr("([{",*q)) n++;
else if (strchr(")]}",*q)) n--;
if (n == 0) break;
}
if ( n != 0 ||
(*p == '(' && *q != ')') ||
(*p == '[' && *q != ']') ||
(*p == '{' && *q != '}') ) {
return false;
} else {
*p = *q = '*';
fprintf(stderr,"%s\n", r);
}
}
}
return true;
}

int main(void)
{
const char *tests[] = {
"{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}",
"{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]",
"(((()())())())", "(((()())(])())",
"(((()())())()", "((())))))",
NULL
};
int i = 0;

while (tests[i] != NULL) {
printf("%s: %d\n", tests[i], balanced(tests[i]));
i++;
}

return 0;
}
```

Output:

```**
{}: 1
**
[]: 1
**
(): 1
a*b*c
a(b)c: 1
abc*d*
abc[d]: 1
a*b*c{d[e]}
a*b*c*d[e]*
a*b*c*d*e**
a(b)c{d[e]}: 1
{]: 0
(]: 0
a(b]c: 0
abc[d}: 0
a*b*c{d[e}]
a(b)c{d[e}]: 0
*((()())())()*
**(()())()*()*
***()()*()*()*
*****()*()*()*
********()*()*
***********()*
**************
(((()())())()): 1
*((()())(])()*
**(()())(]*()*
***()()*(]*()*
*****()*(]*()*
********(]*()*
(((()())(])()): 0
(((()())())(): 0
*(())*)))
**()**)))
******)))
((()))))): 0
```
26. matthew said

That should be r[strlen()+1] of course.

27. Rutger said
```
def valid_balanced_string(test, opening_brackets = "[{(", closing_brackets = "]})"):
stack = []
for c in test:
try:
i = opening_brackets.index(c)
stack.append(closing_brackets[i])
except:
pass

try:
i = closing_brackets.index(c)
if stack.pop() != closing_brackets[i]:
return False
except:
pass

return True

test_input = ["{}", "[]", "()", "a(b)c", "abc[d]", "a(b)c{d[e]}", "{]", "(]", "a(b]c", "abc[d}", "a(b)c{d[e}]"]

for test in test_input:
print "testing: ", test, "result = ", valid_balanced_string(test)
```
28. A beautifully simple perl version!

use strict;
use warnings;

## Run test….
my @to_test = ( ‘{}’, ‘[]’, ‘()’, ‘a(b)c’, ‘abc[d]’, ‘a(b)c{d[e]}’, ‘{]’, ‘(]’, ‘a(b]c’, ‘abc[d}’, ‘a(b)c{d[e}]’ )
printf ” %1s %s\n”, is_balanced(\$_)?’T’:’F’, \$_ foreach @to_test;

## Returns 1 if strings is balanced – don’t you just love perl
sub is_balanced {
( local \$_ = shift ) =~ s{[^{}[\]()]}{}g; ## Remove non-brackets…
0 while s{(\[\]|\{\}|\(\))}{}g; ## Remove pairs if we find them until there are none left
return !\$_; ## If we have left any brackets this will be non-empty or true!
}

29. Try that again with source code highlighting…

```use strict;
use warnings;

## Run test….
my @to_test = ( ‘{}’, ‘[]‘, ‘()’, ‘a(b)c’, ‘abc[d]‘, ‘a(b)c{d[e]}’, ‘{]’, ‘(]’, ‘a(b]c’, ‘abc[d}', 'a(b)c{d[e}]‘ );
printf ” %1s %s\n”, is_balanced(\$_)?’T’:’F’, \$_ foreach @to_test;

## Returns 1 if strings is balanced – don’t you just love perl
sub is_balanced {
( local \$_ = shift ) =~ s{[^{}[\]()]}{}g; ## Remove non-brackets…
0 while s{(\[\]|\{\}|\(\))}{}g; ## Remove pairs if we find them until there are none left
return !\$_; ## If we have left any brackets this will be non-empty or true!
}
```