Check for balanced parentheses

Question

I was given an assignment to check for balanced parentheses from an arbitrary string where parentheses are defined as (, [ or { and their respective "closing" parentheses. The other requirement for the assignment was that I had to use either Stack<T> , Queue<T> or List<T>.

Here is my implementation:

private static void CheckParentheses()
{
    Console.Write("Please enter the string you wist to check formity of: ");
    var input = Console.ReadLine();
    var stack = new Stack<char>();

    char[] allowedChars = { '(', '[', '{', ')', ']', '}' };

    foreach (char chr in input)
        if (allowedChars.Any(x => x == chr))
            stack.Push(chr);

    var reverseStack = stack.Reverse();
    var sequencedBalanced = reverseStack.SequenceEqual(stack, BalancedParanthesisComparer.Instance);
    Console.WriteLine("The input string was {0}well formed", sequencedBalanced ? string.Empty : "NOT ");
}

public sealed class BalancedParanthesisComparer : EqualityComparer<char>
{
    private static readonly BalancedParanthesisComparer _instance = new BalancedParanthesisComparer();

    private BalancedParanthesisComparer() { }

    public static BalancedParanthesisComparer Instance { get { return _instance; } }

    public override bool Equals(char x, char y)
    {
        if ((x == '(' && y == ')') || (y == '(' && x == ')'))
            return true;
        if ((x == '[' && y == ']') || (y == '[' && x == ']'))
            return true;
        if (x == '{' && y == '}' || (y == '{' && x == '}'))
            return true;

        return false;
    }
}

I would like general feedback and would also like to know: regarding the use of an EqualityComparer to do something that isn't really equality-checking, is it very bad practice or is it fine?

Answer 1

Good in general. However

1. You need to separate some concerns. CheckParentheses takes its input from the Console and does the actual algorithm, but what if you want to read the input from a file?The you have to touch this function again. You should rather separate them and let CheckParentheses takes a string as parameter and returns bool

   private bool CheckParentheses(string input){ // returns true if the expression is valid
   
   }
   

2. You don't need to do a sequential search on allowedChars, you could rather use a HashSet<char>, and use Linq instead of for-loops because Linq is great

   var allowedChars = new HashSet<char>(new []{'(', '[', '{', ')', ']', '}' });
   var stack = new Stack<char>(input.Where(c => allowedChars.Contains(c)));
   

3. Always use braces for loops and if statements, so you don't forget to add the required braces if the body of the statement is more than one statement, for example

   if(condition) 
      doSomething
   

   Oooh, I want to do one more thing if this condition holds

   if(condition)
      doSomething
      oneMoreThing
   

   Because there were no braces initially, you or the maintainer will forget to add them because we were in hurry to add the oneMoreThing

Answer 2

Aside from stylistic concerns (as a Java/Clojure guy, I'll let you C#'ers decide on that stuff), I don't see how this a correct algorithm, unless additional constraints are given in the problem statement. Consider this input:

([] ())

Now, clearly that is balanced. And if you reverse it, you get:

))( ][(

But if you compare this reversed input with the original input, you don't find that each open bracket matches up with its closing bracket in the reversed string: the first character and the last are fine, but the inner pairs don't balance at all!

So, unless you are given the further guarantee that the input consists of N opening brackets followed by N closing brackets (ie, no opens after the first close), you can't just compare the reversed string.

Answer 3

It would better to push on the stack the starting parenthesis and when hitting an ending parenthesis to pop off the stack and see if it's the matching pair. If it's not the matching pair you can exit out early and not have to check the rest of the chars.

This would also prevent you from having to reverse the stack and deal with the EqualityComparer at all.

Also allowedChars.Contains(chr) would be better than allowedChars.Any(x => x == chr). See Performance Benchmarking of Contains, Exists and Any on Stack Overflow.

Put example in spoiler. Wasn't sure you would want to see code given it's an assignment

private static bool CheckWellFormed(string input)
{
    var stack = new Stack<char>();
    // dictionary of matching starting and ending pairs
    var allowedChars = new Dictionary<char, char>() { { '(', ')' }, { '[', ']' }, { '{', '}' } };

    var wellFormated = true;
    foreach (var chr in input)
    {
        if (allowedChars.ContainsKey(chr))
        {
            // if starting char then push on stack
            stack.Push(chr);
        }
        // ContainsValue is linear but with a small number is faster than creating another object
        else if (allowedChars.ContainsValue(chr)) 
        {
            // make sure something to pop if not then know it's not well formated
            wellFormated = stack.Any();
            if (wellFormated)
            {
                // hit ending char grab previous starting char
                var startingChar = stack.Pop();
                // check it is in the dictionary
                wellFormated = allowedChars.Contains(new KeyValuePair<char, char>(startingChar, chr));
            }
            // if not wellformated exit loop no need to continue
            if (!wellFormated)
            {
                break;
            }
        }
    }
    return wellFormated;
}

Answer 4

The easiest way I can see is to create 2 arrays of parentheses: 1 for the open ones and 1 for the close ones. We will use these arrays to check whether current char is a parenthesis and obtain its index in the arrays, if so.
We will use the Stack<int> to store indices of currently open parentheses:

public static class BalancedParentheses
{
    // Arrays should contain paired parentheses in the same order:
    private static readonly char[] OpenParentheses = { '(', '[', '{' };
    private static readonly char[] CloseParentheses = { ')', ']', '}' };

    public static bool Check(string input)
    {
        // Indices of the currently open parentheses:
        Stack<int> parentheses = new Stack<int>();

        foreach (char chr in input)
        {
            int index;

            // Check if the 'chr' is an open parenthesis, and get its index:
            if ((index = Array.IndexOf(OpenParentheses, chr)) != -1)
            {
                parentheses.Push(index);  // Add index to stach
            }
            // Check if the 'chr' is a close parenthesis, and get its index:
            else if ((index = Array.IndexOf(CloseParentheses, chr)) != -1)
            {
                // Return 'false' if the stack is empty or if the currently
                // open parenthesis is not paired with the 'chr':
                if (parentheses.Count == 0 || parentheses.Pop() != index)
                    return false;
            }
        }
        // Return 'true' if there is no open parentheses, and 'false' - otherwise:
        return parentheses.Count == 0;
    }
}

Usage:

Console.Write("Please enter the string you wish to check formity of: ");
string input = Console.ReadLine();
Console.WriteLine("The input string was {0}well formed",
    BalancedParentheses.Check(input) ? string.Empty : "NOT ");

Tests:

Console.WriteLine(BalancedParentheses.Check("12 { 123 (1)asd}asd"));    // true
Console.WriteLine(BalancedParentheses.Check("]12 { 123 (1)asd}asd"));   // false
Console.WriteLine(BalancedParentheses.Check("12 { 123 (1)asd[]}asd"));  // true
Console.WriteLine(BalancedParentheses.Check("12 { 123 (1)as}d}asd"));   // false

Answer 5

Perhaps CheckParentheses() would be better named CheckMatchingDelimiters(), since it works with more than just parentheses.

.NET's Stack happens to have a .Reverse() extension method as a consequence of it being Enumerable. However, stacks traditionally don't support reversal: they are designed to be used according to a last-in, first-out discipline. I would therefore consider it cheating to use .Reverse() in an exercise that is designed to demonstrate your understanding of stacks.

Here is an example of a stack-based delimiter matcher.

Answer 6

You may 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 for the latest opening bracket in the stack. At the end of the iteration, if the stack is empty, then all the brackets were balanced.

Here's my code version:

private static bool IsBalanced(string input)
    {
        Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
            { '(', ')' },
            { '{', '}' },
            { '[', ']' },
            { '<', '>' }
        };

        Stack<char> brackets = new Stack<char>();

        try
        {
            // Iterate through each character in the input string
            foreach (char c in input)
            {
                // check if the character is one of the 'opening' brackets
                if (bracketPairs.Keys.Contains(c))
                {
                    // if yes, push to stack
                    brackets.Push(c);
                }
                else
                // check if the character is one of the 'closing' brackets
                    if (bracketPairs.Values.Contains(c))
                {
                    // check if the closing bracket matches the 'latest' 'opening' bracket
                    if (c == bracketPairs[brackets.First()])
                    {
                        brackets.Pop();
                    }
                    else
                        // if not, its an unbalanced string
                        return false;
                }
                else
                    // continue looking
                    continue;
            }
        }
        catch
        {
            // an exception will be caught in case a closing bracket is found, before any opening bracket.
            // that implies, the string is not balanced. Return false
            return false;
        }

        // Ensure all brackets are closed
        return brackets.Count() == 0 ? true : false;
    }

Answer 7

1. You should separate input and the actual check into two separate methods. Your algorithm is not actually dependent on how you get the string so it should be extracted into it's own method which gets the string as parameter and returns bool as a result.

2. allowedChars is not a very good name because it implies it's the allowed set of characters the input may contain while it actually denotes the parenthesis symbols you are interested in. So maybe parenthesis would have been a better name.

3. There is no need to use a static instance for the BalancedParanthesisComparer. Static singletons can have their uses but in general they should be avoided. They cause implicit dependencies and make unit testing the code in general quite painful.