7 solutions
-
1
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; while(n--) { stack <char> s; string x;//字符串x用于最开始的存储 cin>>x; getchar(); int ret=1,l=x.size();//ret用于记录可行性 for(int i=0;i<l;i++) { if(s.empty()&&(x[i]=='}'||x[i]=='>'||x[i]==']'||x[i]==')')) {ret=0;break;}//栈为空的时候如果匹配到反括号肯定是不行的 if(x[i]=='{'||x[i]=='<'||x[i]=='('||x[i]=='[') s.push(x[i]); else { switch(x[i])//开始匹配 { case '}':if('{'==s.top()) { s.pop(); } else ret=0; break; case ')':if('('==s.top()) { s.pop(); } else ret=0; break; case '>':if('<'==s.top()) { s.pop(); } else ret=0; break; case ']':if('['==s.top()) { s.pop(); } else ret=0; break; } } } ret==1&&s.empty()?cout<<"YES"<<endl:cout<<"NO"<<endl;//根据ret判断 } return 0; } -
0
看了看现有的括号匹配的题解，发现大家的代码都是比较长的，所以我就发一下我的详细思路和代码吧。
思路： 匹配失败的可能情况只有3种，只要三种都避免了就一定匹配成功。
第一种：在匹配的过程中，当一个右括号即将进栈时，发现栈是空的，也就是说明无论怎么样一定有一个右括号无法匹配起与之相对应的左括号，所以匹配失败。
第二种：当一个右括号即将进栈时，发现栈顶元素不是其对应的左括号，于是匹配失败。
第三种：在所有的括号都匹配完后，如果栈是非空的，就说明一定有左括号没有与之对应的右括号匹配，匹配失败。
代码思路： 所有的左括号直接入栈，为了方便判断第二种情况，栈顶元素是不是右括号对应的左括号，入栈的是左括号对应的右括号，这样只要直接判断是不是相同就行了。如果过程中，栈空或者栈顶元素不匹配就直接输入"NO"，终止循环。若以上判断都没触发，那就是右匹配到了相对应的左括号，左右括号相抵消，表现出来就是栈顶元素出栈。在最后，再判断一下是否栈空就行了。
#include <bits/stdc++.h> #include <stack> using namespace std; int main() { int t; string s; cin >> t; while (t--) { int f = 0; stack<char> S; cin >> s; int l = s.length(); for (int i = 0; i < l; i++) { if (s[i] == '(') S.push(')'); else if (s[i] == '[') S.push(']'); else if (s[i] == '<') S.push('>'); else if (s[i] == '{') S.push('}'); else if (S.empty() || s[i] != S.top()) { cout << "NO" << endl; f = 1; break; } else S.pop(); } if (f == 1) continue; if (!S.empty()) cout << "NO" << endl; else cout << "YES" << endl; } return 0; } -
0
这道题其实和前面类似
#include<bits/stdc++.h> typedef long long ll; using namespace std; string s; int main() { stack <int> q; int t; cin>>t; while(t--) { int flage=0; cin>>s; for(int i=0;i<s.size();i++) { if(q.empty()) flage=0; else flage=1; if(s[i]=='('||s[i]=='<'||s[i]=='['||s[i]=='{') { q.push(s[i]); } else if(flage==1&&((s[i]==')'&&q.top()=='(')||(s[i]=='}'&&q.top()=='{')||(s[i]==']'&&q.top()=='[')||(s[i]=='>'&&q.top()=='<'))) { q.pop(); }else{ q.push(s[i]); } } if(q.empty()) cout<<"YES"<<endl; else cout<<"NO"<<endl; while(!q.empty()) q.pop(); } return 0; } -
0
这题比较基础，细心一点，不然要暴毙= =
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,fg; char a[105]; stack<char> s; char b[15]={0,'(',')','{','}','[',']','<','>'}; int main() { scanf("%d",&n); while(n--) { fg=1; scanf("%s",a); for(int i=0;i<strlen(a);++i) { if(a[i]==b[1]||a[i]==b[3]||a[i]==b[5]||a[i]==b[7]) { s.push(a[i]); } else { if(s.empty()) { fg=0; break; } else { if(a[i]==b[2]) { if(s.top()==b[1]) { s.pop(); continue; } else { fg=0; break; } } else if(a[i]==b[4]) { if(s.top()==b[3]) { s.pop(); continue; } else { fg=0; break; } } else if(a[i]==b[6]) { if(s.top()==b[5]) { s.pop(); continue; } else { fg=0; break; } } else if(a[i]==b[8]) { if(s.top()==b[7]) { s.pop(); continue; } else { fg=0; break; } } } } } if(fg==0||!s.empty()) printf("NO\n"); else printf("YES\n"); while(!s.empty())//这步很重要！！不然直接暴毙，别问我为什么= = { s.pop(); } } return 0; } -
0
思路和本章前两题相同
不同的只是重复了四次
#include<bits/stdc++.h> #include<string.h> using namespace std; int t,cnt,ans; char c[1005]; int main() { std::ios::sync_with_stdio(false); cin>>t; while(t--) { stack<char> st; cin>>c; for(int i=0;i<strlen(c);i++) { if(c[i]=='(')//第一对括号（） st.push(c[i]); else if(c[i]==')') { if(!st.empty()&&st.top()=='(') st.pop(); else{ st.push(')');//否则就直接塞一个符号进去然后直接break break; } } else if(c[i]=='{')//第二对括号{} st.push(c[i]); else if(c[i]=='}') { if(!st.empty()&&st.top()=='{') st.pop(); else{ st.push('}');//否则就直接塞一个符号进去然后直接break break; } } else if(c[i]=='[')//第三对括号[] st.push(c[i]); else if(c[i]==']') { if(!st.empty()&&st.top()=='[') st.pop(); else{ st.push(']');//否则就直接塞一个符号进去然后直接break break; } } else if(c[i]=='<')//第四对括号 st.push(c[i]); else if(c[i]=='>') { if(!st.empty()&&st.top()=='<') st.pop(); else{ st.push('>');//否则就直接塞一个符号进去然后直接break break; } } } if(st.empty()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } -
0
#include<stdio.h> #include<stack> #include<iostream> #include<string.h> using namespace std; int main() { int t,k; scanf("%d",&t); char a = '(',b = ')',c = '{',d = '}',e = '[',f = ']',g = '<',h = '>'; while(t--) { char str[100]; scanf("%s",str); k=1; stack<char>arr; for(int i = 0;i<strlen(str);i++) { if(str[i]==a||str[i]==c||str[i]==e||str[i]==g){ arr.push(str[i]); } if(str[i]==b||str[i]==d||str[i]==f||str[i]==h){ if(arr.size()==0){ k = 0; printf("NO"); break; } else if(str[i]==b){ if(arr.top()!=a){ k = 0; printf("NO"); break; } } else if(str[i]==d){ if(arr.top()!=c){ k = 0; printf("NO"); break; } } else if(str[i]==f){ if(arr.top()!=e){ k = 0; printf("NO"); break; } } else if(str[i]==h){ if(arr.top()!=g){ k = 0; printf("NO"); break; } } if(k!=0){ arr.pop(); } } } if(k==1){ if(arr.size()==0)printf("YES"); else printf("NO"); } printf("\n"); memset(str,0,sizeof(str)); } return 0; } -
0
swpumarshal LV 8 @ 2022-1-2 10:34:17
#include<bits/stdc++.h> using namespace std; stack <int> s; string a; int main(){ int t; cin>>t; for(int j=0;j<t;j++){ cin>>a; for(int i=0;i<a.size();i++){ if(a[i]=='('){//四个符号选择程序都一样直接复制改一下就可以，虽然看着多但是复制直接起飞； s.push(1); } else if(a[i]==')'){ if(!s.empty()&&s.top()==1){ s.pop(); } else{ s.push(-1); } } else if(a[i]=='['){ s.push(2); } else if(a[i]==']'){ if(!s.empty()&&s.top()==2){ s.pop(); } else{ s.push(-2); } } else if(a[i]=='{'){ s.push(3); } else if(a[i]=='}'){ if(!s.empty()&&s.top()==3){ s.pop(); } else{ s.push(-3); } } else if(a[i]=='<'){ s.push(4); } else if(a[i]=='>'){ if(!s.empty()&&s.top()==4){ s.pop(); } else{ s.push(-4); } } } if(!s.empty()){ cout<<"NO"<<endl; } else{ cout<<"YES"<<endl; } while(!s.empty()){ s.pop(); } } return 0; }
- 1