2013 湘潭邀请赛 Jack’s sequence

题目描述

定义括号序列为如下规则序列(字符串): 1 空序列是规则序列; 2 如果S是规则序列,那(S)也是规则序列; 3 如果A和B都是规则序列,那么AB也是规则序列. 例如,下面的字符串都是规则序列: (), (()), ()() , ()(()) , (()()) 现在有一个合法的括号序列，你的任务是找出该序列“下一个”合法且与原序列等长的括号序列。 这里下一个指的是字典序比较，认为 '(' 小于 ')' ，例如 "(())" < "()()"

输入

多组测试数据。第一行有一个正整数T(T ≤ 1000)，表示有T组数据。 每组数据占一行，为一行括号序列，保证括号序列合法且长度 <= 10,000。

输出

每组测试数据输出一行。 如果该序列存在“下一个”合法且与原序列等长的括号序列，输出它。 如果不存在，则输出"No solution"。

样例输入

4
()()
(())()
()(())
((()))

样例输出

No solution
()(())
()()()
(()())


代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char a[10005];
int  f[10005];
int main()
{
    int i,j,k,n,m,num,wz;
    while(scanf("%d",&m)>0)
    {
        while(m--)
        {
            scanf("%s",a+1);
             memset(f,0,sizeof(f));
            n=strlen(a+1);
            for(i=1;i<=n;i++)
            {
            if(a[i]=='(')
                f[i]=f[i-1]+1;
            else if(a[i]==')')
                f[i]=f[i-1]-1;
            }
        for(i=n,num=0,wz=0;i>=1;i--)
            if(a[i]=='('&&f[i]>1)
            {
                num=f[i]-1;
                wz=i;
                break;
            }
            if(wz==0&&num==0)
                printf("No solution\n");
            else
            {
                for(i=1;i<wz;i++)
                       printf("%c",a[i]);
                printf(")");
                n=n-wz;
                num=(n-num+1)/2;
                for(i=1;i<=num;i++)
                    printf("(");
                for(i=1;i<=n-num;i++)
                    printf(")");
                printf("\n");
            }
        }
    }
    return 0;
}