你说，你的女朋友就是你的电脑

0
Nightglow Acmer LV 8 @ 3 years ago
看了看现有的括号匹配的题解，发现大家的代码都是比较长的，所以我就发一下我的详细思路和代码吧。

思路： 匹配失败的可能情况只有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; }
Copy