using System;

namespace ValidBrackets
{
    class Program
    {
        static void TestResult(string expected, string actual)
        {
            if (expected != actual)
                throw new Exception($"Wrong answer, expected {expected}, got {actual}");
        }
        static void Main(string[] args)
        {
            try
            {
                TestResult("valid", Validate("()()()()()"));
                TestResult("invalid", Validate(")("));
                TestResult("invalid", Validate("(((**"));
                TestResult("valid", Validate("*"));
                TestResult("valid", Validate(""));
                TestResult("valid", Validate("***"));
                TestResult("valid", Validate("**"));
                TestResult("valid", Validate("(**)"));
                TestResult("valid", Validate("****))"));

                Console.WriteLine("All pass");
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }

        static string Validate(string brackets)
            => Validate(brackets, 0, 0) ? "valid" : "invalid";

        // Increment bracketsChecker when we see an '(' and decrement when we see a ')'.
        static bool Validate(string brackets, int index, int bracketsChecker)
        {
            if (index == brackets.Length)
            {
                // at the end of the string, if the checker is zero, then brackets match
                return bracketsChecker == 0;
            }

            return brackets[index] switch
            {
                '(' => Validate(brackets, index + 1, bracketsChecker + 1),

                // When we see a ')' it's important to validate that there was a '(' before it.
                // Otherwise, ')(' would be considered valid
                // 'bracketsChecker > 0' asserts that
                ')' => bracketsChecker > 0 && Validate(brackets, index + 1, bracketsChecker - 1),

                // use conditional ||, if one of the three returns true, then we have a valid option
                '*' => Validate(brackets, index + 1, bracketsChecker + 1) ||  // treat * as (
                       Validate(brackets, index + 1, bracketsChecker) ||      // treat * as nothing
                       Validate(brackets, index + 1, bracketsChecker - 1),    // treat * as )

                _ => throw new Exception("Wrong symbol")
            };
        }
    }
}