题意
有三种括号'{}','[]','()',找出最长连续匹配的括号,输出其长度。
分析
括号匹配用栈来模拟,每次将括号与栈顶元素进行匹配,然后将配对的括号出栈,并且当前连续匹配的括号长度+2,如果遇到不配对的括号了,将其入栈并且连续长度置为0,即前面连续匹配长度计算完毕,每次在进行一个max比较。
代码
#include <bits/stdc++.h> using namespace std; string s; stack<char> sk; int cnt,ans; int main(){ cin>>s; sk.push(s[0]); for(int i = 1; i < s.size(); i++){ if(s[i] == ')' && sk.top() == '('){ cnt += 2; sk.pop(); } else if(s[i] == '}' && sk.top() == '{'){ cnt += 2; sk.pop(); } else if(s[i] == ']' && sk.top() == '['){ cnt += 2; sk.pop(); } else if(s[i] == ')' || s[i] == ']' || s[i] == '}'){ cnt = 0; //只有遇到右括号且与栈顶元素不配对的时候,就代表连续子序列匹配结束 sk.push(s[i]); } else sk.push(s[i]); //左括号仍有机会配对成功,直接入栈 ans = max(ans,cnt); } cout<<ans<<endl; return 0; }