推斷一個序列是否是有效是簡單的。
可是推斷序列是不是有多個解會出問題。
那么從i=0 ~l
假設讀到問號，推斷該問號成為（能否有效，該問號為）是否有效。
假設都有效，則必有多個解。
假設都無效，則無解。
假設一個有效，則把問號改成有效的括號。
代碼實現(xiàn)例如以下
#include<stdio.h>
#include<string.h>
char s[1000005],tp[1000005];
int l;
int pd()
{
int zuo,you,num,i;
num=0;
zuo=0;
you=0;
for(i=0;i<l;i++)
{
num++;
if(num==1)
{
if(tp[i]=='?')
tp[i]='(';
}
if(tp[i]=='(') zuo++;
if(tp[i]==')') you++;
if(you>num/2)
{
return 0;
}
if(num%2==0)
{
if(you==num/2)
{
zuo=0;
you=0;
num=0;
}
}
}
if(zuo>num/2) return 0;
num=0;
zuo=0;
you=0;
for(i=l-1;i>=0;i--)
{
num++;
if(num==1)
{
if(tp[i]=='?')
tp[i]=')';
}
if(tp[i]=='(') zuo++;
if(tp[i]==')') you++;
if(zuo>num/2)
{
return 0;
}
if(num%2==0)
{
if(zuo==num/2)
{
zuo=0;
you=0;
num=0;
}
}
}
if(you>num/2) return 0;
return 1;
}
int main()
{
int zuo,you,x,y,i;
while(scanf("%s",s)!=EOF)
{
l=strlen(s);
if(l%2==1)
{
printf("None\n");
continue;
}
else
{
strcpy(tp,s);
x=pd();
if(x==0)
{
printf("None\n");
continue;
}
for(i=0;i<l;i++)
{
if(s[i]=='?')
{
strcpy(tp,s);
tp[i]=')';
x=pd();
strcpy(tp,s);
tp[i]='(';
y=pd();
if(x+y==2)
{printf("Many\n");
break;
}
if(x+y==0)
{
printf("None\n");
break;
}
if(x==1)
s[i]=')';
else
s[i]='(';
}
}
if(i==l)
{
printf("Unique\n");
}
}
}
return 0;
}
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
