Friday 10 September 2010

Code Snippit - Determining whether brackets are balanced


We usually have coding challenges at work quite often. This one was quite useful. The aims were to do something that regular expressions struggle doing; that is, determine whether brackets are balanced.

Example of a legal expression: “([as](<{}>))”.
Example of an illegal expression: “({<)>}”.

Here's what I came up with...



private bool IsValid(string str)
{
if (!string.IsNullOrEmpty(str))
{
List<char> LeftParenthesis = new List<char>() { '(', '{', '[', '<' };
List<char> RightParenthesis = new List<char>() { ')', '}', ']', '>' };
List<char> items = new List<char>(str.Length);

// Loop through each character
for (int i = 0; i < str.Length; i++)
{
char c = str[i];

if (LeftParenthesis.Contains(c))
{
items.Add(c); // Add each opening bracket
}
else if (RightParenthesis.Contains(c))
{
int rpIndex = RightParenthesis.IndexOf(c);

// Invalid if there are no open brackets and we find a closing one
int lastPairIndex = items.LastIndexOf(LeftParenthesis[rpIndex]);

if (lastPairIndex >= 0)
{
if (items[items.Count - 1] != items[lastPairIndex]) // Last item must be matching bracket
return false;
else
items.RemoveAt(lastPairIndex); // Remove last pair
}
else
return false;
}
}

// Look for any other brackets left over
if (items.Count > 0)
return false;
}

return true;
}

No comments: