Checking string has balanced parentheses

Question

I am reading the Algorithm Design Manual Second Edition and this is from an exercise question. Quoting the question

A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.

Question is under stacks,queues and lists category. Here is what I wrote in C#.

const char LeftParenthesis = '(';
const char RightParenthesis = ')';
bool AreParenthesesBalanced(string str, out int errorAt)
{
    var items = new Stack<int>(str.Length);
    errorAt = -1;
    for (int i = 0; i < str.Length; i++)
    {
        char c = str[i];
        if (c == LeftParenthesis)
            items.Push(i);
        else if (c == RightParenthesis)
        {
            if (items.Count == 0)
            {
                errorAt = i + 1;
                return false;
            }
            items.Pop();
        }
    }
    if (items.Count > 0)
    {
        errorAt = items.Peek() + 1;
        return false;
    }
    return true;
}

This works well. But I am not sure that this is the right method to approach this problem. Any better ideas are welcome.

Answer 1

Yes, stacks are the preferred method for parsing this sort of data.

Answer 2

I think this is the intention, but really you just need to decrement and increment a counter if you are only dealing with parenthesis. If you are dealing with the pairings of square brackets, angle brackets, curly braces or whatever character pairing you'd like to use, you'll need a stack like you have done.

You can also use a list, pulling the head element off and on, but really a stack is probably implemented as a list anyway --at least it is in ocaml.

Answer 3

As TheVillageIdiot said, it's fine. You could also implement it recursively, which might be more elegant, or might not. Finally, you might want to require that matching parentheses contain something valid between them, so as to allow "(a)" but not "()".

Answer 4

Why have a return value and an out parameter that give the same information?

You could return an int: -1 = balanced, otherwise the index of the error.