想到的解法比较rz,就是一层层地进入罐头,当遇到 ’ { ‘,’ [ ‘,’ ( ’ 时进入下一层罐头,当遇到 ’ } ‘,’ ] ‘,’ ) '时检查与罐头开头是否相匹配,若不匹配则彻底false,反之,继续检查。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| #include<iostream> #include<string> #include<map> using namespace std; const int maxn = 1005; string s; int now = 0; map<char, char>mp; bool ok = true; void solve(int len,int depth) { char st = s[now]; now++; while(now<len){ if (s[now] == '}' || s[now] == ']' || s[now] == ')') { if (s[now] != mp[st]) { ok = false; } return; } if (s[now] == '{' || s[now] == '[' || s[now] == '(') { solve(len, depth + 1); } now++; } } int main() { mp['{']='}'; mp['['] = ']'; mp['('] = ')'; int N; cin >> N; for(int i=1;i<=N;i++) { ok = true; now = 0; cin >> s; if (s[0] != '{'&&s[0] != '['&&s[0] != '(') { cout << "NO" << endl; continue; } int len = s.length(); solve(len, 0); if (ok && now == len - 1) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
|