Introduction
Checks a string
for balanced parenthesis, i.e., whether all opening or left hand parenthesis have a closing or right hand parenthesis and are those logically placed in a string
. Can be used to validate a numerical formula or a LINQ expression, or to check if an xml/json is well-formed, etc.
Background
Using Stack
to solve this problem.
Using the Code
Use Stack
, while iterating through each character of the input string
, to Push
any opening brackets to the stack
and to Pop
the closing bracket if it matches the closing bracket of the latest opening bracket in the stack
. At the end of the iteration, if the stack
is empty, then all the brackets were balanced.
public static bool IsBalanced(string input)
{
Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
{ '(', ')' },
{ '{', '}' },
{ '[', ']' },
{ '<', '>' }
};
Stack<char> brackets = new Stack<char>();
try
{
foreach (char c in input)
{
if (bracketPairs.Keys.Contains(c))
{
brackets.Push(c);
}
else
if (bracketPairs.Values.Contains(c))
{
if (c == bracketPairs[brackets.First()])
{
brackets.Pop();
}
else
return false;
}
else
continue;
}
}
catch
{
return false;
}
return brackets.Count() == 0 ? true : false;
}
Examples
- Input: "
[288 votes so far. Categories: {"Everything Else" (47 votes), C# (61 votes), C++ (39 votes), Database (44 votes), Mobile (45 votes), Web Dev (52 votes)}]
"
Output: true
- Input: "
[{}()<sometext>[[{{}}]]]
"
Output: true
- Input: "
<Root><First>Test</First<</Root>
"
Output: false