Regex to first match, then replace found matches

Question

In my C# program I am using Regular expressions to:

• Loop through a list of possible words in need of replacing.
• For each word, to find out if a string I am given has any matches.
• If it does, I perform some (slightly costly) logic to create the replacement.
• I then perform the actual replacement.

My current code looks roughly as follows:

string toSearchInside; // The actual string I'm going to be replacing within
List<string> searchStrings; // The list of words to look for via regex

string pattern = @"([:@?]{0})";
string replacement;

foreach (string toMatch in searchStrings)
{
    var regex = new Regex(
                            string.Format(pattern, toMatch), 
                            RegexOptions.IgnoreCase
                            );
    var matches = regex.Matches(toSearchInside);

    if (matches.Count == 0)
        continue;

    replacement = CreateReplacement(toMatch);

    toSearchInside = regex.Replace(toSearchInside, replacement);
}

And I can get this working, but it seems somewhat inefficient in that it is using the regex engine twice - Once to find the matches (regex.Matches()) and once for the replacing regex.Replace()). I was wondering if there was a way to simply say replace the matches you already found?

Also, if has been asked what is within the CreateReplacement() method since it could be possibly done via a Match Elevator, but it is actually a separate method that's fairly costly and not really what I'm asking in this case - My bigger question here is how to deal with this situation of having to use Regex twice - Once to find the matches and then a second time to replace them.

I hope that what I'm trying to find out how to do actually makes sense.

Answer 1

Regex.Matches returns a MatchCollection which contains Matches which captures the index and length of each match. So as such you won't have to fire up the regex engine again because you can do something like this:

string toSearchInside; // The actual string I'm going to be replacing within
List<string> searchStrings; // The list of words to look for via regex

string pattern = @"([:@?]{0})";
string replacement;

foreach (string toMatch in searchStrings)
{
    var regex = new Regex(
                            string.Format(pattern, toMatch), 
                            RegexOptions.IgnoreCase
                            );
    var matches = regex.Matches(toSearchInside);

    if (matches.Count == 0)
        continue;

    replacement = CreateReplacement(toMatch);

    // in case the replacement is of a different length we replace from
    // from back to front to keep the match indices correct
    foreach (var match in matches.Cast<Match>().Reverse())
    {
        toSearchInside = toSearchInside.Replace(match.Index, match.Length, replacement);
    }
}

Unfortunately the .NET framework doesn't come with a positional Replace so we have to create one which I did as an extension method:

public static string Replace(this string s, int index, int length, string replacement)
{
    var builder = new StringBuilder();
    builder.Append(s.Substring(0,index));
    builder.Append(replacement);
    builder.Append(s.Substring(index + length));
    return builder.ToString();
}

If you do this often and the match patterns don't change you could consider two things:

• Pre-compile the regular expressions
• Pre-create the replacements

Answer 2

To improve @ChrisWue's answer I would like to suggest having 2 extension methods, one acting on a MatchCollection and the other acting on a Match like so

public static class RegexExtensions
{
    public static string Replace(this MatchCollection matches, string source, string replacement)
    {
        foreach (var match in matches.Cast<Match>())
        {
            source = match.Replace(source, replacement);
        }
        return source;
    }
    public static string Replace(this Match match, string source, string replacement)
    {
        return source.Substring(0, match.Index) + replacement + source.Substring(match.Index + match.Length);
    }
}  

I have omitted the usually required null checks for these methods because something should be left for you to do.

In addition I have replaced he StringBuilder usage in favour of simple one line string concatenation using + because this is automatically using internaly a StringBuilder

I would like to encourage you to always use braces {} although they might be optional. Using them just helps you to make your code less error prone.

Implementing this changes lead to

string toSearchInside; // The actual string I'm going to be replacing within
List<string> searchStrings; // The list of words to look for via regex

string pattern = @"([:@?]{0})";
string replacement;

foreach (string toMatch in searchStrings)
{
    var regex = new Regex(
                            string.Format(pattern, toMatch), 
                            RegexOptions.IgnoreCase
                            );
    var matches = regex.Matches(toSearchInside);

    if (matches.Count == 0)
    {
        continue;
    }

    replacement = CreateReplacement(toMatch);

    toSearchInside = matches.Replace(toSearchInside, replacement);
}

Answer 3

You don't have to run the same regex twice by first checking if it matches and then replacing parts. You can do everything in a single call to Regex.Replace. If it won't match then the string remains unchanged.

foreach (var toMatch in searchStrings)
{
    toSearchInside = Regex.Replace(
        toSearchInside, 
        string.Format(pattern, toMatch), 
        CreateReplacement(toMatch), 
        RegexOptions.IgnoreCase);
}

---

If you need more control over the replacement process you can use the MatchEvaluator. This will allow you to evaluate each single replacement.

This is not exactly what you are doing in your code but in case you should need it here's an example:

foreach (var toMatch in searchStrings)
{
    var regex = new Regex(string.Format(pattern, toMatch), RegexOptions.IgnoreCase);

    // Evaluate each match and create a replacement for it.
    toSearchInside = regex.Replace(toSearchInside, m 
        => CreateReplacement(m.Groups[1].Value));
}

where the m is a Match object for the current match.

Answer 4

Improvement to @ChrisWue and @Heslacher's solution

I really like @ChrisWue and @Heslacher's solution but it's inefficient in that a ton of temporary Strings get created with all the calls to Substring, and the same string gets rebuilt over and over and over again (as many StringBuilder objects as there are matches).

It ought to be possible with just one StringBuilder, like so:

var builder = new StringBuilder();
int prevIndex = 0
foreach (var match in matches)
{
    builder.Append(toSearchInside, prevIndex, match.Index);
    builder.Append(replacement);
    prevIndex = match.Length;
}
builder.Append(toSearchInside, prevIndex, toSearchInside.Length - prevIndex);

Benefits: only one StringBuilder, no temporary strings.

Improvement to @t3chb0t's solution

I also was glad that @t3chb0t pointed to the MatchEvaluator solution as I thought it has a lot of promise. I was hoping to replace one of the deficiencies I've seen so far with all proposed solutions to date: the haystack string is scanned multiple times, once for each target word. Regular expressions have the | operator to scan for multiple things at once! After a bit of thought I came up with this:

var MemoizedCreateReplacement = Memoize<string, string>(CreateReplacement);

// note, no start paren, and ending with '|' instead of close paren
string pattern = @"[:@?]{0}|"; 

StringBuilder sb;
sb.Append"(";
foreach(var toMatch in searchStrings)
{
    sb.AppendFormat(pattern,toMatch);
}
sb.chars[sb.Length-1]=")"; // replace last | with )
var regex = new Regex(sb.ToString());
regex.Replace(toSearchInside, m => MemoizedCreateReplacement(m.Groups[1].Value));

Benefits: Only one pass over the toSearchInside string. Only one StringBuilder; no temporary strings used in calls to it. Only one temporary string (for the Regex) and each replacement gets computed once, only if it's needed.

Memoize() code, based on what I found http://explodingcoder.com/blog/content/painless-caching-memoization-net

public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function) {
   return Memoize(function, new Dictionary<TArg, TResult>());
}

public static Func<TArg, TResult> Memoize<TArg, TResult>(Func<TArg, TResult> function, IDictionary<TArg, TResult> cache) {
   return delegate(TArg key) {TResult replacement; return cache.TryGetValue(key, out replacement) ? replacement : (cache[key] = function(key));};
}