sgu179 SGU起航！

//发现dfs除了搜索功能外的其他功能，他本身是一种序列，这个题恰是“先序”的下一个（合法范围内）序列！


#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct state       
{
    string s;
    int sum_0;
    int sum_1;
};
vector<state>v;
bool flag;
void dfs(int cur,state ss,int size,string xulie)
{
    if(cur%2==0)  //剪枝一：一旦发现小了，马上回溯！
    {
        string temp1(xulie,0,cur-1);//只比前cur个字符
       if(ss.s<temp1)
        {
          return;
        }
    }
    if(flag==1)return;
    if(cur==size)   //一次获得即可返回，DFS序列本可以是字典序！
    {
        if(ss.sum_0==ss.sum_1&&ss.s>xulie)
           { v.push_back(ss);flag=1;}
    }
    else
    {
        if(ss.sum_0<=size/2)
        {
              state temp_ss(ss);      //只建立临时对象传递下去！
              temp_ss.sum_0=ss.sum_0+1;temp_ss.s=ss.s+"0";  
              dfs(cur+1,temp_ss,size,xulie);
        }
        if(ss.sum_1+1<=ss.sum_0)
        {
             state temp_ss(ss);
             temp_ss.sum_1=ss.sum_1+1;temp_ss.s=ss.s+"1";
              dfs(cur+1,temp_ss,size,xulie);
        }
    }
}
int main()
{    string xulie;
    while(cin>>xulie)
    {
        v.clear();
        flag=0;
        state ss;
      ss.s="0";ss.sum_0=1;ss.sum_1=0;

     for(int i=0;i<xulie.size();i++)
      {
          if(xulie[i]=='(')
               xulie[i]='0';
          else
             xulie[i]='1';
      }
      dfs(1,ss,xulie.size(),xulie);
          if(!v.empty())
           {
               string temp2;
               for(int i=0;i<v[0].s.size();i++)
                    {
                        if((v[0].s)[i]=='0')
                         temp2+='(';
                        else
                        temp2+=')';
                    }
                cout<<temp2<<endl;
           }
          else cout<<"No solution"<<endl;
    }
}