c++的实现问题

c++的实现问题

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

  1. 如果是"[ ( [ ] [ ] ) ]"这样的例子就无法通过,我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;
}


正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

2回答
我是没有昵称 2021-03-29 21:39:00
// 你参考一下我的代码,然后debug一下你的代码,我估计是pop的时机不对
// 循环时碰到非各种括号的字符,直接跳过即可
#include <iostream>
#include <string>
#include <stack>

using namespace std;

class Solution
{
public:
static bool isValid(string s)
{
stack<char> myStack;
for (int i = 0; i < s.length(); i++)
{
char c = s[i];
if (c == '(' || c == '[' || c == '{')
myStack.push(c);
else if (c == ')' || c == ']' || c == '}')
{
if (myStack.empty())
return false;
char topChar = myStack.top();
myStack.pop();
if (c == ')' && topChar != '(')
return false;
if (c == ']' && topChar != '[')
return false;
if (c == '}' && topChar != '{')
return false;
}
}
return myStack.empty();
}
};

int main()
{
string s1 = "{ $$ ( [ ] ) } ";
string s2 = "{$( [] } )";
cout << Solution::isValid(s1) << endl;
cout << Solution::isValid(s2) << endl;
}


liuyubobobo 2020-10-06 13:03:41

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


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

[([][])]


继续加油!:)

  • 提问者 慕移动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
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师