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.