Removing curly braces and contents inside it

Question

Lets say I have a string like this:

 string s = "A }{ B { C } }{"
//Indexes:   0123456789ABCDE

Just consider the indexes beyond #9 are 10,11,12,13, and 14 respectively. My code turns s to "A ", because whatever is inside matching curly braces gets removed.

How the matching works:
When you find a closing brace (}), the last opening brace ({) which does not yet have an associated closing brace should be associated with the closing brace we just found. For example, in the above string I have given, the closing brace at index 2 cannot have an opening brace. So it is "Incomplete". the brace at index 3 is paired with brace at index 13. And brace at index 7 is paired with brace at index 11. Brace at index 14 does not have a closing brace so it is also "incomplete". I hope you understand what I am trying to do :)

A simple regex such as {[^}]*} can match the curly braces but it does not handle nesting very well. So I wrote a class to parse this. But I found that compared to regex, my method is very slow. Regex takes 0ms but my method takes 3ms. I would appreciate if anyone could tell me how I can optimise it further.

internal class BracketPair
{
    private readonly string _originalString;
    private int _endIndex;

    public BracketPair(string originalString, int startIndex)
    {
        _originalString = originalString;
        StartIndex = startIndex;
        Children = new List<BracketPair>();
        NestedLevel = 0;
    }

    public int StartIndex { get; }

    public int EndIndex {
        get { return _endIndex; }
        set {
            _endIndex = value;
            IsComplete = true;
        }
    }

    //If there are matching pairs of { and } for this
    public bool IsComplete { get; private set; }
    public List<BracketPair> Children { get; }
    public int NestedLevel { get; set; }

    public override string ToString()
    {
        if (!IsComplete)
            throw new InvalidOperationException("BracketPair is incomplete");
        return _originalString.Substring(StartIndex, EndIndex - StartIndex + 1);
    }

    public static void HideInternalNote(string originalString)
    {
        //This list will have all bracket pairs in the string
        var bracketPairs = new List<BracketPair>();
        //Iterate through every char
        for (var i = 0; i < originalString.Length; i++) {
            char currentChar = originalString[i];
            if (currentChar == '{') {
                var bracketPair = new BracketPair(originalString, i);

                if (bracketPairs.Any(b => !b.IsComplete)) {
                    //Add to last Incomplete bracket pair's children list.
                    BracketPair parent = bracketPairs.Last(b => !b.IsComplete);
                    parent.Children.Add(bracketPair);

                    bracketPair.NestedLevel = parent.NestedLevel + 1;
                }
                //Add a non-complete bracket pair
                bracketPairs.Add(bracketPair);
            }
            // if it's '}' and there exists a non-complete bracket pair before, complete the last non complete bracket pair.
            else if (currentChar == '}' && bracketPairs.Any(b => !b.IsComplete)) {
                BracketPair lastNonCompleteBracketPair = bracketPairs.Last(b => !b.IsComplete);
                lastNonCompleteBracketPair.EndIndex = i; //This will Complete it auto.
            }
        }

        for (int i = bracketPairs.Count - 1; i >= 0; i--) {
            BracketPair bracketPair = bracketPairs[i];

            if (!bracketPair.IsComplete) {
                //If there was an incomplete bracketpair with children, move the children one nest level outwards.
                if (bracketPair.Children.Any())
                    DecrementChildrenNestedLevelRecursively(bracketPair);
                //Remove the useless incomplete bracketpair because it is incomplete
                bracketPairs.Remove(bracketPair);
            }
        }

        foreach (BracketPair bracketPair in bracketPairs.Where(bracketPair => bracketPair.NestedLevel == 0)) {
            //Console.WriteLine(bracketPair.ToString());
            originalString = originalString.Replace(bracketPair.ToString(), string.Empty);
        }

        Console.WriteLine(originalString);
    }

    private static void DecrementChildrenNestedLevelRecursively(BracketPair bracketPair)
    {
        foreach (BracketPair child in bracketPair.Children) {
            child.NestedLevel--;
            DecrementChildrenNestedLevelRecursively(child);
        }
    }
}

All braces which are not a child of another brace has nested level of 0. As they go down, nested level will increment.

Answer 1

All right; take two. My previous proposed better solution was wrong. This one I believe is correct.

The original code is far too complicated for the task at hand. The given regular expression solution is good, but generates a large number of temporary strings in the case where there are many braces to remove. I propose the following solution:

using System;
using System.Linq;  
using System.Collections.Generic;
class Program
{   
  static string RemoveMatchingBraces(string s)
  {        
    var stack = new Stack<char>();
    int count = 0;
    foreach(char ch in s)
    {
      switch(ch)
      {
        case '{':
          count += 1;
          stack.Push(ch);
          break;
        case '}':
          if (count == 0)
            stack.Push(ch);
          else
          {
            char popped;
            do 
            { 
              popped = stack.Pop(); 
            } while (popped != '{');
            count -= 1;
          }
          break;
        default:
          stack.Push(ch);
          break;
      } 
    }
    return string.Join<char>("", stack.Reverse());
  }
  public static void Main()
  {
    Console.WriteLine(RemoveMatchingBraces("}}AB{CDE{FG}H{IJ}K}LMN{OP}QRS{{"));
  }
}

We use a push-down stack to keep track of the characters we've seen so far. When we find a matching brace we go back and erase all the characters up to that matching brace. What is left on the stack when we're done is everything that was not matched.

The solution is easily seen to be O(n) in both time and space; plainly the total number of pops and the total number of pushes must both be less than or equal to the number of characters in the string.

Answer 2

I would definitely use a regex for this. It might not be the most performant solution but I think it's the simplest. You can handle the nesting problem by making the * quantifier lazy by appending a ? to it in your pattern:

public static string HideInternalNote(string input)
{
    if (input == null)
    {
        throw new ArgumentNullException("input");
    }
    if (input == string.Empty)
    {
        return input;
    }
    var inputWithBracePairsRemoved = RemovePairedBraces(input);
    var result = RemoveAllBraces(inputWithBracePairsRemoved);
    return result;
}

private static string RemoveAllBraces(string input)
{
    return input
        .Replace("{", string.Empty)
        .Replace("}", string.Empty);
}

private static string RemovePairedBraces(string input)
{
    var expression = new Regex("{[^{]*?}");
    // OR
    // var expression = new Regex("{[^{}]*}");

    var previous = input;
    string current;
    while (true)
    {
        current = expression.Replace(previous, string.Empty);
        if (current == previous)
        {
            break;
        }
        previous = current;
    }
    return current;
}

I don't know whether it will match all of your inputs but it works for the example you've given. The while loop is a bit annoying - if you don't have any nesting it will only run once but if you have a heavily nested string you'll end up running the regex quite a few times.