c++的实现问题

老师我想用c++实现这个问题，但是遇到了一些问题：

如果是"[ ( [ ] [ ] ) ]"这样的例子就无法通过，我debug发现在入栈过程中只有"["成功，紧接着就退出循环，直接进行判断。但是如果我用map来对应判断，例子就顺利通过测试。

1.成功的代码

#include<stdio.h>
#include<map>
#include<iostream>
#include<stack>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    int len=s.size();
    map<char,char> m;
    m['(']=')';
    m['{']='}';
    m['[']=']';
    stack <char> a;
    int flag=1;
    for(int i=0;i<len;i++)
    {
        if(s[i]=='(' || s[i]=='{' || s[i]=='[')
            a.push(s[i]);
        else if(s[i]==')' || s[i]=='}' || s[i]==']')
        {
            if(a.size() && m[a.top()]==s[i])
                a.pop();
            else
            {
                flag=0;
                break;
            }
        }
    }
    if(flag && a.size() == 0)
        printf("yes\n");
    else
        printf("no\n");
     
     
    return 0;

2.失败的代码

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(void){
    stack<char> s;
    string str;
    cin >> str;
    //push and pop
    int flag = 1;
    for(int i = 0;i < str.length(); i++){
        //push
        if(str[i] == '('  || str[i] =='['  || str[i] =='{' ){
            s.push(str[i]);
        }else if(str[i] == ')'  || str[i] ==']'  || str[i] =='}'){//pop
            if(s.empty() || ((s.top() =='(' && str[i] != ')') || (s.top() == '[' && str[i] != ']') || (s.top() == '{' && str[i] != '}'))){
                flag = 0;
                break;
            }
            s.pop();
        }
    }
    if(flag == 1 && s.empty()){
        cout << "yes\n";
    }else {
        cout << "no\n";
    }
    return 0;
}

慕移动9049991 2020-10-06

源自：数据结构基础：动态数组，栈和队列 2-3 栈的另一个应用：括号匹配

收起

2回答

我是没有昵称 2021-03-29 21:39:00

// 你参考一下我的代码，然后debug一下你的代码，我估计是pop的时机不对<br>// 循环时碰到非各种括号的字符，直接跳过即可<br>#include <iostream><br>#include <string><br>#include <stack><br><br>using namespace std;<br><br>class Solution<br>{<br>public:<br>    static bool isValid(string s)<br>    {<br>        stack<char> myStack;<br>        for (int i = 0; i < s.length(); i++)<br>        {<br>            char c = s[i];<br>            if (c == '(' || c == '[' || c == '{')<br>                myStack.push(c);<br>            else if (c == ')' || c == ']' || c == '}')<br>            {<br>                if (myStack.empty())<br>                    return false;<br>                char topChar = myStack.top();<br>                myStack.pop();<br>                if (c == ')' && topChar != '(')<br>                    return false;<br>                if (c == ']' && topChar != '[')<br>                    return false;<br>                if (c == '}' && topChar != '{')<br>                    return false;<br>            }<br>        }<br>        return myStack.empty();<br>    }<br>};<br><br>int main()<br>{<br>    string s1 = "{ $$ ( [ ] ) } ";<br>    string s2 = "{$( [] } )";<br>    cout << Solution::isValid(s1) << endl;<br>    cout << Solution::isValid(s2) << endl;<br>}<br>

收起回答

liuyubobobo 2020-10-06 13:03:41

你再问题描述中的那个括号字符串中有大量的空格，所以导致了返回 No

我测试你的程序使用这个输入是没有问题的：

1	`[([][])]`

继续加油！：）

收起回答

提问者慕移动9049991 #1

谢谢老师！不过为什么空格就会失败呢，比较判定中不是只有满足那三个括号才能进行比较，否则接着循环，为什么会退出呢？

2020-10-06 13:08:27
liuyubobobo 回复提问者慕移动9049991 #2

因为空格也是一个字符，str[i] 是空格，会引发你的逻辑置 flag 为 0，实际单步跟踪模拟调试一下试试看？继续加油！：）

2020-10-06 13:11:28
提问者慕移动9049991 回复 liuyubobobo #3

谢谢老师！不过过程是遇到第一个空格之后退出循环，此时的flag仍然为1不过栈不为空（存在"[" ），才得到no，从逻辑上没有问题的话我可能只能想是自己运行环境的问题了？

2020-10-06 13:19:05