c# - 检查字符串是否有平衡括号

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.

问题在堆栈、队列和列表类别下。这是我用 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

我认为这是意图，但如果您只处理括号，实际上您只需要递减和递增计数器。如果您正在处理方括号、尖括号、花括号或任何您想使用的字符对的配对，您将需要一个堆栈，就像您所做的那样。

您也可以使用列表，将头元素拉上拉下，但实际上堆栈可能无论如何都实现为列表——至少在 ocaml 中是这样。