using System;

using System.Collections.Generic;

​

public class Program

{

​

    /*

    * Validate brackets tests:

    *   "abc(abc)"   = true

    *   ")abc(abc)"  = false

    *   "a(bc(abc))" = true

    *   "a(bc(abc)"  = false

    */

    public static void Main()

    {

        foreach (var s in new[] {"abc(abc)", ")abc(abc)", "a(bc(abc))", "a(bc(abc)" })

        {

            Console.WriteLine(string.Format("{0} = {1}", s, ValidateBrackets(s)));

        }

    }

    public static bool ValidateBrackets(string input)

    {

        // Use stack because we can push and pop on in order and verify brackets. LIFO.

        var parentheses = new Stack<char>();

​

        // Loop through each character to check it.

        // O(n)

        foreach (char chr in input)

        {

            // Check if the 'chr' is an open parenthesis, and store it on the stack if so.

            // O(1)

            if (chr == '(')

            {

                parentheses.Push(chr);  // Add bracket to stack.

            }

            // Check if the 'chr' is a close parenthesis, and if it is, pop the previous char and verify it was an open bracket.

            else if (chr ==')')

            {

                if (parentheses.Count == 0)

                {

                    return false;

                }

​

                // O(1)

                if (parentheses.Pop() != '(')

                {

                    return false;

                }

            }

        }

        // Return 'true' if there is no open parentheses, and 'false' if there are.

        return parentheses.Count == 0;

    }

}