| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2843 人关注过本帖
标题:[求助]一道ACM题
只看楼主 加入收藏
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
 问题点数:0 回复次数:44 
[求助]一道ACM题

ACM1100题.
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

上面是英文的,大家要不习惯,我晚上回来再翻译一下.
先谢谢了!!
以下是我的代码.
我先把字符串的字符N处理掉,然后把它们构造成二叉树的形式,如果构造成功,则就是YES,反之就是NO,中间还构造了一个栈来辅助判断。
请各位高手帮忙指点指点为什么程序连运行都不行啊,WTC是对的,但C-FREE不能正常运行。
#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++];
/*遇到是CDEI大写字母则进栈*/
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 ;
/*当栈空且K值长度等于字符串就是YES*/

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编辑过]

搜索更多相关主题的帖子: ACM Hedonian syntax correctness syntactical 
2006-09-26 17:16
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
这是翻译,可能翻译得不太好,不过大体意思是出来了.
在Hedonia国,hdeonian是官方语言。一个教Hedonia的教授注意到她的学生有很多仍然不懂hdeonian的语法规则。每次都帮学生纠正语法错误,让她感到很累,她决定给学生一个挑战性的任务:让他们去编个能检查每个句子语法是否出错的程序。和Hedonia国的大自然类似,hdeonian的语法规则也是非常简单的,这里有几条规则:
0:hdeonian的句子只能由p-z以及N,C,D,E,I这几个字母构成。
1:每个单独从p-z之间的字母都是一个正确的句子。
2:如果s是一个正确的句子,那么Ns也是正确的句子。
3:如果s和t都是正确的句子,那么Cst,Dst,Est,Ist也都是正确的句子。
4:0-3是判断这个句子语法是否正确的唯一规则。
现在让你编一个检查句子是否有语法错误的程序。
输入:
每句输入的句子以回车符结束。输入以EOF结束。
你可以认为每句话最多有256个字符,最少有一个字符。
输出:
输出为YES(那些符合语法的)或NO(那些不符语法的)的字符串。每个答案都要占一行。而且最后答案以EOF结束。
样例输入:
Cp
Isz
NIsz
Cqpq
样例输出:
NO
YES
YES
NO

对不礼貌的女生收钱......
2006-09-26 18:12
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 

汗,你写的程序确实够长的,好多指针啊,看不懂
看了一下题目应该没这么复杂吧,
只要定义一个数组,再从后往前遍历一遍就可以了啊,
int count=0;//记录句子的个数,
1.st[i]>='p'&&st[i]<='z',count++;
2.st[i]=C,D,E,I; count--;
3.st[i]=='N',不用处理
4.,如果是不符和的字符,立即退出判断,
最后判断是否只有一个句子.


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-09-26 20:33
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 

规则1是每个单独从p-z之间的字母都是一个正确的句子。
只是一个单独的字母,也就是说像pq这样的句子语法是错误的。
您似乎误解了题目的意思,或许是我没翻译好,不好意思
一开始的时候,我是用递归去解的,后来提交的时候,time limit exceed.所以换成二叉树配合栈来解速度会提高很多.
您帮我看看哪地方内存出错了?在WTC下运行答案都是对的,在C-FREE老是说某地方的内存不能为read.
先谢过,呵呵。

[此贴子已经被作者于2006-9-26 20:58:59编辑过]


对不礼貌的女生收钱......
2006-09-26 20:55
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用soft_wind在2006-9-26 20:55:15的发言:

规则1是每个单独从p-z之间的字母都是一个正确的句子。
只是一个单独的字母,也就是说像pq这样的句子语法是错误的。//当然是错的,因为他有两个句子嘛
您似乎误解了题目的意思,或许是我没翻译好,不好意思
一开始的时候,我是用递归去解的,后来提交的时候,time limit exceed.所以换成二叉树配合栈来解速度会提高很多.
您帮我看看哪地方内存出错了?在WTC下运行答案都是对的,在C-FREE老是说某地方的内存不能为read.
先谢过,呵呵。


我用VC可以运行啊....不过,
事实上你的程序还是错了,我测了一组数据,
IIseIse 你输出的是NO,


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-09-26 21:04
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用soft_wind在2006-9-26 17:16:23的发言:

ACM1100题.
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

上面是英文的,大家要不习惯,我晚上回来再翻译一下.
先谢谢了!!
以下是我的代码.
我先把字符串的字符N处理掉,然后把它们构造成二叉树的形式,如果构造成功,则就是YES,反之就是NO,中间还构造了一个栈来辅助判断。
请各位高手帮忙指点指点为什么程序连运行都不行啊,WTC是对的,但C-FREE不能正常运行。
#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++];
/*遇到是CDEI大写字母则进栈*/
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 ;
/*当栈空且K值长度等于字符串就是YES*/

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 ;
}



汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-09-26 21:12
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
C-FREE不能运行,ACM的编译器好象是gcc的,反正编译不通过,估计出的问题和C-FREE的差不多。
至于您说的那个例子.因为e不是合法的字符,所以输出NO.
或者您可以把您的算法再说一下,我没理解您3楼的算法

对不礼貌的女生收钱......
2006-09-26 21:16
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
恩,谢谢!我再检查一下!
果然到那地方就不行了,呵呵。

对不礼貌的女生收钱......
2006-09-26 21:21
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 

汗,不好意思,你的程序确实在VC中不能运行.....
我的想法其实很简单:
若要满足要求,则整个字符串肯定只能转化为一个句子(字符)..
接着从后往前遍历,....
int count=0;//记录句子的个数,
1.st[i]>='p'&&st[i]<='z',count++;
2.st[i]=C,D,E,I; count--;//因为把两个句子合成了一个句子
3.st[i]=='N',不用处理//句子的个数不变
4.,如果是不符和的字符,
最后判断是否只有一个句子
楼主可以试试,我的算法实现很简单的,不对再讨论(我也不会证明).

PS..一点小建议:
输入可以写成while(gets(string)) ;
最好不要动态开辟内存,很容易出现问题的,偶觉得


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2006-09-26 21:28
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
收藏
得分:0 
while(gets(string)) ;这样写有些编译器不能正常退出,所以有些牛人都提倡那种输入,我也是学他们的,呵呵。
我那个push没错啊,我找不到,晕啊!
您的算法我有些了解了.恩,比我强多了!哈哈
看来是我想复杂了,晕死!

对不礼貌的女生收钱......
2006-09-26 21:38
快速回复:[求助]一道ACM题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030516 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved