检查字符串具有平衡括号

Question

我正在阅读算法设计手册第二版,这是一个练习题.引用问题

编译器和文本编辑器的一个常见问题是确定字符串中的括号是否是平衡的并且是否正确嵌套.例如,字符串((())())()包含正确嵌套的括号对,字符串)()(和())不包含.如果字符串包含正确嵌套和平衡的括号,则给出一个返回true的算法,否则返回false.对于完全信用,如果字符串未正确嵌套和平衡,则标识第一个违规括号的位置.

问题在堆栈,队列和列表类别下.这是我在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;
}

这很好用.但我不确定这是解决这个问题的正确方法.欢迎任何更好的想法.

Answer 1

我认为这是意图,但如果你只是处理括号,你真的需要减少和增加一个计数器.如果你正在处理方括号,尖括号,花括号或你想要使用的任何字符配对的配对,你需要像你所做的那样堆栈.

你也可以使用一个列表,关闭和打开head元素,但实际上堆栈可能实现为列表 - 至少它是在ocaml中.

Answer 2

    static public bool CheckForBalancedBracketing(string IncomingString)
    {
    /*******************************************************************
     * The easiest way to check for balanced bracketing is to start    *
     * counting left to right adding one for each opening bracket, '(' *
     * and subtracting 1 for every closing bracket, ')'.  At the end   *
     * the sum total should be zero and at no time should the count    *
     * fall below zero.                                                *
     *                                                                 *
     * Implementation:  The bracket counting variable is an unsigned   *
     * integer and we trap an overflow exception.  This happens if the *
     * unsigned variable ever goes negative.  This allows us to abort  *
     * at the very first imbalance rather than wasting time checking   *
     * the rest of the characters in the string.                       *
     *                                                                 *
     * At the end all we have to do is check to see if the count       *
     * is equal to zero for a "balanced" result.                       *
     *                                                                 *
     *******************************************************************/
        const char LeftParenthesis = '(';
        const char RightParenthesis = ')';
        uint BracketCount = 0;

        try
        {
            checked  // Turns on overflow checking.
            {
                for (int Index = 0; Index < IncomingString.Length; Index++)
                {
                    switch (IncomingString[Index])
                    {
                        case LeftParenthesis:
                            BracketCount++;
                            continue;
                        case RightParenthesis:
                            BracketCount--;
                            continue;
                        default:
                            continue;
                    }  // end of switch()

                }
            }
        }

        catch (OverflowException)
        {
            return false;
        }

        if (BracketCount == 0)
        {
            return true;
        }

        return false;

    }  // end of CheckForBalancedBracketing()

Answer 3

这将适用于(),{}和 的组合[]。

还可以检测以下错误：([)],)[]()和()(, ...

bool isWellFormatted(string line)
{           
        Stack<char> lastOpen = new Stack<char>();
        foreach (var c in line)
        {               
            switch (c)
            {
                case ')':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '(') return false;
                    break;
                case ']':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '[' ) return false;
                    break;
                case '}':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '{') return false;
                    break;
                case '(': lastOpen.Push(c); break;
                case '[': lastOpen.Push(c); break;
                case '{': lastOpen.Push(c); break;
            }                                                                       
        }
        if (lastOpen.Count == 0) return true;
        else return false;
    }