Parenthese sequence

??
????
(??

Unique
Many
None

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1001000;

char str[maxn];
int num[maxn],prefix[maxn],suffix[maxn];
int pre0[maxn],suf0[maxn];

void init()
{
    memset(num,0,sizeof(num));
    memset(prefix,0,sizeof(prefix));
    memset(suffix,0,sizeof(suffix));
    memset(pre0,0,sizeof(pre0));
    memset(suf0,0,sizeof(suf0));
}

int main()
{
while(scanf("%s",str)!=EOF)
{
    int n=strlen(str);
    if(n%2==1)
    {
        puts("None"); continue;
    }
    init();
    for(int i=0;i<n;i++)
    {
        if(str[i]=='(') num[i+1]=1;
        else if(str[i]==')') num[i+1]=-1;
        else if(str[i]=='?') num[i+1]=0;
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(num[i]) prefix[i]=prefix[i-1]+num[i];
        else prefix[i]=prefix[i-1]+1;
        if(prefix[i]<0)
        {
            flag=0; break;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(prefix[i]<=1)
            pre0[i]=pre0[i+1]+1;
        else pre0[i]=pre0[i+1];
    }
    if(flag==false)
    {
        puts("None"); continue;
    }
    for(int i=n;i>=1;i--)
    {
        if(num[i]) suffix[i]=suffix[i+1]-num[i];
        else suffix[i]=suffix[i+1]+1;
        if(suffix[i]<0)
        {
            flag=false;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(suffix[i]<=1)
            suf0[i]=suf0[i-1]+1;
        else suf0[i]=suf0[i-1];
    }
    if(flag==false)
    {
        puts("None"); continue;
    }
    int cnt=0;
    for(int i=2;i<n;i++)
    {
        if(num[i]==0)
        {
            if( (prefix[i]>=2&&pre0[i]==0) && (suffix[i]>=2&&suf0[i]==0) )
                cnt++;
        }
    }
    if(cnt)
        puts("Many");
    else
        puts("Unique");
}
	return 0;
}

HDOJ 4915 Parenthese sequence,布布扣,bubuko.com

HDOJ 4915 Parenthese sequence

原文：http://blog.csdn.net/ck_boss/article/details/38510943