c++ - 在输入文本中匹配平衡和嵌套的大括号

Question

我参加了一个测验，我提供了代码，但自动测试显示八个测试用例中有一个失败了。 我自己多次测试我的代码，但都通过了。我找不到问题出在哪里。

问题是设计一个算法来检查字符串中的括号是否匹配。

1) 只考虑圆括号()和方括号[]，省略其他字符。
2) 每对括号应相互匹配。也就是说(匹配)，[匹配]。
3) 不允许交叉，如:([)]。有两对支架，但它们相互交叉。

解决问题，我的方法如下:

1. 搜索整个输入字符串中的每个字符，索引从 0 到 str.size() - 1。
2. 用两个栈记录开始标签(，和[，每一种类型一个栈，遇到其中一个，将其索引压入对应的栈。
3. 当遇到结束标记) 和] 时，我们弹出相应的堆栈。
4. 出栈前先检查两个栈顶，当前栈应该有最大索引，否则说明有和其他类型不匹配的开始标签，这样可以检查交叉。

我的代码在这里:

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    string str;
    cin >> str;

    stack<int> s1, s2;
    int result = 0;
    for (int ix = 0, len = str.size(); ix < len; ix++)
    {
        if (str[ix] == '(')
        {
            s1.push(ix);
        }
        else if (str[ix] == '[')
        {
            s2.push(ix);
        }
        else if (str[ix] == ')')
        {
            if (s1.empty() || (!s2.empty() && s1.top() < s2.top()))
            {
                result = 1;
                break;
            }
            s1.pop();
        }
        else if (str[ix] == ']')
        {
            if (s2.empty() || (!s1.empty() && s2.top() < s1.top()))
            {
                result = 1;
                break;
            }
            s2.pop();
        }
        else
        {
            // do nothing
        }
    }
    if (!s1.empty() || !s2.empty())
    {
        result = 1;
    }
    cout << result << endl;
}

按照之前的方法，这道题只需要on stack就可以解决，所以我修改了代码，这里是单栈版本。 [关键点不是争论哪个更好，而是我的代码有什么问题。]

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    string str;
    cin >> str;

    stack<char> s;
    const char *p = str.c_str();
    int result = 0;
    while (*p != '\0')
    {
        if (*p == '(' || *p == '[')
        {
            s.push(*p);
        }
        else if (*p == ')')
        {
            if (s.empty() || s.top() != '(')
            {
                result = 1;
                break;
            }
            s.pop();
        }
        else if (*p == ']')
        {
            if (s.empty() || s.top() != '[')
            {
                result = 1;
                break;
            }
            s.pop();
        }
        else
        {
            // do nothing
        }
        p++;
    }
    if (!s.empty())
    {
        result = 1;
    }
    cout << result << endl;
}

Answer 1

当使用格式化输入读取 std::string 时，仅读取第一个单词:在跳过前导空格后，读取字符串直到遇到第一个空格。因此，输入 ( ) 应该匹配，但 std::cin >> str 只会读取 (。因此，输入可能应该看起来像这样:

if (std::getline(std::cin, str)) {
    // algorithm for matching parenthesis and brackets goes here
}

使用 std::getline() 仍然假设输入是如何呈现的，即它在一行上。如果算法应该处理来自 std::cin 的整个输入，我会使用

str.assign(std::istreambuf_iterator<char>(std::cin),
           std::istreambuf_iterator<char>());

尽管我认为该算法不必要地复杂(在堆栈上存储那种括号就足够了)，但我也认为它应该有效，也就是说，我发现的唯一问题是输入的方式得到。