回 帖 发 新 帖 刷新版面

主题:[讨论]魔王语言转换问题

在做数据结构栈和队列这章的习题时,有道题是如下描述的:
有一个魔王总是使用自已的一种非常精练而抽象的语言讲话,没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的,因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的:
(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");
}

回复列表 (共8个回复)

沙发

找到第一个问题了
void Translate_to_human_lang(LinkQueue *after_devil, LinkQueue *devil)这个函数的while循环里char s = s, a = a, e = e, t = t, d = d, l;这里明显缺单引号了

板凳

第二个问题也找到了
你在main函数输出译文字母串的时候把原队列已经清空了,自然没有元素给你再去翻译,至于是不输出字母串还是怎么处理,相信你应该心里有数了
看完了,又解决了一个问题……可以睡觉了……

3 楼



谢谢!问题已经解决了,改后的代码放在了另外一个回复中(每个回复好像不能超过1000字)。恳请你对我的程序的排版提出建议,因为我在修改过程中,感觉代码一大堆,自己看着就有些吃力……另外,我还有个问题,对于这道魔王语言解释的题,我实现的是括号不嵌套的魔王语言的解释,如果魔王的语言是括号内嵌入多个括号,即一层括号嵌入一层括号,这样的话该如何解决?请指点下,谢谢!

4 楼

#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 Deal_with_uppercase(LinkQueue *after_devil, char ch);                  
//处理魔王语言中的大写字母
void Deal_with_brackets(LinkQueue *after_devil, SqStack *S, char ch);
//处理魔王语言括号内的部分
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;      //储存魔王语言转化成字母语言
    QueuePtr p;

    Input(&devil);
    Translate_to_human_lang(&after_devil, &devil);
    
    printf("Translated language:\n\n");
    p = after_devil.front->next;
    printf("%c", p->data);
    while (p != after_devil.rear){
        //打印转化后的字母语言
        p = p->next;
        printf("%c", p->data);
    }
    printf("\n\n");

    printf("Corresponding chinese language are:\n\n");
    Translate_to_chinese_lang(&after_devil, decipher);

}

void InitQueue(LinkQueue *Q){
    //构造队列,不设头节点
    Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q->front){
        //存储分配失败
        printf("No enough Memory!\n");
        exit(0);
    }

    Q->rear->next = NULL;
}

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 (e != '!');
}

void Deal_with_uppercase(LinkQueue *after_devil, char ch){
    //处理魔王语言为大写字母的情况
    if (ch == 'A'){
        EnQueue(after_devil, 's');
        EnQueue(after_devil, 'a');
        EnQueue(after_devil, 'e');
    }
    else if (ch == '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{
        //ch不是A或B
        EnQueue(after_devil, ch);
    }
}

void Deal_with_brackets(LinkQueue *after_devil, SqStack *S, char ch){
    //处理魔王语言括号内的部分
    char l;

    do{
        l = Pop(S);
        if (l != ch){
            //如果弹出的元素不是原括号内的第一个元素
            EnQueue(after_devil, ch);
        }
        if (l >= 'A' && l <= 'Z'){
            //如果弹出的是大写字母
            Deal_with_uppercase(after_devil, l);
        }
        else{
            EnQueue(after_devil, l);
        }
    }while (S->top != S->base);
}

void Translate_to_human_lang(LinkQueue *after_devil, LinkQueue *devil){
    //把魔王语言转化为字母语言
    char l, first, u = DeQueue(devil);
    SqStack S;
    InitStack(&S);
    InitQueue(after_devil);

    while (devil->front != devil->rear){
        //逐个输出魔王语言,并将其转化为字母语言储存到after_devil队列中
        if (u >= 'A' && u <= 'Z'){
            //u为大写字母,并处理大写字母
            Deal_with_uppercase(after_devil, u);
        }
        else if (u == '('){
            first = u = DeQueue(devil);
            while(u != ')'){
                //把魔王语言括号内的元素储存到栈中,实现逆序
                Push(&S, u);
                u = DeQueue(devil);
            }
            
            Deal_with_brackets(after_devil, &S, first);
        }
        else{
            //处理其他不是大写字母或括号内的字母
            EnQueue(after_devil, u);
        }
        u = DeQueue(devil);
    }
}

void Translate_to_chinese_lang(LinkQueue *after_devil, char *decipher[]){
    //把字母语言转化为汉语
    char e;
     
    do{
        e = DeQueue(after_devil);
        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("%c", e);
        }
    }while(after_devil->front != after_devil->rear);

    printf("\n");
}

5 楼

题目描述的规则没说允许嵌套……
我觉得你的缩进风格不错,如果想调整得漂亮一些,要么分文件写,要么就把每个函数内的空行去掉,函数间空行适度拉开

6 楼

谢谢!把这道题写完后突然想起如果有括号嵌套的问题该怎么办,当时感觉如果用递归似乎可以实现,但没找到合适的数据结构来储存[em10]

7 楼

对雪光风剑深表钦佩

8 楼

递归的天然搭档是堆栈。

我来回复

您尚未登录,请登录后再回复。点此登录或注册