Count String - Use recursive solution - much more easy to follow and understand! Excellent code

countString2.cs

using System;
using System.Collections.Generic;
using System.IO;

class CountStrings
{
    static Dictionary<string, long> knowen = new Dictionary<string, long>();

    static void Main(string[] args)
    {
        long countTestCases = Convert.ToInt64(System.Console.ReadLine());

        for (long k = 0; k < countTestCases; k++)
        {

            string[] input = System.Console.ReadLine().Split(' ');
            string regexp = input[0];
            int n = Convert.ToInt32(input[1]);

            long result = Count(regexp, n);

            Console.WriteLine(result);
        }
    }

    static long Count(string regexp, int n)
    {
        if (regexp.Length == 1)
        {
            if (n == 1)
                return 1;
            else
                return 0;
        }

        if (knowen.ContainsKey(regexp + n))
        {
            return knowen[regexp + n];
        }

        regexp = regexp.Substring(1, regexp.Length - 2);

        long result;
        if (regexp[regexp.Length - 1] == '*')
        {
            string r1 = regexp.Substring(0, regexp.Length - 1);

            if (n == 0)
                return 1;

            result = 0;
            for (int i = 1; i <= n; i++)
            {
                result += Count(r1, i) * Count("(" + regexp + ")", n - i);
                result %= 1000000007;
            }
        }
        else if (isOrExpression(regexp) >= 0)
        {
            int posDevider = isOrExpression(regexp);
            string r1 = regexp.Substring(0, posDevider);
            string r2 = regexp.Substring(posDevider + 1, regexp.Length - posDevider - 1);

            result = Count(r1, n) + Count(r2, n);
            result %= 1000000007;
        }
        else
        {
            int posDevider = isAndExpression(regexp);
            string r1 = regexp.Substring(0, posDevider + 1);
            string r2 = regexp.Substring(posDevider + 1, regexp.Length - posDevider - 1);

            result = 0;
            for (int i = 0; i <= n; i++)
            {
                result += Count(r1, i) * Count(r2, n - i);
                result %= 1000000007;
            }
        }

        knowen.Add("(" + regexp + ")" + n, result);

        return result;
    }

    private static int isOrExpression(string regexp)
    {
        Stack<char> braces = new Stack<char>();

        for (int i = 0; i < regexp.Length; i++)
        {
            char c = regexp[i];

            if (c == '(')
            {
                braces.Push(c);
            }
            else if (c == ')')
            {
                braces.Pop();
            }
            else if (c == '|')
            {
                if (braces.Count == 0)
                    return i;
            }
        }

        return -1;
    }

    private static int isAndExpression(string regexp)
    {
        Stack<char> braces = new Stack<char>();

        if (regexp[0] == 'a' || regexp[0] == 'b')
            return 0;

        for (int i = 0; i < regexp.Length; i++)
        {
            char c = regexp[i];

            if (c == '(')
            {
                braces.Push(c);
            }
            else if (c == ')')
            {
                braces.Pop();

                if (braces.Count == 0)
                    return i;
            }
        }

        return -1;
    }
}