主题:[讨论]魔王语言转换问题
在做数据结构栈和队列这章的习题时,有道题是如下描述的:
有一个魔王总是使用自已的一种非常精练而抽象的语言讲话,没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的,因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:
(1) α→β1β2…βm
(2) (θβ1β2…βm)→(θβm…β2θβ1θ)
在这两种形式中,从左到右均表示解释; 从右到左均表示抽象。
写一个魔王解释程序,将魔王的话解释成人能听懂的话。
基本要求:设大写字母表示魔王语言的词汇,小写字母表示人的词汇,
希腊字母表示可以用大写字母或小写字母代换的变量。用下述两种规则和下述规则(2)实现。
(1) B→tAdA
(2) A→sae
测试数据:B(einxgz)B
B(einxgz)B=tsaedsaeezegexeneietsaedsae
字母-汉字对应表:
t d s a e z g x n i
天 地 上 一个 鹅 追 赶 下 蛋 恨
则魔王说的是:"天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅"。
以下是我的代码,虽然可以编译通过,但没法正确输出结果。我现在还不会用gdb调试器,一行行找错误,找了半天还找不到,请指点下。
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct{
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack;
typedef struct QNode{
char data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
void InitQueue(LinkQueue *Q); //初始化队列Q
void EnQueue(LinkQueue *Q, char e); //插入元素e为Q的新的队尾元素
char DeQueue(LinkQueue *Q); //若队列不空,删除Q的队头元素
void InitStack(SqStack *S); //构造一个空栈
void Push(SqStack *S, char e); //插入元素e为新的栈顶元素
char Pop(SqStack *S); //若栈不空,删除栈顶元素
void Input(LinkQueue *devil); //输入魔王语言
void Translate_to_human_lang(LinkQueue *after_devil, LinkQueue *devil);
//把魔王语言转化为字母语言
void Translate_to_chinese_lang(LinkQueue *after_devil, char *decipher[]);
//把字母语言转化为汉语
char *decipher[] = {"天", "地", "上", "一只", "鹅", "追", "赶", "下", "蛋", "恨"};
main(){
char e;
LinkQueue devil; //储存魔王语言
LinkQueue after_devil; //储存魔王语言转化成字母语言
Input(&devil);
Translate_to_human_lang(&after_devil, &devil);
printf("Translated language:\n");
while (after_devil.front != after_devil.rear){
//打印转化后的字母语言
e = DeQueue(&after_devil);
printf("%c", e);
}
printf("Corresponding chinese language are:\n");
Translate_to_chinese_lang(&after_devil, decipher);
}
void InitQueue(LinkQueue *Q){
//构造队列
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
QueuePtr head = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front || !head){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
Q->front->next = head;
head->next = Q->rear;
}
void EnQueue(LinkQueue *Q, char e){
//插入元素e为Q的新的队尾元素
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
p->data = e;;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
char DeQueue(LinkQueue *Q){
//若队列不空,则删除Q的队头元素,并返回删除的元素
char e;
if (Q->front == Q->rear){
//空队列
printf("Can't Delete!\n");
exit(0);
}
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
p = Q->front->next;
e = p->data;
Q->front->next = p->next;
if (Q->rear == p){
//队列中只有一个元素
Q->rear = Q->front;
}
if (p->next != NULL){
free(p);
}
return e;
}
void InitStack(SqStack *S){
//构造一个空栈
S->base = (char *) malloc(STACK_INIT_SIZE * sizeof(char));
if (!S->base){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
}
void Push(SqStack *S, char e){
//插入元素e为新的栈顶元素
if (S->top - S->base >= S->stacksize){
//栈满,追加存储空间
S->base = (char *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(char));
if (!S->base){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;
}
char Pop(SqStack *S){
//若栈不为空,则删除S的栈顶元素,并返回栈顶元素
char e;
if (S->top == S->base){
//空栈
printf("No element to delete!\n");
exit(0);
}
e = *--S->top;
}
void Input(LinkQueue *devil){
//输入魔王的语言
char e;
InitQueue(devil);
printf("Please enter devil language(end with '!'):");
do{
scanf("%c", &e);
EnQueue(devil, e);
}while (devil->rear->data != '!');
}
void Translate_to_human_lang(LinkQueue *after_devil, LinkQueue *devil){
//把魔王语言转化为字母语言
char e, l;
SqStack S;
InitStack(&S);
InitQueue(after_devil);
while (devil->front != devil->rear){
//逐个输出魔王语言,并将其转化为字母语言储存到after_devil队列中
char s = s, a = a, e = e, t = t, d = d, l;
char u = DeQueue(devil);
if (u >= 'A' && u <= 'Z'){
//u为大写字母
if (u == 'A'){
EnQueue(after_devil, s);
EnQueue(after_devil, a);
EnQueue(after_devil, e);
}
else if (u == 'B'){
EnQueue(after_devil, t);
EnQueue(after_devil, s);
EnQueue(after_devil, a);
EnQueue(after_devil, e);
EnQueue(after_devil, d);
EnQueue(after_devil, s);
EnQueue(after_devil, a);
EnQueue(after_devil, e);
}
}
else if (u == '('){
//把队列的括号里面的元素储存到栈中,实现逆序
u = DeQueue(devil);
while(u >= 'a' && u <= 'z' && u != ')'){
Push(&S, u);
u = DeQueue(devil);
}
do{
l = Pop(&S);
EnQueue(after_devil, e);
EnQueue(after_devil, l);
}while(S.top != S.base);
}
}
}
void Translate_to_chinese_lang(LinkQueue *after_devil, char *decipher[]){
//把字母语言转化为汉语
char e;
e = DeQueue(after_devil);
while (after_devil->front != after_devil->rear){
switch(e){
case 't': printf("%s", *decipher); break;
case 'd': printf("%s", *(decipher + 1)); break;
case 's': printf("%s", *(decipher + 2)); break;
case 'a': printf("%s", *(decipher + 3)); break;
case 'e': printf("%s", *(decipher + 4)); break;
case 'z': printf("%s", *(decipher + 5)); break;
case 'g': printf("%s", *(decipher + 6)); break;
case 'x': printf("%s", *(decipher + 7)); break;
case 'n': printf("%s", *(decipher + 8)); break;
case 'h': printf("%s", *(decipher + 9)); break;
default: printf("No related decipher!\n");
}
e = DeQueue(after_devil);
}
printf("\n");
}
有一个魔王总是使用自已的一种非常精练而抽象的语言讲话,没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的,因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:
(1) α→β1β2…βm
(2) (θβ1β2…βm)→(θβm…β2θβ1θ)
在这两种形式中,从左到右均表示解释; 从右到左均表示抽象。
写一个魔王解释程序,将魔王的话解释成人能听懂的话。
基本要求:设大写字母表示魔王语言的词汇,小写字母表示人的词汇,
希腊字母表示可以用大写字母或小写字母代换的变量。用下述两种规则和下述规则(2)实现。
(1) B→tAdA
(2) A→sae
测试数据:B(einxgz)B
B(einxgz)B=tsaedsaeezegexeneietsaedsae
字母-汉字对应表:
t d s a e z g x n i
天 地 上 一个 鹅 追 赶 下 蛋 恨
则魔王说的是:"天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅"。
以下是我的代码,虽然可以编译通过,但没法正确输出结果。我现在还不会用gdb调试器,一行行找错误,找了半天还找不到,请指点下。
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct{
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack;
typedef struct QNode{
char data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
void InitQueue(LinkQueue *Q); //初始化队列Q
void EnQueue(LinkQueue *Q, char e); //插入元素e为Q的新的队尾元素
char DeQueue(LinkQueue *Q); //若队列不空,删除Q的队头元素
void InitStack(SqStack *S); //构造一个空栈
void Push(SqStack *S, char e); //插入元素e为新的栈顶元素
char Pop(SqStack *S); //若栈不空,删除栈顶元素
void Input(LinkQueue *devil); //输入魔王语言
void Translate_to_human_lang(LinkQueue *after_devil, LinkQueue *devil);
//把魔王语言转化为字母语言
void Translate_to_chinese_lang(LinkQueue *after_devil, char *decipher[]);
//把字母语言转化为汉语
char *decipher[] = {"天", "地", "上", "一只", "鹅", "追", "赶", "下", "蛋", "恨"};
main(){
char e;
LinkQueue devil; //储存魔王语言
LinkQueue after_devil; //储存魔王语言转化成字母语言
Input(&devil);
Translate_to_human_lang(&after_devil, &devil);
printf("Translated language:\n");
while (after_devil.front != after_devil.rear){
//打印转化后的字母语言
e = DeQueue(&after_devil);
printf("%c", e);
}
printf("Corresponding chinese language are:\n");
Translate_to_chinese_lang(&after_devil, decipher);
}
void InitQueue(LinkQueue *Q){
//构造队列
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
QueuePtr head = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front || !head){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
Q->front->next = head;
head->next = Q->rear;
}
void EnQueue(LinkQueue *Q, char e){
//插入元素e为Q的新的队尾元素
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
if (!p){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
p->data = e;;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
char DeQueue(LinkQueue *Q){
//若队列不空,则删除Q的队头元素,并返回删除的元素
char e;
if (Q->front == Q->rear){
//空队列
printf("Can't Delete!\n");
exit(0);
}
QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
p = Q->front->next;
e = p->data;
Q->front->next = p->next;
if (Q->rear == p){
//队列中只有一个元素
Q->rear = Q->front;
}
if (p->next != NULL){
free(p);
}
return e;
}
void InitStack(SqStack *S){
//构造一个空栈
S->base = (char *) malloc(STACK_INIT_SIZE * sizeof(char));
if (!S->base){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
}
void Push(SqStack *S, char e){
//插入元素e为新的栈顶元素
if (S->top - S->base >= S->stacksize){
//栈满,追加存储空间
S->base = (char *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(char));
if (!S->base){
//存储分配失败
printf("No enough Memory!\n");
exit(0);
}
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;
}
char Pop(SqStack *S){
//若栈不为空,则删除S的栈顶元素,并返回栈顶元素
char e;
if (S->top == S->base){
//空栈
printf("No element to delete!\n");
exit(0);
}
e = *--S->top;
}
void Input(LinkQueue *devil){
//输入魔王的语言
char e;
InitQueue(devil);
printf("Please enter devil language(end with '!'):");
do{
scanf("%c", &e);
EnQueue(devil, e);
}while (devil->rear->data != '!');
}
void Translate_to_human_lang(LinkQueue *after_devil, LinkQueue *devil){
//把魔王语言转化为字母语言
char e, l;
SqStack S;
InitStack(&S);
InitQueue(after_devil);
while (devil->front != devil->rear){
//逐个输出魔王语言,并将其转化为字母语言储存到after_devil队列中
char s = s, a = a, e = e, t = t, d = d, l;
char u = DeQueue(devil);
if (u >= 'A' && u <= 'Z'){
//u为大写字母
if (u == 'A'){
EnQueue(after_devil, s);
EnQueue(after_devil, a);
EnQueue(after_devil, e);
}
else if (u == 'B'){
EnQueue(after_devil, t);
EnQueue(after_devil, s);
EnQueue(after_devil, a);
EnQueue(after_devil, e);
EnQueue(after_devil, d);
EnQueue(after_devil, s);
EnQueue(after_devil, a);
EnQueue(after_devil, e);
}
}
else if (u == '('){
//把队列的括号里面的元素储存到栈中,实现逆序
u = DeQueue(devil);
while(u >= 'a' && u <= 'z' && u != ')'){
Push(&S, u);
u = DeQueue(devil);
}
do{
l = Pop(&S);
EnQueue(after_devil, e);
EnQueue(after_devil, l);
}while(S.top != S.base);
}
}
}
void Translate_to_chinese_lang(LinkQueue *after_devil, char *decipher[]){
//把字母语言转化为汉语
char e;
e = DeQueue(after_devil);
while (after_devil->front != after_devil->rear){
switch(e){
case 't': printf("%s", *decipher); break;
case 'd': printf("%s", *(decipher + 1)); break;
case 's': printf("%s", *(decipher + 2)); break;
case 'a': printf("%s", *(decipher + 3)); break;
case 'e': printf("%s", *(decipher + 4)); break;
case 'z': printf("%s", *(decipher + 5)); break;
case 'g': printf("%s", *(decipher + 6)); break;
case 'x': printf("%s", *(decipher + 7)); break;
case 'n': printf("%s", *(decipher + 8)); break;
case 'h': printf("%s", *(decipher + 9)); break;
default: printf("No related decipher!\n");
}
e = DeQueue(after_devil);
}
printf("\n");
}