检查字符串有平衡的括号 [英] Checking string has balanced parentheses

问题描述

我读的算法设计手册第二版的，这是一个锻炼的问题。引用这个问题

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

有关编译器的一个共同的问题和   文本编辑器是确定是否   在字符串中的括号   平衡和正确嵌套。对于   例如，字符串（（（））（））（）   包含正确嵌套双   括号，其中所述字符串）（）（   和（））没有。给出了一个算法，   如果一个字符串包含返回true   正确的嵌套和平衡   括号，假否则。   对于完全学分制，找准位置   第一个问题的括号如果   字符串是不正确的嵌套和   平衡的。

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＃中这样写道。

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.

推荐答案

我觉得这是有意的，但真的是你只需要递减和递增计数器，如果你只处理括号。如果你正在处理的方括号，尖括号，大括号或其他字符配对你想使用的配对，你需要一个堆栈像你这样做了。

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.

您也可以使用列表，拉头元素和关闭，但确实是一个堆栈可能实现为列表反正--at至少这是OCaml中。

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.

这篇关于检查字符串有平衡的括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！