The thirteen post of the series of programming job interview challenge is out, Only 13 comments with answers were provided to job interview challenge #12. This is a small amount comparing to the previous challenges, but I realize and understand that it was language specific and not very trivial challenge…

Jason Kikel was the first one to solve the question, and here is his short answer:

UnmanagedClass is referencing an address on ManagedClass without pinning it. The ManagedClass instance needs to be pinned so the GC won’t move it to another location during a collection.

pinIn other words, I didn’t use the _pin keyword when I allocated the managed class. The process of pinning a managed object, cause the Common Language Runtime (CLR) Garbage Collector (GC) not to relocate and move the object in memory. So, when we pass managed data to unmanaged code, pinning is necessary.

James Curran posted the solution in his blog – http://honestillusion.com/blogs/blog_0/archive/2008/07/16/dev102-s-challenge-12-managed-unmanaged.aspx.

Those are the other readers who provided a correct solution for last week challenge: befarino, leppie, Christof Jans and Jelle Hissink.

This Week Question:

Your input is a string which is composed from bracket characters. The allowed characters are:'(‘, ‘)’, ‘[‘. ‘]’, ‘{‘, ‘}’, ‘<‘ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.

Example of a legal expression: “([](<{}>))”.

Example of an illegal expression: “({<)>}”.

Provide the most efficient, elegant and simple solution for that problem.I think that this is a well known problem but I am not sure, so excuse me if this week’s question is screwed.

Get updates by RSS to catch up with the next posts in this series and to get the correct answer for today’s question. As always you may post the solution in your blog or comment. Comments with answers will be approved only next week.

Tags :

89 Responses to “A Programming Job Interview Challenge #13 – Brackets”


  1. sirrocco

    Said on July 21, 2008 :

    Use a stack.

    if (is open bracket)
    push(bracket)
    else if (is closing bracket) and (in the stack)
    pop(bracket)
    else if (is closing bracket) and (not in the stack)
    message not valid

  2. Omar

    Said on July 21, 2008 :

    I would use a stack, and expect the following to return true for valid input:

    initialise stack
    for each character c in input
    {

    if (isOpeningBrace(c))
    {
    stack.push(c)
    }
    else
    {
    bracket = stack.pop()
    if (bracket != c) return false
    }
    }

    // check that every opening bracket was closed
    if (stack.size() != 0) return false

    return true;

  3. Jason Kikel

    Said on July 21, 2008 :

    Use a stack. Read each character of the input string and if its a left bracket /[\(\{\[‘ matches ‘ 0 after the input string is fully read return invalid otherwise return valid.

  4. Mark R

    Said on July 21, 2008 :

    As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.

    C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.

  5. Mark R

    Said on July 21, 2008 :

    Ah, I forgot about the recursive solution.

    Create a function which takes a pointer or index into a string as an input/output parameter and returns true/false. If the string is empty, return true; otherwise examine the first character and return false if it is not an opening bracket. Advance the pointer and call the funtion recursively; if it returns false, return false as well. Otherwise check the next character from the input, if it’s the matching closing bracket advance the pointer and return true, otherwise return false.

  6. Trinity

    Said on July 21, 2008 :

    Here is my O(n) solution.

    You can use a stack to determine if the given input string is valid or not.

    1) Start at the beginning of the string and read it character by character.

    2) If the current character is an open bracket i.e. any one of (, [, {, then pop the element (head) of the stack and compare it with the current character. If they are of the same type, move to the next character. Else print error message saying that the string is not valid and exit.

    4) Do steps 2 and 3 till the end of the string. 5) If there are no more characters to process then print the input string is valid.

  7. James Curran

    Said on July 21, 2008 :

    My solution is posted here:
    http://honestillusion.com/blogs/blog_0/archive/2008/07/21/dev102-s-challenge-13-brackets.aspx

    (So, am I the first with full code?)

  8. Justin Etheredge

    Said on July 21, 2008 :

    Here is a quick C# solution:

    string parens = “()[]{}”;
    Stack stack = new Stack();
    foreach (char c in value)
    {
    int index = parens.IndexOf(c);
    if ((index % 2) == 0)
    {
    stack.Push(c);
    }
    else
    {
    if (stack.Count 0) return false;
    return true;

  9. Michael Mrozek

    Said on July 21, 2008 :

    Read the string from left to right. Push each opening symbol onto a stack. When a closing symbol is encountered, pop the stack and make sure the top of stack was the matching opening symbol. If it isn’t, or if the string is empty and the stack isn’t, the string is bad; otherwise, it’s good

  10. Nate

    Said on July 21, 2008 :

    How about this…

    namespace ConsoleApplication1
    {
    class Program
    {
    static void Main(string[] args)
    {
    Console.WriteLine(Validator.Validate(“([]())”));
    Console.WriteLine(Validator.Validate(“({}”));
    Console.WriteLine(Validator.Validate(“abc”));
    Console.ReadKey();
    }
    }

    static class Validator
    {

    static readonly List Starts = new List { ‘(‘, ‘[‘, ‘{‘, ‘<‘ };
    static readonly List Ends = new List { ‘)’, ‘]’, ‘}’, ‘>’ };
    private static readonly Dictionary Pairs = new Dictionary { { ‘(‘, ‘)’ }, { ” }, { ‘[‘, ‘]’ }, { ‘{‘, ‘}’ }, { ‘)’, ‘(‘ }, { ‘>’, ‘<‘ }, { ‘]’, ‘[‘ }, { ‘}’, ‘{‘ } };

    internal static string Validate(string input)
    {
    Stack current = new Stack();
    int index = -1;
    foreach (char value in input)
    {
    index++;
    if (Starts.Contains(value))
    {
    current.Push(value);
    }
    else if (Ends.Contains(value))
    {
    if (current.Peek() != Pairs[value])
    {
    return GetMessage(“Out-of-Sequence character”, value, index);
    }
    else
    {
    current.Pop();
    }
    }
    else
    {
    return GetMessage(“Illegal character”, value, index);
    }
    }
    return “Valid”;
    }

    private static string GetMessage(string message, char character, int charNumber)
    {
    return string.Format(“{0} – {1} – index {2}”, message, character, charNumber);
    }

    }

    }

  11. Kevin Hjelden

    Said on July 21, 2008 :

    Simply keep a stack of the open characters, and only allow a closing of the most recent one:

    string opens = “[{)”;
    bool validate(string s)
    {
    vector stack;
    foreach (char c in string)
    {
    if (c in opens)
    {
    // push on to stack when open character received
    stack.push(opens.position(c));
    }
    else if (c in closes)
    {
    // make sure it’s a valid closing
    int last = stack.pop();
    if (last != closes.position(c))
    return false;
    }
    else
    {
    // must be an opening or closing
    return false;
    }
    }
    return true;
    }

  12. Jeremy Weiskotten

    Said on July 21, 2008 :

    A simple stack would work. Iterate over each character in the string. If you have an open bracket, push it onto the stack. If you have a close bracket, pop the last start bracket you added off the stack and test for a match with your close bracket.

  13. hi

    Said on July 21, 2008 :

  14. Alex

    Said on July 21, 2008 :

    A recursive method would work best, which works as follows:

    Based on the first char in the string, find the index of the matching closing character.

    Example will be using: ({([][])}{}())[]
    Do this by counting- +1 for each instance of that opening character, -1 for each corresponding closing character, starting with the opening character. So ({([][])}{}())[] would be +1,+1,-1,+1,-1,-1. We’re at Zero, so that last ) is the one we want. If you get to the end of the string and never make it to 0, the whole thing is invalid. Return false.
    Otherwise, take the substring between the opening char (first char in this string) and closing char (whose index you just determined), and recursively call this function on that substring- in this example, it would be “{([][])}{}()”. If that returns false, return false. Otherwise, move on to the next substring peice: in this case, “[]”. Check every enclosed substring recursively this way, and if any of them return false, return false. If you make it to the end of the string and don’t have anything open-ended, and none of your recursively checked substrings returned false, than congrats! You’re valid. Return true.

  15. S Javeed

    Said on July 21, 2008 :

    Perl Solution. Run as follows:

    echo “({}” | perl ./brackets.pl
    echo “([]())” | perl ./brackets.pl

    or just run brackets.pl and enter the various strings followed by a newline after each string.

    Code:

    #!/usr/bin/perl

    sub checkBrackets ($) {
    my ($input) = @_;

    chomp $input;

    my $bracketType = {
    “(” => 0.1,
    “)” => 0.2,

    “[” => 1.1,
    “]” => 1.2,

    “{” => 2.1,
    “}” => 2.2,

    ” 3.1,
    “>” => 3.2,
    };

    my $status = 1;
    my $i = 0;
    my @stack = ();
    my $chr;

    for ($i = 0; $i {$chr});

    if ($type =~ /\.1$/) {
    push @stack, $chr;
    } elsif ($type =~ /\.2$/) {
    if (int($bracketType->{$chr}) == int($bracketType->{$stack[-1]})) {
    pop @stack;
    } else {
    last;
    }
    }
    }

    $status = 0 if (@stack);

    return $status;
    }

    while (my $line = ) {
    chomp $line;

    my $result = checkBrackets($line);

    print “$line: ” . ($result ? “LEGAL” : “ILLEGAL”) . “\n”;
    }

  16. Steven Baker

    Said on July 21, 2008 :

    easily done with a stack

  17. leppie

    Said on July 22, 2008 :

    I think this question is to tempt a Regex answer, but that will be wrong (and impossible!).

    The answer is simply using a stack, then moving left to write, pushing opening ‘parenthesis’ and and asserting when popping a closing ‘parenthesis’. Any assert fail, deems the sequence invalid.

  18. Morgan Cheng

    Said on July 22, 2008 :

    Solution: Iterate the string and track left brackets with a stack.

    Create a stack to hold all open left brackets. “Open” means we haven’t found its matching right brackets yet. For each char in the string (from left to right), if the stack is empty, we push current char into the stack only if it is a left bracket char, otherwise its a invalid string for sure; if the stack is not empty, we check whether current char is a left bracket or right bracket. For left bracket, we just push it to stack; for right bracket, we compare it with the top char in char. If they are matching brackets, we continue, otherwise it is a invalid string.

    After the string is iterated, if the stack is empty, it is valid string; otherwise it is invalid.

    Both time complexity and space complexity are O(n), since it traverse the whole string and need a O(n) stack. Below is a C#3 implementation.

    static Dictionary bracketPairs = new Dictionary()
    {
    { ‘)’, ‘(‘ },
    { ‘]’, ‘[‘ },
    { ‘>’, ‘<‘ },
    { ‘}’, ‘{‘ },
    };

    static HashSet m_leftBrackets = new HashSet() { ‘(‘, ‘[‘, ‘<‘, ‘{‘ };

    static HashSet m_rightBrackets = new HashSet() { ‘)’, ‘]’, ‘>’, ‘}’ };

    public static bool IsValidString(string str)
    {
    Stack bracketStack = new Stack();
    foreach (char ch in str)
    {
    if (bracketStack.Count == 0)
    {
    if (m_leftBrackets.Contains(ch))
    {
    bracketStack.Push(ch);
    }
    else
    {
    return false;
    }
    }
    else
    {
    if (m_leftBrackets.Contains(ch))
    {
    bracketStack.Push(ch);
    }
    else if (m_rightBrackets.Contains(ch))
    {
    char topChar = bracketStack.Pop();
    if (topChar != bracketPairs[ch])
    {
    return false;
    }
    }
    else
    {
    return false; // has invalid char
    }
    }
    }

    return (bracketStack.Count == 0);
    }

  19. Hello world

    Said on July 22, 2008 :

    #include
    #include

    static const unsigned char close_match[256] = {
    [‘(‘] ‘)’,
    [‘{‘] ‘}’,
    [”,
    [‘[‘] ‘]’,
    };

    static int
    match(const unsigned char *s)
    {
    unsigned char stack[strlen(s)];
    int sp = 0;

    for (; *s; s++) {
    if (close_match[*s]) {
    stack[sp++] = close_match[*s];
    } else if (sp == 0 || *s != stack[–sp]) {
    return 0;
    }
    }

    return sp == 0;
    }

    int
    main(int ac, char **av)
    {
    if (ac != 2) {
    printf(“Usage: %s string\n”, av[0]);
    return -1;
    }

    printf(“%slegal\n”, match((const unsigned char *) av[1]) ? “” : “il”);
    return 0;
    }

  20. Liming Zhang

    Said on July 22, 2008 :

    If one such expression is legal, it must contain at least on pair of bracket–one of leftward, one of righward, with no any other character between them.
    So, my solution:
    Search the whole string to find such a pair of bracket metioned above. If found, remove them, and search again.
    Condition of legal string: after times of removal, this string must become a string with length of zero.

  21. herval

    Said on July 22, 2008 :

    my quick and dirty solution:
    make a set of stacks, one for each character pair – pushing when it’s an open (, { or .
    – raise error when popping from an empty stack
    – raise an error at the end of the string, if any stack is still full

  22. Samuel Williams

    Said on July 22, 2008 :

    This should work! Hopefully ^_^

    #!/usr/bin/env ruby

    L = {“(” => “)”, “[” => “]”, “{” => “}”, ” “>”}

    good = “([]())”
    bad = “({}”

    # Performance is O(N) with memory requirement O(N/2)

    def check(input)
    # Stack to record what to expect next
    s = []

    input.split(//).each do |c|
    puts “#{c}: #{s.inspect}”
    if L.key? c
    s << L[c]
    else
    d = s.pop

    if d != c
    puts “Error got #{c} but expecting #{d}”
    return
    end
    end
    end
    end

    puts “Checking good…”
    check(good)
    puts “Checking bad…”
    check(bad)

  23. dextar

    Said on July 22, 2008 :

    My attempt in Python (was a fun way to try some python :-))

    def valid_str(str):
    stack = []
    brackets = { ”, ‘(‘ : ‘)’, ‘{‘ : ‘}’, ‘[‘ : ‘]’ }
    for c in str:
    closer = brackets.get(c)
    if closer != None:
    stack.append(closer)
    elif len(stack) == 0 or c != stack.pop():
    return False
    return len(stack) == 0

  24. dextar

    Said on July 22, 2008 :

    Oops! Don’t know how to write code in the comments.

    # brackets should also contain a less than and greater than pair, but it gets stripped as HTML tags I guess.
    # also, the indenting dissapears (which is very important in python.

    trying with a ‘pre’ below. If not, well, you know what I meant :-)

    def valid_str(str):
    stack = []
    brackets = { ”, ‘(‘ : ‘)’, ‘{‘ : ‘}’, ‘[‘ : ‘]’ }
    for c in str:
    closer = brackets.get(c)
    if closer != None:
    stack.append(closer)
    elif len(stack) == 0 or c != stack.pop():
    return False
    return len(stack) == 0

  25. macmariman

    Said on July 22, 2008 :

    Create a stack, iterate the input string, push char if it is any opening bracket. If it is closing bracket then compare with the top of the stack, if they are the ‘same kind’ (current char is closing bracket for the top of the stack) pop it and continue iteration else return false. At the end if the stack is empty return true else return false.

  26. Haskell programmer

    Said on July 22, 2008 :

    module Main () where
    main = do s <- getLine
    putStrLn $ match s []

    leftToRight c = case c of
    ‘ ‘>’
    ‘{‘ -> ‘}’
    ‘[‘ -> ‘]’
    ‘(‘ -> ‘)’
    otherwise -> ‘x’

    match (a:b) (c:d) | a == c = match b d
    match (a:b) c = match b ((leftToRight a):c)
    match [] [] = “legal”
    match _ _ = “illegal”

  27. Darrell Wright

    Said on July 22, 2008 :

    This is just a matter of pushing popping peeking a stack. Just push a valid left bracket and when a right bracket is encountered, peek at the top of the stack and see if it is the matching left bracket. If it isn’t, the string is invalid. If you finish and haven’t encountered an invalid, it is valid. Not many other ways to do this efficiently.

    public static bool checkBrackets( string testString ) {
    List leftBrackets = new List( ) { ‘(‘, ‘[‘, ‘{‘, ‘<‘ };
    List rightBrackets = new List( ) { ‘)’, ‘]’, ‘}’, ‘>’ };
    Stack stk = new Stack( );

    int pos;
    for( int n = 0; n = 0 ) {
    stk.Push( testString[n] );
    } else if( (pos = rightBrackets.IndexOf( testString[n] )) >= 0 ) {
    if( stk.Peek( ) != leftBrackets[pos] ) {
    return false;
    } else {
    stk.Pop( );
    }
    }
    }
    return true;
    }

  28. Ryan

    Said on July 22, 2008 :

    This is simply a LIFO stack. When you encounter a closing bracket, pop the last opening brace off the stack, if it’s not the corresponding opening bracket, then the input is illegal.

  29. Shams Mahmood

    Said on July 22, 2008 :

    This method works by looping through each of the characters and maintaining a stack of unmatched opening brackets. Whenever an opening bracket is found it is pushed into the stack, when a closing bracket is found the stack head is checked for the corresponding opening bracket. If such a bracket is found then the stack head is ‘popped’ else we report an error. At the end of this loop if the stack is empty then the expression is valid.
    Time complexity: O(n) [Each character is being processed with constant time to push, pop and peek the stack]
    Space complexity: O(n) [Maximum of n characters can be inside the stack at a time]

    public static boolean isExpressionValid(final String pInput) {

    Stack eOpeningBraces = new Stack();
    for( int i = 0; i < pInput.length(); i++ ) {
    char eLoopChar = pInput.charAt(i);

    if( isOpeningBrace(eLoopChar) ) {
    eOpeningBraces.push(eLoopChar);
    } else if( isClosingBrace(eLoopChar) ) {
    if( eOpeningBraces.isEmpty() ) {
    return false;
    }
    char eHeadOfStackChar = eOpeningBraces.peek();
    if( isOpenCloseMatching(eHeadOfStackChar, eLoopChar) ) {
    eOpeningBraces.pop();
    } else {
    return false;
    }
    }
    }
    return eOpeningBraces.isEmpty();
    }

    public static boolean isOpeningBrace(final char pInput) {
    return (
    (pInput == ”) ||
    (pInput == ‘)’) ||
    (pInput == ‘]’) ||
    (pInput == ‘}’)
    );
    }

    public static boolean isOpenCloseMatching(final char pOpen, final char pClose) {
    return (
    (pOpen == ”) ||
    (pOpen == ‘(‘ && pClose == ‘)’) ||
    (pOpen == ‘[‘ && pClose == ‘]’) ||
    (pOpen == ‘{‘ && pClose == ‘}’)
    );
    }

  30. Kimmen

    Said on July 22, 2008 :

    By using a hash table and a stack you will be able to verify the input. The hash table contains a map between the start bracket character and it’s corresponding end bracket. The stack holds all the end bracket characters that has to be matched.

    For each character, let’s call it a token, in the input string check if it’s a start bracket. If it is, put it’s corresponding end bracket in the stack. But if it’s not a start bracket, check with the top of the stack if the token is the end bracket we are looking for. If it is, pop if from the stack and continue. If the token is neither a start bracket nor the end bracket we are looking for, the input is invalid. After checking each token, the input string is valid if the stack is empty =).

    Here’s the code:
    private static IDictionary tTable = new Dictionary
    {
    {‘(‘,’)’},
    {‘[‘,’]’},
    {”},
    {‘{‘,’}’},
    };

    private static bool ParseBracketString
    (string input)
    {
    var tokens = new Stack(input.Length);

    foreach (var token in input)
    {
    if (tTable.ContainsKey(token))
    {
    tokens.Push(tTable[token]);
    }
    else if (tokens.Peek().Equals(token))
    {
    tokens.Pop();
    }
    else
    {
    return false;
    }
    }

    return tokens.Count == 0;
    }

  31. Terje Myklebust

    Said on July 22, 2008 :

    This is my solution:

    private static bool ValidateBrackets(IEnumerable inputString)
    {
    // I put all the allowed “bracket sets” into a dictionary.
    // This simplifies (shortens) the code, but is probably a bit
    // slower than doing direct comparision for each of our allowed characters
    // The closing bracket is put in as the key, because we only need to find our
    // opening bracket based on the closing bracket, not the other way around.
    var allowedBrackets = new Dictionary(4);
    allowedBrackets.Add(‘}’, ‘{‘);
    allowedBrackets.Add(‘)’, ‘(‘);
    allowedBrackets.Add(‘]’, ‘[‘);
    allowedBrackets.Add(‘>’, ‘<‘);

    // We add a stack where we will store all our currently
    // (as we iterate the string) opened brackets
    var openBrackets = new Stack(8);
    foreach (Char c in inputString)
    {
    // First we check if the current char is a opening bracket, and if it is,
    // we add it to our stack. If not, we check if it is a closing bracket
    // and follow up with a check to see that it is closing the last opened bracket
    // by looking up the value (opening bracket) in allowedBrackets using the key (closing bracket)
    if(allowedBrackets.ContainsValue(c))
    openBrackets.Push(c);
    else if(allowedBrackets.ContainsKey(c))
    {
    if(openBrackets.Pop() != allowedBrackets[c])
    return false;
    }
    }
    return openBrackets.Count == 0;
    }

  32. Jelle Hissink

    Said on July 22, 2008 :

    You could just walk through the string, and maintain a list of currently open brackets (FILO list). It could look like: (from my head, so it might not compile ;-)
    public bool CheckBrackets(string input) {
    Stack openBrackets = new Stack();
    foreach (char c in input) {
    char? expectedOpenBracket = null;
    switch (c) {
    case ‘{‘:
    case ‘[‘:
    case ‘(‘:
    case ”:
    expectedOpenBracket = ‘<‘;
    break;
    }
    if (expectedOpenBracket.HasValue) {
    if (openBrackets.Count == 0) {
    return false; // no open bracket, so no match
    }
    if (openBrackets.Pop() != expectedOpenBracket.Value) {
    return false; // no match
    }
    }
    }
    return openBrackets.Count == 0; // we should have closed all brackets by now…
    }

  33. Matt Howells

    Said on July 22, 2008 :

    Create a char stack.

    Iterate through each char in the string.

    If char is an opening, push it onto the stack.

    If char is a closing, pop a char off the stack and make sure they match (e.g. ‘{‘ and ‘}’)

    If they do not match or the stack was empty then the string is invalid.

    By returning the index of the char you have got to you could indicate to where the string is wrong.

  34. Dave Amphlett

    Said on July 22, 2008 :

    Here’s my first comment on these challenges. Nothing amazing just a pretty straight forward solution:

    public class ValidatingBracketStack
    {
    public static bool Validate(string input)
    {
    ValidatingBracketStack stack = new ValidatingBracketStack();
    foreach (char c in input.ToCharArray())
    if (!stack.Next(c))
    return false;
    return stack.IsEmpty;
    }

    private Stack _stack = new Stack();

    public bool Next(char c)
    {
    switch (c)
    {
    case ‘{‘:
    case ‘(‘:
    case ‘[‘:
    case ”:
    return PopAndMatchAgainst(‘<‘);
    default:
    return false;
    }
    }

    public bool IsEmpty
    {
    get { return _stack.Count == 0; }
    }

    private bool PopAndMatchAgainst(char c)
    {
    return (IsEmpty) ? false : (_stack.Pop() == c);
    }
    }

  35. levi

    Said on July 22, 2008 :

  36. levi_h

    Said on July 22, 2008 :

    I’m not sure whether my previous comment was added or not (it doesn’t seem that way), but I’ve written a solution in Java: http://docs.google.com/View?docID=dppnxf9_3zhpzzrgv

  37. Mark Brackett

    Said on July 22, 2008 :

    Iterate the char array, adding open tokens to a stack. When you hit a close token, verify that it matches the popped open tag.

    C#:
    // Note they’re in the same order
    const string OPEN = “([{“.ToCharArray();

    Stack openTokens = new Stack();

    foreach(char c in s.ToCharArray()) {
    if (int i = OPEN.IndexOf(c) >= 0) {
    // open token
    openTokens.Push(i);
    } else {
    // close or invalid token
    if (CLOSE[openTokens.Pop()) != c) {
    throw new InvalidFormatException();
    }
    }
    }

  38. configurator

    Said on July 22, 2008 :

    private static readonly Dictionary legalBrackets = new Dictionary { {‘(‘, ‘)’},
    {‘[‘, ‘]’},
    {‘{‘, ‘}’},
    {”}};

    private static bool Legal(string brackets) {
    Stack stack = new Stack();

    foreach (char c in brackets) {
    char closer;
    if (legalBrackets.TryGetValue(c, out closer))
    stack.Push(closer);
    else if (stack.Pop() != c)
    return false;
    }

    return stack.Count == 0;
    }

    ———————————————–

    Basically, we create a dictionary where the starting brackets points to the ending one.
    For each character, if the character is a starting bracket, we push the corresponding ending bracket to a stack. For every character that is not a starting bracket, the character must be the first character in the stack, so we Pop and compare.
    This code does not allow any character other than brackets; to allow, we would need to change the line
    if (stack.Pop() != c)
    to
    if (legalBrackets.ContainsValue(c) && stack.Pop() != c)

  39. Tim Kington

    Said on July 22, 2008 :

    boolean isValid(String str)
    {
    Stack stack = new Stack();

    for(int i = 0; i < str.length(); i++)
    {
    char c = str.charAt(i);
    switch(c)
    {
    case ‘(‘:
    case ‘{‘:
    case ‘[‘:
    case ”:
    if(c != stack.pop())
    return false;
    break;
    }
    }
    }

    This should really also catch StackEmptyException and return false there, too.

  40. valera

    Said on July 22, 2008 :

    Obvious solution:
    Some sort of finite-state machine,
    Complicity: o(n)
    Memory: not more than o(n)
    Algorithm (pseudo code):
    foreach(char C in inputString)
    {
    if(C is openingBracket) stack.push(C)
    else if(stack.pop() is not same bracket as C)
    return false;
    }
    return true;

    BTW Stack structure can be replaced with bit array of 2bit structures (to encode 4 types of brackets)

  41. Christof Jans

    Said on July 22, 2008 :

    static bool IsValid(string inputString)
    {
    Stack stack = new Stack();

    foreach (char c in inputString)
    {
    switch (c)
    {
    case ‘(‘:
    case ‘{‘:
    case ‘[‘:
    case ‘ 0 && stack.Peek() == ‘(‘) stack.Pop();
    else return false;
    break;

    case ‘}':
    if (stack.Count > 0 && stack.Peek() == ‘{‘) stack.Pop();
    else return false;
    break;

    case ‘]':
    if (stack.Count > 0 && stack.Peek() == ‘[‘) stack.Pop();
    else return false;
    break;

    case ‘>':
    if (stack.Count > 0 && stack.Peek() == ‘<‘) stack.Pop();
    else return false;
    break;
    }
    }

    return stack.Count == 0;
    }

  42. Mike G.

    Said on July 22, 2008 :

    Well, I don’t know if this is efficient, elegant, OR simple, but it is short :)

    In any language, I believe that the solution lies in eliminating matched “inner” pairs until either all the brackets have been eliminated, or something unmatched is found.

    This script does it by using perl substitutions to repeatedly remove the pairs. Success happens if the string is empty after all the removals possible are done.

    perl -ne’chomp; my $line=$_; while(s/\(\)//g||s///g||s/\[\]//g||s/\{\}//g){};if(length){print “$line is INVALID\n”;}else {print “$line is VALID\n”}’

  43. Michael

    Said on July 22, 2008 :

    Nice question, but very academical :).

    Stack is best structure for controlling nested elements.

    Algorithm is simple. If we found ‘open’ bracket push them to stack, if we found ‘close’ bracket and stack is empty or top of stack not equal arbitrary ‘open’ bracket for found ‘close’ bracket then we illegial string, otherwise we pop top element from the stack

    At the end if stack is empty then we have correct string without any nesting problem with brackets.

    Here is program:

    using System;
    using System.Collections.Generic;

    public class MyClass {
    static string openBrackets = @”{[)”;

    private static bool checkBrackets(string testString) {
    Stack brackets = new Stack();

    foreach (char c in testString) {

    if (openBrackets.IndexOf(c) != -1) {
    brackets.Push(c);
    } else {
    int pos = closeBrackets.IndexOf(c);
    if ( pos != -1) {
    if ((brackets.Count == 0) || (brackets.Peek() != openBrackets[pos]) ) {
    return false;
    } else {
    brackets.Pop();
    }
    }
    }
    }
    return (brackets.Count == 0);

    }

    public static void Main() {
    Console.WriteLine(String.Format(“String {0}: result: {1}”, @”{aaaaaaaa}”, checkBrackets(@”{aaaaaaaa}”)));
    Console.WriteLine(String.Format(“String {0}: result: {1}”, @”([]())”, checkBrackets(@”([]())”)));
    Console.WriteLine(String.Format(“String {0}: result: {1}”, @”({}”, checkBrackets(@”({}”)));
    Console.WriteLine(String.Format(“String {0}: result: {1}”, @”{aaaaaaa}”, checkBrackets(@”{aaaaaaa}”)));
    Console.WriteLine(String.Format(“String {0}: result: {1}”, @”(a”, checkBrackets(@”(a”)));
    }
    }

  44. Mike G.

    Said on July 22, 2008 :

    Ooops, after a bit of thought, this can be a lot shorter and clearer.

    perl -ne’1 while(s/\(\)||\[\]|\{\}//g);print “NOT ” if length>1;print”OK\n”‘

    Basically, remove all inner matching characters from the string, and repeat until you can’t.

  45. Charles

    Said on July 22, 2008 :

    Recursivly use a regex to find the groups with a pattern such as

    ([\(][\)])|([\[][\]])|([\{][\}])|([\])

    Check for a remainder when no matches are found. A remainder would indicate an invalid match

  46. Mike G.

    Said on July 22, 2008 :

    Note that for long strings, the O(n^2) nature of the s/// solution starts to bite. In that case, it’s better to code up something that keeps the seen string in memory and just deletes off the last character if it’s an opening character and it’s matching close is read. Otherwise, append the read character to the string.

  47. Jon von Gillern

    Said on July 22, 2008 :

  48. Richard Vasquez

    Said on July 22, 2008 :

    Just off the top of my head without thinking (and I’m sure there will be an exception to prove me wrong…) isn’t this solvable with a simple stack?

    Read through your string, and every time you have an opening bracket character, you push it into the stack.

    When you get a closing bracket character, you peek at the top of the stack and if it matches the closing bracket character, you pop and move on. Otherwise, throw an exception and call it a day.

    If you don’t have an empty stack when this is all done, throw an exception then as well.

    I’ll think on this some through the week and change my answer if something strikes me, but this is the pre-caffeine answer.

  49. Gerhard Balthasar

    Said on July 22, 2008 :

    I’ll try my luck:

    private static final String open = “([{“;

    public static boolean isLegal(String brackets) {
    int index;
    Stack s = new Stack();
    for (char c : brackets.toCharArray()) {
    index = open.indexOf(c);
    if (index >= 0) s.push((int)c);
    index = close.indexOf(c);
    if (index >= 0) {
    if (s.peek() == open.charAt(index)) s.pop(); else return false;
    }
    }
    return true;
    }

    Greeting, Gerhard

  50. Daniel Jimenez

    Said on July 22, 2008 :

    Wouldn’t a simple EBNF do this?

    To wit,
    Brackets ::= “”
    | ”
    | ‘(‘ Brackets ‘)’
    | ‘{‘ Brackets ‘}’
    | ‘[‘ Brackets ‘]’

    This assumes the empty string is a legal pair of (zero) brackets :-).

    EBNFs always look so nice, then they’re translated to yacc, or javacc, or antlr, and so much of the elegance is just … lost.

  51. ilitirit

    Said on July 22, 2008 :

    /* Doesn’t work with escaped chars could possibly made faster by checking if the stack is greater than half the length of the string */

    readonly static char [] openers = new char [] { ‘(‘, ‘[‘, ‘{‘, ” };

    public static bool IsValid(string input)
    {
    Stack brackets = new Stack(input.Length);
    int index;

    foreach (char character in input)
    {
    if ((index = (Array.FindIndex(closers, delegate(char c) { return (c == character); }))) >= 0)
    {
    if (brackets.Peek() == openers[index])
    brackets.Pop();
    else
    return false;
    }
    else if (Array.FindIndex(openers, delegate(char c) { return (c == character); }) >= 0)
    {
    brackets.Push(character);
    }
    }

    return (brackets.Count == 0);
    }

  52. Hugh Brown

    Said on July 22, 2008 :

  53. Hegi

    Said on July 22, 2008 :

    A rather easy one. It’s classic CS problem.
    Most natural option is usage of stack data structure. Whenever we see left bracket of any kind we push in on a stack. Whenever we see right bracket we look what is on top of the stack, if it is matching bracket we pop it. If not, report that strcture is illegal. If there is no bracket to read, than we check whether stack is empty. If so, bracket were placed correctly, otherwise we report illegal structure.

    It’s maximum O(n/2) in memory usage.
    Perhaps there is a better solution using balance method. Not quite sure how to implemet it for multiple brackets, though.

    Using one set of brackets it’s pretty easy. If left bracket increase balance by one. If right than decrase it. If balance drops below zero, than error. At the end baalnce must be equal to 0.

  54. Sayre

    Said on July 22, 2008 :

    use a stack

  55. Dejan Dimitrovski

    Said on July 22, 2008 :

    VB solution

    Function CheckMatchingBraces(ByVal testString As String) As Boolean

    Const OPEN_BRACES As String = “({]”

    Dim valid As String = True
    Dim stackBraces As New Stack(Of Char)

    For Each character As Char In testString.ToCharArray
    If OPEN_BRACES.IndexOf(character) > -1 Then
    stackBraces.Push(character)
    Else
    ‘a closing brace so the next character in the stack
    ‘must be the coresponding opening brace
    If OPEN_BRACES.Chars(CLOSE_BRACES.IndexOf(character)) stackBraces.Pop Then
    Return False
    End If
    End If
    Next

    Return True
    End Function

    One caveat, the closing brace characters in the closing bracket string must be in the same order as the corresponding open braces in the open braces string

  56. Phi

    Said on July 22, 2008 :

    while( char = readchar()){
    if(char.isLeftBracket()) {
    stack.push(char)
    } else {
    if(char != stack.pop()) {
    return false
    }
    }
    }

    return true

  57. DaveG

    Said on July 22, 2008 :

    Solution with test cases is posted on my blog. Basic php solution is here:
    function brackets ($t) {
    $open = ‘({]';

    $fail = (strlen($t)==1);
    for ($i=0; (!$fail && $i<strlen($t)); $i++) {
    $curr = substr($t,$i,1);
    if ( strpos($open, $curr) === false ) {
    $fail = ( $i==0 || ( strpos($open,substr($prev,-1)) != strpos($close,$curr) )) ;
    if (!$fail) $prev = substr($prev,0,-1);
    } else $prev .= $curr;
    }
    return $fail;
    }

  58. ZagNut

    Said on July 22, 2008 :

  59. Xerxes

    Said on July 22, 2008 :

    Hi – please find my submission for the problem here:

    http://www.xerxesb.com/2008/a-programming-job-interview-challenge-13-brackets/

  60. Arni Hermann

    Said on July 23, 2008 :

    An easy solution comes to mind… You use a stack where you push onto it whenever a specific bracket opens and pop whenever the opposite bracket closes. The resulting stack should be empty or otherwise there’s an illegal state.

  61. Carl Anderson

    Said on July 23, 2008 :

    One approach: iterate through string pushing left bracket characters onto a stack, and popping off a character when a right character is encountered. If the current character and the popped off character do not form a matching pair, it is not a valid string:

    public class Dev102_19 extends TestCase{

    public static boolean validate(String s){
    if (s==null || s.equals(“”))return false;
    Stack stack = new Stack();
    for (int i = 0 ; i < s.length() ; i++){
    Character c = s.charAt(i);
    if (c=='(‘ || c=='[‘ || c=='{‘ || c=='<‘){
    stack.push(c);
    }
    else{
    if (stack.size()<1)return false;
    Character p = stack.pop();
    //if bracket doesn’t form a matching pair, it is not valid:
    if (p=='(‘ && c!=’)’)return false;
    if (p=='[‘ && c!=’]’)return false;
    if (p=='{‘ && c!=’}’)return false;
    if (p==”)return false;
    }
    }
    if (stack.size()>0)return false;//valid string will produce an empty stack
    return true;
    }

    public void testValidate(){
    assertTrue(validate(“([]())”));
    assertTrue(validate(“{}”));
    assertTrue(validate(“{{}}”));
    assertFalse(validate(“”));
    assertFalse(validate(“({}”));
    assertFalse(validate(“>>”));
    assertFalse(validate(“>”));
    assertFalse(validate(“<“));
    assertFalse(validate(null));
    }
    }

  62. bartek szabat

    Said on July 23, 2008 :

    using System;
    using System.Collections.Generic;
    using System.Diagnostics;

    public static class BracketExpressionValidator
    {
    private static int[] map = new int[char.MaxValue];
    private static int bc = 0;

    public static void AddBracketDefinition(char opener, char closer)
    {
    bc++;

    map[opener] = bc;
    map[closer] = -bc;
    }

    static BracketExpressionValidator()
    {
    AddBracketDefinition(‘(‘, ‘)’);
    AddBracketDefinition(‘[‘, ‘]’);
    AddBracketDefinition(‘{‘, ‘}’);
    AddBracketDefinition(”);
    }

    ///
    /// Validates brackets expression (see http://www.dev102.com/2008/07/21/a-programming-job-interview-challenge-13-brackets/ )
    ///
    /// brackets expression
    /// True is expression is legal, false if expression is illegal
    public static bool Validate(string expression)
    {
    Stack stack = new Stack();

    foreach (char c in expression)
    {
    int code = map[c];

    //if (code == 0)
    //{
    // throw new Exception(“Disallowed character”);
    //}
    Debug.Assert(code != 0);

    if (code > 0)
    stack.Push(code);
    else
    {
    if (stack.Count==0 || stack.Pop() != -code)
    return false;
    }
    }

    return stack.Count == 0;
    }

    }

  63. gav

    Said on July 23, 2008 :

    Solution in F#
    http://pastebin.org/56336

  64. Richard Harrison

    Said on July 23, 2008 :

    I thought about using regular expressions, but honestly I’m not sure what kind of overhead we might have. Also, as the question stated that the input is composed from the bracket characters, no validation occurs within the function I provided. Here is my solution to #13:

    private bool AreBracketsValid(string input)
    {
    const string OPEN = “([{“;

    bool result = true;

    Stack s = new Stack();

    foreach (char c in input)
    {

    // Push open characters to stack
    if (OPEN.Contains(c))
    {
    s.Push(c);
    }

    // If close character matches open character, remove open character from stack
    else if (OPEN.IndexOf(s.Peek()) == CLOSE.IndexOf(c))
    {
    s.Pop();
    }

    // No match, invalid brackets
    else
    {
    result = false;
    break;
    }
    }

    return result;
    }

  65. Richard Harrison

    Said on July 23, 2008 :

    Hmmm…okay, some code is getting dropped out when I post it…here’s a URL with the code instead:

    http://testing.iontier.com/stuff/Challenge13.txt

  66. Klemen K.

    Said on July 24, 2008 :

    I think this problem is fairly straight forward, although i’m not sure if it’s the most efficient… You just have to keep track of opening and closing brackets, stack like. If they don’t match up, then we have an illegal expression.

    If i take your example:
    ([]())
    i’d go character by character and remember that the first one is opening ‘(‘, the second one is opening ‘[‘, the third one is closing ‘]’ which is ok, because the previous first opening (from back forward) was of the same type ‘[‘ etc etc

    ({}
    1. opening ‘(‘
    2. opening ‘{‘
    3. opening ‘<‘
    4. closing ‘)’ <- error, because the previous first opening was of a different type

    And you can have an optimisation and before going into this checking, just count how many openings and closings there is and if the numbers don’t match up… it’s illegal. But this optimisation wouldn’t work in these two cases.

  67. Hegi

    Said on July 24, 2008 :

    I’ve put my solution on my newly founded blog. Enjoy!

  68. Petar Petrov

    Said on July 24, 2008 :

    Here’s my solution:
    private static List patterns = new List() { “()”, “[]”, “{}”, “” };
    public static bool IsValidExpression(string expression)
    {
    if (expression.Length > 0)
    {
    foreach (var p in patterns)
    {
    var hasValidPattern = expression.Contains(p);
    if (hasValidPattern)
    {
    return IsValidExpression(expression.Replace(p, string.Empty));
    }
    }
    }
    return expression.Length == 0;
    }
    I think this solution meets all requirements ( simple, elegant and efficient).

  69. Niranjan Viswakarma

    Said on July 29, 2008 :

    Assuming that the different bracket types have no priority among them as such, as is usually the case with mathematical expressions, for e.g u cannot have a ‘{‘ within a ‘(‘, etc.. i.e, “{a*(b+c)}” is valid while “(a*{b+c})” is not.

    Use a counter variable to mimic the operation of a stack.

    Start scanning the expression left to right.
    Every time a left bracket of any kind, ie ‘(‘, ‘{‘, ‘[‘ or ” is encountered, decrement the counter by 1.

    (The Increment stands for the push operation and the Decrement, for the pop operation)

    At the end of the expression, if the counter is zero, it is legal. Otherwise, the expression is illegal.

    Time Complexity: O(n)
    Space Complexity: O(1)

  70. Michael Dikman

    Said on July 29, 2008 :

    Simple:
    Iterating over the input. Putting every opening bracket into a stack. On every closing bracket i dequeue top element from the stack and compare if they match. If they match i go on, otherwise its illegal.

  71. Chris Marisic

    Said on July 30, 2008 :

  72. Alessio Spadaro

    Said on July 31, 2008 :

    If you have a stack available you can push each open bracket and, for each closing bracket, check if it match the top of the stack. If it does, pop the matching bracket. If it doesn’t (either for the wrong bracket or because the stack is empty) the string is illegal.
    If at the end of the string the stack is not empty, the string is illegal.
    this is linear (O(n)) in both space and time.
    A solution with O(1) space would use the input string itself as a stack, using an index for the top of the stack and another to scan the string, with the very same alghoritm.

  73. Santa

    Said on July 31, 2008 :

    We can use a stack and insert tokens(if it is a opening bracket) or pop tokens(if it is a closing bracket, until a matching opening bracket is popped).

    When the end of the expression is encountered we should have the stack empty and at no point during the process we should pop out a null value from the stack.

  74. Marcos Silva Pereira

    Said on August 1, 2008 :

    Iterate the String:

    If you get a opening token put the correspondent token that close in a stack.

    If you get a ending token, pop a item from the stack and see if it’s equals to the current token, if not, you get an invalid expression.

    Verify, at the end of iteration, if the stack is empty or not. An non empty stack indicates an invalid expression, per instance, “{<[“.

    Kind Regards

  75. Joost Morsink

    Said on August 4, 2008 :

    There was a syntax error in my previous post…

    class Program
    {
    private static Dictionary openClose = new Dictionary { { ‘(‘, ‘)’ }, { ” }, { ‘[‘, ‘]’ }, { ‘{‘, ‘}’ } };

    static void Main(string[] args)
    {
    Console.WriteLine(IsSyntaxCorrect(args[0]));
    }

    static bool IsSyntaxCorrect(string s){
    var stack=new Stack();
    foreach (var ch in s)
    if (openClose.ContainsKey(ch))
    stack.Push(openClose[ch]);
    else if (stack.Count == 0 || stack.Peek() != ch)
    return false;
    else
    stack.Pop();
    return true;
    }
    }

  76. Arjan Bosma

    Said on August 7, 2008 :

    Not impossible. Just a lot of work to get right.

    static bool IsValidExpression(string expression)
    {
    Regex rxExpression = new Regex(@”^((?{(?.*)})|(?\[(?.*)\])|(?\((?.*)\)))+$”);
    bool bReturn = rxExpression.IsMatch(expression);
    foreach (Match m in rxExpression.Matches(expression))
    {
    Capture c = m.Groups[“sub”];
    if (c.Length > 0)
    {
    bReturn = IsValidExpression(c.ToString());
    if (bReturn == false)
    break;
    }
    }
    return (bReturn);
    }

  77. Phil Klein

    Said on August 19, 2008 :

    With nearly every solution utilizing a stack, I thought I’d try and approach the problem differently. Here’s an alternative solution:

    public bool ValidateBrackets(string input)
    {
    string brackets = Regex.Replace(input, @”[^\{\}\[\]\(\)\]+”, String.Empty);

    if (brackets.Length % 2 != 0) return false;
    else
    {
    int length;
    do
    {
    length = brackets.Length;
    brackets = brackets.Replace(“{}”, String.Empty)
    .Replace(“[]”, String.Empty)
    .Replace(“()”, String.Empty)
    .Replace(“”, String.Empty);
    } while (length > brackets.Length);
    return brackets.Length == 0;
    }
    }

  78. Phil Klein

    Said on August 19, 2008 :

    Unfortunately my < and > were removed from my post above. Please take that into account.

  79. Joseph Porter

    Said on December 27, 2008 :

    If you’re looking for some other good programming interview questions, check out:

    http://www.programmerinterview.com/

10 Trackback(s)

  1. Jul 21, 2008: Honest Illusion : Dev102's Challenge #13 : Brackets
  2. Jul 21, 2008: Validating a stack sequence - alex.moskalyuk
  3. Jul 22, 2008: The Tomes Of Experience » A Programming Job Interview Challenge #13 - Brackets
  4. Jul 22, 2008: Balanced parenthesis » FSharp.it
  5. Jul 23, 2008: Validating use of Parenthesis • OJ’s rants
  6. Jul 25, 2008: nWizard - Norbert Rakosi’s blog on Free Software development … JAVA … Personal Development… and … bad speling… » A Programming Job Interview Challenge #13 - Brackets
  7. Jul 30, 2008: A Programming Job Interview Challenge #13 « dotNetChris
  8. Aug 1, 2008: Passing Curiosity » Blog Archive » Matching Brackets in Haskell
  9. Aug 5, 2008: A PROGRAMMING JOB INTERVIEW CHALLENGE #14 - 2D GEOMETRY | Dev102.com
  10. Aug 11, 2008: Passing Curiosity » Blog Archive » Matching Brackets in Cocoa

Post a Comment