fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string s;
  5.  
  6. int check(int l, int r, int depth) {
  7. if (l > r) return 0;
  8. if (l == r - 1) return 1;
  9. stack<pair<int, int>> stk;
  10. int ans = 1;
  11. for (int i = l; i <= r; i++) {
  12. if (s[i] == '(') {
  13. stk.push({i, depth + stk.size()});
  14. } else {
  15. pair<int, int> p = stk.top();
  16. stk.pop();
  17. if (p.second == depth) {
  18. ans += check(p.first + 1, i - 1, depth + 1);
  19. }
  20. }
  21. }
  22. return ans;
  23. }
  24.  
  25. void solve() {
  26. int n;
  27. cin >> n;
  28. cin >> s;
  29. cout << check(0, 2 * n - 1, 1) << endl;
  30. }
  31.  
  32. int main() {
  33. // your code goes here
  34. int t;
  35. cin >> t;
  36. while (t--) solve();
  37. }
Success #stdin #stdout 0.01s 5296KB
stdin
5
1
()
3
()(())
3
((()))
4
(())(())
9
(())(((())))(()())
stdout
1
2
3
3
6