题意描述:
‘{ [ (’对于这几种括号得字符串,找出配对的括号,求其连续的最长的配对的括号字符串,(),(()),()()等形式的就是配对的括号。
原始思路:
这个题就是对栈的运用,咱们可以定义一个字符类型栈,根据栈先进后出的特性, 我们从字符串的开始一个一个的装字符,将栈顶元素与将将要装入的元素进行判断,若配对,则出栈,连续的序列长度num加上2.在不配对的情况下,如果将进栈的是右括号,那么就是断掉了,如{),这个时候就把这次断掉的num和上一次的num比较,取大值。然后num归零。而当将进栈元素是左括号时,是有可能连续的如(()),这个时候就直接入栈,但我觉得,当连续的(((进栈时,连续序列就断掉了,最终没有想出答案。
改进思路:
在原始思路的条件下,我想通过了,不管多少({【左括号进栈,都是有可能连续的,入((((((())))))),所以只管入栈就是,然后接着上面思路,循环完字符串后,再比较一次序列长度,取最大值。
#include<iostream>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
int main() {
stack<char> st;
string s;
cin >> s;
int maxx=0,num=0;
st.push(s[0]);
for (int i = 1; i < s.length(); i++) {
if (st.top()-s[i]==-1||st.top()-s[i]==-2){
st.pop();
num+=2;
}else if(s[i]==')'||s[i]=='}'||s[i]==']'){
maxx=max(maxx,num);
st.push(s[i]);
num=0;
}else{
st.push(s[i]);
}
}
maxx=max(maxx,num);
cout << maxx;
return 0;
}
本以为对了,但还是出问题。for循环下的第一个if处有段错误(试验多次找出的)。
错因:
在不断入栈出栈后,在栈空的情况下,取栈顶元素去参与运算,发生段错误。栈为空时,使用top()函数会返回-1导致出错。
改进代码:
if (st.size()!=0&&st.top()-s[i]==-1||st.top()-s[i]==-2)
结果还是出错,依旧段错误。几经检查,发现在if判断中,因为有一个&&和一个||,if判断时,从左向右判断,结果把!=0和==-1这两个式子归为一部分,==-2归为另一部分,导致错误。必须给后面||连接的加括号才行。最终解决了这个题目。
最终代码:
#include<iostream>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
int maxx=0,num=0;string s;
stack<char> st;
int main() {
cin >> s;
st.push(s[0]);
for (int i = 1; i < s.length(); i++) {
if (st.size()!=0&&(st.top()-s[i]==-1||st.top()-s[i]==-2)){
st.pop();
num+=2;
}else if(s[i]==')'||s[i]=='}'||s[i]==']'){
maxx=max(maxx,num);
st.push(s[i]);
num=0;
}else{
st.push(s[i]);
}
}
maxx=max(maxx,num);
cout << maxx;
return 0;
}
总结:
在((((连续左括号处,没有深入的思考,导致思路堵死。对栈空情况没有理解清楚,导致段错误。对于多个逻辑符号存在的情况,没有考虑到其判断逻辑的先后顺序导致段错误。