Balanced Delimiters
June 10, 2014
Although the interviewer didn’t say so explicitly, the task is to write a function that determines if the parentheses, brackets and braces are properly balanced in a string. Here’s our solution, which copies opening parentheses, brackets and braces into a stack and matches the corresponding closing parentheses, brackets and braces, discarding everything else:
(define (balanced? str)
(let ((starters '(#\( #\[ #\{)) (enders '(#\) #\] #\})))
(let loop ((cs (string->list str)) (xs (list)))
(cond ((null? cs) (null? xs)) ; #t if stack is empty, or #f
((member (car cs) starters) ; push starter on stack
(loop (cdr cs) (cons (car cs) xs)))
((member (car cs) enders) ; pop matching ender from stack, or #f
(and (pair? xs)
(or (and (char=? (car xs) #\() (char=? (car cs) #\)))
(and (char=? (car xs) #\[) (char=? (car cs) #\]))
(and (char=? (car xs) #\{) (char=? (car cs) #\})))
(loop (cdr cs) (cdr xs))))
(else (loop (cdr cs) xs)))))) ; neither starter nor ender
A programmer with a recent computer science degree will immediately recognize the problem of balanced delimiters and know to use a stack; the self-taught programmer, or one who didn’t pay attention at school, or one who’s been out of school for a while, will have more trouble answering the interviewer.
You can run the program at http://programmingpraxis.codepad.org/qNiI3O3Y, where you will also see that it passes all of the interviewer’s test cases.
The previous exercise used a finite state machine to match consecutive identical characters. Although today’s exercise seems similar, it can’t be solved by a simple finite state machine because matches are permitted to be nested; a finite state machine can’t count the matches. That’s why we need the stack.
Programming Praxis 
[…] all programming interview questions, this one is contrived… and it is also succinct, precise, pleasant, and […]
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))))))))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));
}
——————
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));
}
Use the call stack as the bracket matching stack:
(define (match-brackets [matching #f]) (define pairs '((#\( . #\)) (#\{ . #\}) (#\[ . #\]))) (define c (read-char)) (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)]))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.
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 listAnd a very simple Markov program:
$ cat delim.mkv () => [] => {} => ( =>. ( [ =>. [ { =>. { ) =>. ) ] =>. ] } =>. } $ ./markov "((({()[(([{}][]){})]{}})))" < delim.mkv ((({()[(([{}][]){})]{}}))) ((({[(([{}][]){})]{}}))) ((({[(([{}]){})]{}}))) ((({[(([]){})]{}}))) ((({[((){})]{}}))) ((({[({})]{}}))) ((({[()]{}}))) ((({[]{}}))) ((({{}}))) ((({}))) ((())) (()) () $ ./markov "(()(])" < delim.mkv (()(]) ((]) ((])Now for something completely different.
import re def balanced(s): # Remove everything that's not a delimiter. t = re.sub(r'[^]})[{(]', '', s) while t: # remove matched, adjacent delimiters u = re.sub(r'\(\)|\[\]|\{\}', '' , t) if u == t: # no more balanced delimiters return False t = u return True@Mike – nice, but not that different to my Markov program.
Actually, I don’t need all those silly rules for termination – Markov programs terminate if no rules apply, so we can just have:
() => [] => {} =>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']
A solution in Haskell:
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
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}]A Haskell solution to add to the list:
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]
Apologies for the typo! It’s been a while since I posted here, apparently.
#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[0]
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]
“`
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[0]
stack << char
elsif char == pair[1] && head == pair[0]
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
“`
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[0] stack << char elsif char == pair[1] && head == pair[0] 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.inspectApologies for the two fodder comments. I thought this used markdown.
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}]"I meant Graham there, not John. Can’t tell the difference between Ruby and Haskell.
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 balancedSome 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; }in main: int i = 0; (shame on me)
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; }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 *(())*))) **()**))) ******))) ((()))))): 0That should be r[strlen()+1] of course.
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)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!
}
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! }