7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ use regex. handle nesting through recursion or iteration. \$\endgroup\$ – rbp Jan 15 '16 at 21:14
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot. This is an excellent solution. I can better understand this. And this performs better for long inputs (When I replaced the stack with a list) \$\endgroup\$ – Winger Sendon Jan 15 '16 at 23:19
  • 1
    \$\begingroup\$ @EmpereurAiman: A list would indeed work just as well, and would likely be more memory efficient. I have been doing a lot of programming in functional languages lately and now everything problem looks like something to solve with a stack! \$\endgroup\$ – Eric Lippert Jan 16 '16 at 16:44
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot. This does exactly what my parser method does, but with magnitudes less time :) Can you explain the regex a bit? I am new to regex and am having a hard time understanding what the lazy qualifier is doing there. For example, in the case of {Ja{mes}}, it matches {mes}. When I take the lazy qualifier out, it matches {mes}}. I am confused. \$\endgroup\$ – Winger Sendon Jan 14 '16 at 22:04
  • 1
    \$\begingroup\$ @EmpereurAiman Basically * is greedy so it will try to match as many times as possible; adding the ? makes it lazy and will make it match as few times as possible. You could also make the regex: {[^{}]*} to not match closing braces... I guess it depends on which way your mind works as to which one is easier to understand... Good tutorial: regular-expressions.info/repeat.html \$\endgroup\$ – RobH Jan 14 '16 at 22:10
  • \$\begingroup\$ Thanks. I find the latter expression easier to understand. Also thanks for the tutorial :) \$\endgroup\$ – Winger Sendon Jan 14 '16 at 22:29
  • \$\begingroup\$ @RobH - heh, I got dragged in to a disccsion about this question, and suggested that I would solve it with a regex in a loop. It was only after I put the code up in ideone that I saw that your answer does essentially that too. The loop is a bit different though: ideone.com/7GRLw1 - jsut FYI \$\endgroup\$ – rolfl Jan 15 '16 at 21:42
  • \$\begingroup\$ @rofl - that's a better way of doing the loop! I was sure there was a way of doing it without a while (true) with a break but I was being a bit slow! Thanks for showing me :) \$\endgroup\$ – RobH Jan 15 '16 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.