ＡＣＭ１１００题．
In the land of Hedonia the official language is Hedonian. A Hedonian professor had noticed that many of her students still did not master the syntax of Hedonian well. Tired of correcting the many syntactical mistakes, she decided to challenge the students and asked them to write a program that could check the syntactical correctness of any sentence they wrote. Similar to the nature of Hedonians, the syntax of Hedonian is also pleasantly simple. Here are the rules:
0. The only characters in the language are the characters p through z and N, C, D, E, and I.
1. Every character from p through z is a correct sentence.
2. If s is a correct sentence, then so is Ns.
3. If s and t are correct sentences, then so are Cst, Dst, Est, and Ist.
4. Rules 0. to 3. are the only rules to determine the syntactical correctness of a sentence.
You are asked to write a program that checks if sentences satisfy the syntax rules given in Rule 0. - Rule 4.
Input:
Each input sentence is ended by a new-line character. The collection of sentences is terminated by the end-of-file character. If necessary, you may assume that each sentence has at most 256 characters and at least 1 character.
Output:
The output consists of the answers YES for each well-formed sentence and NO for each not-well-formed sentence. The answers are given in the same order as the sentences. Each answer is followed by a new-line character, and the list of answers is followed by an end-of-file character.
Sample Input:
Cp
Isz
NIsz
Cqpq
Sample Output:
NO
YES
YES
NO
上面是英文的，大家要不习惯，我晚上回来再翻译一下．
先谢谢了！！
以下是我的代码．
我先把字符串的字符Ｎ处理掉，然后把它们构造成二叉树的形式，如果构造成功，则就是ＹＥＳ，反之就是ＮＯ，中间还构造了一个栈来辅助判断。
请各位高手帮忙指点指点为什么程序连运行都不行啊，ＷＴＣ是对的，但Ｃ－ＦＲＥＥ不能正常运行。
#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 ;
}
void InitialStack(list_stack*stack)
{
stack=(list_stack*)malloc(sizeof(list_stack));
stack->link=NULL ;
}
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)
{
int 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 ;
int 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 ;
/*把'N'字符处理掉*/
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 ;
InitialStack(s);
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);
}
return 0 ;
}
[此贴子已经被作者于2006-9-26 20:49:34编辑过]
。
