如果是一个合法的序列,每对配对的括号的两个字符(‘(’ 和 ')' 或者 '[' 和 ']')一定是相邻的,每次判断下该字符是否有配对即可。
如果配对,将左括号出栈即可。特别注意:空格也是合法的。
AC代码:
#include<cstdio> #include<stack> using namespace std; const int maxn = 200; char str[maxn]; stack<char>s; bool Balance(){ char ch; for(int i = 0; str[i] != '\n'; ++i){ if(str[i] == ' ') continue; if(!s.empty()) { ch = s.top(); if(ch == '(' && str[i] == ')' || ch == '[' && str[i] == ']') s.pop(); else s.push(str[i]); } else s.push(str[i]); } if(s.empty()) return true; else while(!s.empty()) s.pop(); return false; } int main(){ int T; scanf("%d", &T); getchar(); while(T--){ fgets(str, sizeof(str), stdin); if(Balance()) printf("Yes\n"); else printf("No\n"); } return 0; }
如有不当之处欢迎指出!