It is not uncommon to accidentally create strings that contain unbalanced parentheses. For example, a user might enter the following equation in your calculator application:
(((a) + (b)) + c * d
This equation contains four (
characters while
only matching them with three )
characters. You
cannot solve this equation, since the user did not supply the fourth
)
character. Likewise, if a user enters a regular
expression, you might want to do a simple check to see that
all
the (
,
{
, [
, and
<
characters match up to every other
)
, }
, ]
, and
>
character.
In addition to determining whether the characters/strings/tags match, you should also know where the unbalanced character/string/tag exists in the string.
Use the various Check
methods of the
Balance
class to determine whether and where the
character/string is unbalanced:
using System; using System.Collections; public class Balance { public Balance( ) {} private Stack bookMarks = new Stack ( ); public int Check(string source, char openChar, char closeChar) { return (Check(source.ToCharArray( ), openChar, closeChar)); } public int Check(char[] source, char openChar, char closeChar) { bookMarks.Clear( ); for (int index = 0; index < source.Length; index++) { if (source[index] == openChar) { bookMarks.Push(Index); } else if (source[index] == closeChar) { if (bookMarks.Count <= 0) { return (index); } else { bookMarks.Pop( ); } } } if (bookMarks.Count > 0) { return ((int)bookMarks.Pop( )); } else { return (-1); } } public int Check(string source, string openChars, string closeChars) { return (Check(source.ToCharArray( ), openChars.ToCharArray( ), closeChars.ToCharArray( ))); } public int Check(char[] source, char[] openChars, char[] closeChars) { bookMarks.Clear( ); for (int index = 0; index < source.Length; index++) { if (source[index] == openChars[0]) { if (CompareArrays(source, openChars, index)) { bookMarks.Push(index); } } if (source[index] == closeChars[0]) { if (CompareArrays(source, closeChars, index)) { if (bookMarks.Count <= 0) { return (index); } else { bookMarks.Pop( ); } } } } if (bookMarks.Count > 0) { return ((int)bookMarks.Pop( )); } else { return (-1); } } public bool CompareArrays(char[] source, char[] targetChars, int startPos) { bool isEqual = true; for (int index = 0; index < targetChars.Length; index++) { if (targetChars[index] != source[startPos + index]) { isEqual = false; break; } } return (isEqual); } }
The Check
method determines whether there is one
closing element for every opening element. There are four overloaded
Check
methods, and each takes three parameters of
varying types. These methods return an integer indicating where the
offending character is located, or a negative number if each
openChar
has a matching
closeChar
.
These methods return an integer indicating where the offending string
is located, or a negative number if each
openChars
has a matching
closeChars
.
The code to exercise the Balance
class is shown
here:
class CTest { static void Main( ) { Balance balanceUtil = new Balance( ); // A string with an unbalanced } char. This unbalanced char is the final // } char in the string. string unbalanced = @"{namespace Unbalanced { public class Tipsy { public Tipsy( ) { }}}}} "; // Use the various overloaded Check methods // to check for unbalanced } chars Console.WriteLine("Balance {}: " + balanceUtil.Check(unbalanced, '{', '}')); Console.WriteLine("Balance {}: " + balanceUtil.Check(unbalanced.ToCharArray( ), '{', '}')); Console.WriteLine("Balance {}: " + balanceUtil.Check(unbalanced.ToCharArray( ), new char[1] {'{'}, new char[1] {'}'})); Console.WriteLine("Balance {}: " + balanceUtil.Check(unbalanced.ToCharArray( ), new char[1] {'{'}, new char[1] {'}'})); } }
This code produces the following output:
Balance {}: 136 Balance {}: 136 Balance {}: 136 Balance {}: 136 Balance {}: -1
where a -1
means that the items are balanced and a
number greater than -1
indicates the character
position that contains the unbalanced character.
Determining whether
characters have a matching character is actually quite easy when a
Stack
object is used. A stack works on a first-in,
last-out (FILO) principle. The first item added to a stack is always
the last one to be removed; conversely, the last item added to a
stack is always the first removed.
To see how the stack is used in matching characters, let’s see how we’d use it to handle the following equation:
((a + (b)) + c) * d
The algorithm works like this: we iterate through all characters in the equation, then any time we come upon a left or right parenthesis, we push or pop an item from the stack. If we see a left parenthesis, we know to push it onto the stack. If we see a right parenthesis, we know to pop a left parenthesis from the stack. In fact, the left parenthesis that was popped off of the stack is the matching left parenthesis to the current right parenthesis. If all parentheses are balanced, the stack will be empty after iterating through all characters in the equation. If the stack is not empty, the top left parenthesis on the stack is the one that does not have a matching right parenthesis. If there are two or more items in the stack, there is more than one unbalanced parenthesis in the equation.
For the previous equation, starting at the lefthand side, we would
push one left parenthesis on the stack and then immediately push a
second one. We consume the a
and
+
characters and then come upon a third left
parenthesis; our stack now contains three left parentheses. We
consume the b
character and come upon two right
parentheses in a row. For each right parenthesis, we will pop one
matching left parenthesis off of the stack. Our stack now contains
only one left parenthesis. We consume the +
and
c
characters and come upon the last right
parenthesis in the equation. We pop the final left parenthesis off of
the stack and then check the rest of the equation for any other
parenthesis. Since the stack is empty and we are at the end of the
equation, we know that each left parenthesis has a matching right
parenthesis.
For our Check
methods in this recipe, the location
in the string where each left parenthesis is located is pushed onto
the stack. This allows us to immediately locate the offending
parenthesis.