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

概述我参加了一个测验,我给出了代码但是自动测试表明八个测试用例中的一个失败了. 我自己多次测试我的代码,但都通过了.我找不到问题出在哪里. 问题是设计一种算法来检查字符串中的括号是否匹配. 1)只考虑圆括号()和方括号[],省略ohter chars. 2)每对括号应相互匹配.这意味着(匹配)和[匹配]. 3)不允许交叉,例如：([]].有两对括号,但它们相互交叉. 为了解决这个问题,我的方法描述如下 我参加了一个测验,我给出了代码但是自动测试表明八个测试用例中的一个失败了.
我自己多次测试我的代码,但都通过了.我找不到问题出在哪里.

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

1)只考虑圆括号()和方括号[],省略ohter chars.
2)每对括号应相互匹配.这意味着(匹配)和[匹配].
3)不允许交叉,例如：([]].有两对括号,但它们相互交叉.

为了解决这个问题,我的方法描述如下：

>搜索整个输入字符串中的每个字符,索引从0到str.size() – 1.
>使用两个堆栈来记录开始标记(和[,每个类型在一个堆栈中.当遇到其中一个时,在相应的堆栈中推送它的索引.
>当关闭结束标记时)和],我们d出相应的堆栈.
>在d出之前,检查两个堆栈的顶部,当前堆栈应该具有​​最大索引,否则这意味着与另一个类型具有不匹配的开始标记,因此可以通过这种方式检查交叉.

我的代码在这里：

#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;}

如前所述,这个问题可以通过堆栈来解决,所以我修改了我的代码,这里是单栈版本. [关键点不是要认为白色更好,但是我的代码有什么错误.]

#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 != '
if (std::getline(std::cin,str)) {    // algorithm for matching parenthesis and brackets goes here}
')    {        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;}

解决方法 当使用格式化输入来读取std :: string时,只读取第一个单词：跳过前导whitespate后,将读取一个字符串,直到遇到第一个空格.因此,input()应匹配,但std :: cin>> str只会读取(.因此,输入应该看起来像这样：

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

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

虽然我认为算法是不必要的复杂(在堆栈存储括号的类型就足够了),我也认为它应该工作,即我发现的唯一问题是获得输入的方式.

总结

以上是内存溢出为你收集整理的c – 在输入文本中匹配平衡和嵌套大括号全部内容，希望文章能够帮你解决c – 在输入文本中匹配平衡和嵌套大括号所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。