Brackets

You are given a string S containing a collection of N brackets. You must determine whether the brackets are properly nested; this is the case if:

  • S is empty;
  • S has the form “(U)” or “[U]” or “{U}” where U is a properly nested string;
  • S has the form “VW” where V and W are properly nested strings.

for example the string “{[()()]}” is properly nested but “([)()]” is not.

Assumptions

  • N is an integer within the range [0..200,000] (so guard for empty inputs. An empty string is properly nested.)
  • string S consists only of the following characters: “(“, “{“, “[“, “]“, “}” and/or “)“, so you don’t need to guard for invalid characters.

Programming language used: C#

Solution:

The clue is in the theme of the lesson: use a stack. You push each bracket onto the stack, and if another bracket is pushed on immediately afterwards that closes the parentheses then you pop both. An empty stack after processing each character in S indicates S was properly nested.

bracketsolution