/*原程序*/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
typedef struct BITREE
{
char data ;
struct BITREE*lchild,*rchild ;
}
BitNode ;
typedef BitNode*element ;
typedef struct STACK
{
element data ;
struct STACK*link ;
}
list_stack ;
int isEmpty(list_stack*stack)
{
if(stack->link)
return 0 ;
else return 1 ;
}
list_stack* InitialStack()
{
list_stack*stack=(list_stack*)malloc(sizeof(list_stack));
stack->link=NULL ;
return stack;
}
void push(list_stack*stack,element num)
{
list_stack*node=(list_stack*)malloc(sizeof(list_stack));
node->data=num ;
node->link=stack->link ;
stack->link=node ;
}
element GetTop(list_stack*stack)
{
if(!isEmpty(stack))
return stack->link->data ;
else return NULL ;
}
void pop(list_stack*stack)
{
if(!isEmpty(stack))
{
list_stack*node=stack->link ;
stack->link=node->link ;
free(node);
}
}
int isCaptal(char ch)
{
unsigned i ;
char obt1[]="CDEI" ;
for(i=0;i<strlen(obt1);i++)
if(ch==obt1[i])
return 1 ;
return 0 ;
}
int main(void)
{
char string[257]=
{
'\0'
}
,str[257]=
{
'\0'
}
;
char ch ;
unsigned i=0,j=0,flag,k=0 ;
list_stack*s=NULL ;
BitNode*p=NULL,*q=NULL ;
while(1)
{
gets(string);
flag=1 ;
if(string[0]=='\0')
break ;
if(string[strlen(string)-1]=='N')
{
printf("NO\n");
continue;
}
for(i=0;i<strlen(string);i++)
{
if(string[i]!='N')
str[j++]=string[i];
}
str[j]='\0' ;
for(i=0;i<strlen(str);i++)
if(str[i]<112||str[i]>122)
{
if(str[i]!=67&&str[i]!=68&&str[i]!=69&&str[i]!=73)
{
printf("NO\n");
flag=0 ;
break ;
}
}
if(flag)
{
k=0 ;
s=InitialStack();
while(1)
{
ch=str[k++];
if(isCaptal(ch))
{
p=(BitNode*)malloc(sizeof(BitNode));
push(s,p);
p->data=ch ;
p=p->lchild ;
}
else
{
p=(BitNode*)malloc(sizeof(BitNode));
p->data=ch ;
p->lchild=p->rchild=NULL ;
if(isEmpty(s)&&k==strlen(str))
{
printf("YES\n");
break ;
}
else if(isEmpty(s))
{
printf("NO\n");
break ;
}
q=GetTop(s);
pop(s);
p=q->rchild ;
}
}
}
j=0 ;
free(s);
s=NULL;
}
return 0 ;
}
/*按照9楼的程序,稍微变动而已*/
#include "stdio.h"
#include "string.h"
int isCaptal(char ch)
{
unsigned i ;
char obt1[]="CDEI" ;
for(i=0;i<strlen(obt1);i++)
if(ch==obt1[i])
return 1 ;
return 0 ;
}
int isN(char ch)
{
if(ch=='N')
return 1;
else return 0;
}
int isLower(char ch)
{
if(ch>='p'&&ch<='z')
return 1;
else return 0;
}
int isLetter(char ch)
{
if(isCaptal(ch)||isN(ch)||isLower(ch))
return 1;
else return 0;
}
int isValue(char ch)
{
if(isLower(ch))
return 1;
else if(isN(ch))
return 0;
else if(isCaptal(ch))
return -1;
}
int main(void)
{
char str[257]=
{
'\0'
}
;
int counter[256]={0};
int i,flag=1;
while(1)
{
flag=1;
gets(str);
for(i=0;i<256;i++)
counter[i]=0;
if(str[0]=='\0')
break ;
for(i=0;i<strlen(str);i++)
{
if(!isLetter(str[i]))
{
printf("NO\n");
flag=0;
break;
}
}
if(flag)
{
if(!isLower(str[strlen(str)-1]))
{
printf("NO\n");
flag=0;
continue;
}
}
if(flag)
{
counter[strlen(str)-1]=1;
for(i=strlen(str)-2;i>=0;i--)
{
counter[i]=counter[i+1]+isValue(str[i]);
if(counter[i]<1)
{
flag=0;
printf("NO\n");
break;
}
}
if(counter[0]==1)
printf("YES\n");
else if(flag) printf("NO\n");
}
}
return 0;
}
我改了我的程序,都能运行了,但提交的时候,超时,估计不是算法太差,而是忽略了某些情况,在某些情况下不能输出,导致延时。
请大家帮忙看看,还有哪种情况忽略了,打印不出结果。
[此贴子已经被作者于2006-9-27 14:13:48编辑过]