栈:
#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;string str;cin >> str;stack<char> s; // 用栈来存储左括号for (int i = 0; i < n; i++) {if (str[i] == '(') {s.push('('); // 遇到左括号,压入栈} else if (str[i] == ')') {if (s.empty()) { // 栈为空,表示没有匹配的左括号cout << "No" << endl;return 0;} else {s.pop(); // 遇到右括号,弹出栈顶元素,匹配一个左括号}}}if (s.empty()) {cout<<"Yes";} else {cout<<"No"; // 如果栈不为空,表示有多余的左括号}return 0;
}
dfs
#include <iostream>
using namespace std;
int n;
string s;bool dfs(int i, int ba) {if (i == s.size()) { // 如果平衡值为 0,说明左右括号匹配return ba == 0;}if (s[i] == '(') { // 如果当前是左括号,递归到下一个位置并增加深度return dfs(i + 1, ba + 1);} else if (s[i] == ')') {return ba > 0 && dfs(i + 1, ba - 1);}return false;
}int main() {cin >> n;cin >> s;if (dfs(0, 0)) {cout << "Yes";} else {cout << "No";}return 0;
}
找到了一位大佬的巧妙解法:
#include <bits/stdc++.h>
using namespace std;
int main()
{int n; cin >> n; char x; int sum = 0; for (int i = 0; i < n; i++) {cin >> x;if (x == ')' && sum > 0) sum--; // 如果是右括号且之前有未匹配的左括号,sum 减 1else sum++; // 如果是左括号或右括号但 sum <= 0,sum 加 1}if (!sum) cout << "Yes"; // 如果 sum 为 0,说明括号匹配,输出 "Yes"else cout << "No"; // 否则输出 "No"return 0;
}