Parenthese sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072
K (Java/Others)
Problem Description
bobo found an ancient string. The string contains only three charaters -- "(", ")" and "?".
bobo would like to replace each "?" with "(" or ")" so that the string is valid (defined as follows). Check if the way of replacement can be uniquely determined.
Note:
An empty string is valid.
If S is valid, (S) is valid.
If U,V are valid, UV is valid.
Input
The input consists of several tests. For each tests:
A string s1s2…sn (1≤n≤106).
Output
For each tests:
If there is unique valid string, print "Unique". If there are no valid strings at all, print "None". Otherwise, print "Many".
Sample Input
?? ???? (??
Sample Output
Unique Many None
题意：输入一个长度不超过10^6的字符串，串中只包含‘（’、‘）’、‘?’。其中‘?’既可以当做’（‘， 又可以当做’）‘，求有多少种方法满足括号匹配。如果不能匹配，输出“None”；如果只有一种，输出“Unique”；否则输出“Many”。
分析：如果没有‘?’，问题就变成了简单的括号匹配，这个很好判断；
每次遇到一个‘?’，我们可以先把这个‘?’变成‘（’，判断是否匹配；再把‘?’变成')',判断是否匹配。
如果都匹配，则有多种匹配方法；
如果都不匹配，则无法匹配；
如果只有一个匹配，则把这个‘?’变成使之匹配的括号，然后继续判断下一个‘?'即可。
#include<cstdio>
#include<cstring>
const int N = 1e6 + 50;
char str[N], s[N];
int len;
int judge() //判断当前的字符串是否匹配
{
int l = 0; //记录左括号的数量
int r = 0; //记录右括号的数量
int num = 0; //记录已经遍历过的字符数量
int i;
for(i = 0; i < len; i++) //从前往后判断
{
num++;
if(num == 1)
{
if(s[i] == '?')
s[i] = '(';
}
if(s[i] == '(') l++;
else if(s[i] == ')') r++;
if(r > num/2) //右括号数量太多，无法完全匹配
return 0;
if(r * 2 == num) //前num个可以完全匹配
{
l = r = num = 0;
}
}
if(l > num/2) return 0;
num = l = r = 0;
for(i = len - 1; i >= 0; i--) //从后往前判断
{
num++;
if(num == 1)
{
if(s[i] == '?')
s[i] = ')';
}
if(s[i] == '(') l++;
else if(s[i] == ')') r++;
if(l > num / 2) return 0; //左括号数量太多，无法完全匹配
if(l * 2 == num) //后num个可以完全匹配
{
l = r = num = 0;
}
}
if(r > num/2) return 0;
return 1;
}
int main()
{
int flag_l, flag_r, i;
while(~scanf("%s",str))
{
len = strlen(str);
if(len & 1)
{
printf("None\n");
continue;
}
strcpy(s, str);
flag_l = judge(); //假设没有 '?'，判断是否匹配
if(!flag_l)
{
printf("None\n");
continue;
}
for(i = 0; i < len; i++)
{
if(str[i] == '?')
{
strcpy(s, str);
s[i] = ')';
flag_l = judge();
s[i] = '(';
flag_r = judge();
if(flag_l && flag_r)
{
printf("Many\n");
break;
}
if(!flag_l && !flag_r)
{
printf("None\n");
break;
}
if(flag_l && !flag_r)
s[i] = ')';
else if(!flag_l && flag_r)
s[i] = '(';
}
}
if(i == len)
printf("Unique\n");
}
return 0;
}