using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace SO13389560Balancing
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "~(a b (c) d (e f (g) h) i) j (k (l (m) n) p) q";
            string pattern = @"
(?<=
    (?(Depth)(?!))          # 4. Finally, make sure there are no extra closed parentheses.
    ~\(
    (?>                     # (non backtracking)
        [^()]               # 3. Allow any other character
        |
        \( (?<-Depth>)?     # 2. When seeing an open paren, decreace depth if possible.
                            #    Also allow excess parentheses: '~((((((a' is OK.
        |
        (?<Depth>  \) )     # 1. When seeing a closed paren, add to depth.
    )*
)
\w                          # Match your letter";
        

            s = Regex.Replace(s, pattern, "!", RegexOptions.IgnorePatternWhitespace);

            Console.WriteLine(s);
            //Console.ReadKey();
        }
    }
}