思路

可以用栈，先尽可能配对。符合题意的序列是在原序列的左边加左括号，右边加右括号，最终看栈里有多少个左括号和右括号未配对即可。

code

#include<bits/stdc++.h>
using namespace std;
stack<char> s;
string str;
int n;
int main(){
	cin>>n>>str;
	for(int i=0;i<n;i++){
		if(!s.empty()&&(str[i]==')'&&s.top()=='('))
			s.pop();
		else
			s.push(str[i]);
	}
	int l=0,r=0;
	while(s.size()){
		if(s.top()=='(')	r++;
		else	l++;
		s.pop();
	}
	while(l--)	cout<<'(';
	cout<<str;
	while(r--)	cout<<')';
}