当前位置：文档库 › 魔王语言解释

魔王语言解释

数据结构课程设计文档

2.2魔王语言解释（线性）

[问题描述]

有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：

（1）α－> β1β2…βm

（2）（θδ1δ2…δn)－>θδnθδn－1…θδ1θ

在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。

[基本要求]

用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。

（1）B －> tAdA

（2）A －> sae

[测试数据]

B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae

若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。

t d s a e z g x n h

天地上一只鹅追赶下蛋恨

一：需求分析

(1)以一维数组demon[ i ]表示魔王语言．

(2)魔王语言由用户输入,初始保存在demon[ i ]中．

(3)魔王语言与人类语言对应关系固化在程序中．

(4)实现过程：

A：初始，魔王语言接收后存放在demon[ i ]中．

B：初次遍历数组，将数组中括号内的元素入栈，同时插入相应首字母；

C：再次遍历数组，将数组元素依次入队。（小写字母直接入队；大写字母经翻译成相应字符后入队；遇到括号，将栈中保存的元素依次出栈入队）在翻译过程中，如果依旧包含大写字母，则置flag为1，否则为0。

D：将队列中元素赋值给demon[ i ]。如果此时flag=1，则再次重复C过程。直至所有元素为人类语言。

E：输出demon[ i ]。此时数组中元素为对应的人类语言。注：如果程序中没有相应的对应关系，则翻译成“???”。

二：概要设计：

1：设定栈的抽象数据类型定义：

ADT stack｛

数据对象：D＝｛ai|ai∈CharSet,i＝1,2,…,n,n>=0｝

数据关系：R1＝{|ai-1,ai∈D,i＝2,…,n}

基本操作：

initstack (＆s)

操作结果:构造一个空栈s.

push (＆s,e)

初始条件:栈s已存在.

操作结果:在栈s的栈顶插入新的栈顶元素e.

pop(＆s,＆e)

初始条件:栈s已存在.

操作结果:删除s的栈顶元素,并以e返回其值.

}ADT stack

2:设定队列的抽象数据类型:

ADT queue{

数据对象：D＝｛ai|ai∈Elemset,i＝1,2,…,n,n>=0｝

数据关系：R1＝{|ai-1,ai∈D,i＝2,…,n}

基本操作：

initqueue(&q)

操作结果: 构造一个空队列q.

enqueue(&q, e)

初始条件: 队列q已存在.

操作结果: 插入元素e为q的新队尾元素.

dequeue(&q,&e)

初始条件: q为非空队列.

操作结果: 删除q的队头元素,并用e返回其值.

}ADT queue

3:本程序包含四个模块:

1)主函数模块.其中主函数为:

status main()

{

初始化栈;

初始化队列;

接收魔王语言输入到数组demon[i ];

遍历数组将括号中元素进栈;

while(数组demon[i ]中元素有大写字母)

{ 翻译排序处理后入队列;

将对列元素保存在数组demon[i ];

}

输出人类语言(数组demon[ i]);

}

2)括号内元素入栈处理模块.

tempstack(&temps)

将括号内元素入栈,依次插入首字符.

举例：(abcd)－>adacaba.

3)排序入队列模块.

sort(&s,&q)

{

遍历数组;

{

遇到小写字母,直接入队列;

遇到大写字母,翻译大写后入队列;

遇到括号,将栈中保存的元素依次出栈入队列; }

}

4)翻译大写处理模块.

spenqueue(&*q,key)

{

switch(key)

{

找到各个大写字母对应的字符串.

没有相应的则解释为’???’

}

各模块之间调用关系:

主函数模块

{

括号内元素入栈处理模块;

排序入队模块

{

翻译大写处理模块;

}

三:详细设计

1.定义全局变量

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define NULL 0

#define OVERFLOW -2

#define MAXSIZE 100

#define stack_init_size 100

#define stackincrement 10

typedef char selemtype;

typedef char qelemtype;

typedef char elemtype;

typedef int status;

char e;

char demon[MAXSIZE];

2.栈类型及其基本操作

typedef struct

{

selemtype *base;

selemtype *top;

int stacksize;

}sqstack;

status initstack (sqstack *s)

{

s->base=(selemtype *)malloc(stack_init_size*sizeof(selemtype));

if(!s->base) exit (OVERFLOW);

s->top=s->base;

s->stacksize=stack_init_size;

return OK;

}/*创建栈*/

status push (sqstack *s,selemtype e)

{

if(s->top-s->base>=s->stacksize)

{

s->base=(elemtype *) realloc(s->base,(s-

>stacksize+stackincrement)*sizeof(elemtype));

if(!s->base) exit(OVERFLOW);

s->top=s->base+s->stacksize;

s->stacksize+=stackincrement;

}

*(s->top++)=e;

return OK;

}/*入栈*/

status pop(sqstack *s,selemtype *e)

{

if(s->top==s->base) return ERROR;

*e=*(--(s->top));

return OK;

}/*出栈*/

3.队列类型及其基本操作

typedef struct qnode

{

qelemtype data;

struct qnode *next;

}qnode,*queueptr;

typedef struct

{

queueptr front;

queueptr rear;

}linkqueue;

status initqueue(linkqueue *q)

{

q->front=q->rear=(queueptr)malloc(sizeof(qnode)); if(!q->front) exit(OVERFLOW);

q->front->next=NULL;

return OK;

}/*创建队列*/

status enqueue(linkqueue *q,qelemtype e) {

queueptr p;

p=(queueptr)malloc(sizeof(qnode));

if(!p) exit(OVERFLOW);

p->data=e;

p->next=NULL;

q->rear->next=p;

q->rear=p;

return OK;

}/*入队*/

status dequeue(linkqueue *q,qelemtype *e) {

queueptr p;

if(q->front==q->rear) return ERROR;

p=q->front->next;

*e=p->data;

q->front->next=p->next;

if(q->rear==p)

{

q->rear=q->front;

}

free(p);

return OK;

}/*出队*/

4.括号内元素入栈处理函数

void tempstack(sqstack *temps)

{

int i=0;

char t;

char c;

c=demon[i ];

for(i=0;c!='#';i++)/*遍历数组*/

{

c=demon[i ];

if(c=='(')/*遇到开括号*/

{

t=demon[i+1];/*取括号中的首字母*/

push(temps,t);/*入栈*/

i++;/*指向首字母*/

{

i++;

c=demon[i ];

push(temps,c)/*第一次循环将次字母入栈*/;

push(temps,t);/*再将首字母进栈*/

}

while(c!=')');/*直到括号中元素全部进栈*/

pop(temps,&t);/*将多余进栈的首字母t出栈*/

pop(temps,&t); /*将多余进栈的’)’出栈*/

}

}/*临时栈*/

5.特殊入队函数

void spenqueue(linkqueue *q,char key)

{

int j=0;

char a[5];

switch(key) /*判断大写字母对应的字符串*/

{

case'A':strcpy(a,"sae");break;

case'B':strcpy(a,"tAdA");break;

case'C':strcpy(a,"abc");break;

case'D':strcpy(a,"def");break;

case'E':strcpy(a,"ghi");break;

case'F':strcpy(a,"klm");break;

case'H':strcpy(a,"mop");break;

default:strcpy(a,"???"); /*不能翻译的魔王语言以”???”输出*/ }

while(a[j]!='\0') /*如果数组还有字母*/

{

enqueue(q,a[j]);/*进队*/

j++;

}

}/*特殊入队*/

6.排序入队处理函数

status sort(sqstack *s,linkqueue *q)

{

qnode b;

int flag=0;/*大写字母监视哨置零*/

int i;

for(i=0;demon[ i]!='#';i++)/*遍历数组*/

{

b.data=demon[ i];

if( ('a'<=b.data&&b.data<='z') || b.data=='?') /*如果是小写字母或者’?’则直接入队*/

{

enqueue(q,b.data);

}

else

{

if('A'<=b.data&&b.data<='Z') /*如果是大写字母,则调用特殊入队函数,*/

{

spenqueue(q,b.data);

flag=1; /*发现大写字母监视哨置1*/

}

else

{

if(b.data=='(')/*如果是括号*/

{

pop(s,&e);

enqueue(q,e);

}

while(!(s->top==s->base)); /*只要栈不为空,则出栈进队*/

while (b.data!=')') /*只要还指向括号内元素,就继续往后移,保证原括号内的元素不再进栈*/

{

i++;

b.data=demon[ i];

}

return flag;

}/*排序*/

status main()

{

sqstack s1;

linkqueue q1;

int k=0;

int flag=1;

clrscr();

printf("\n\n\n\t\t\tWELCOME!\n");

printf("\t***************************************\n"); printf("\tPlease Input The Demon's Words:\n\t");

printf("!: Less Than 30 Letters: )\n\t");

printf("!: Please Stop By '#': )\n\t");

printf("***************************************\n\t"); printf("The Demon's Words:\n\t");

scanf("%s",demon);

printf("\n\t***************************************"); initstack(&s1); /*创建栈*/

initqueue(&q1); /*创建队*/

tempstack(&s1); /*调用函数*/

while (flag==1) /*如果有大写字母*/

{

k=0;

flag=sort(&s1,&q1);

while(q1.front!=q1.rear) /*重写demon[i ]*/

{

dequeue(&q1,&e);

demon[k]=e;

k++;

}

demon[k]='#';

}

demon[k]='\0';

printf("\n\tThe Human's Words:\n\t%s",demon);

printf("\n\n\t***************************************"); printf("\n\t\t\tTHANK YOU!\n\t");

printf("Please press any key to exit...");

if(getch()) exit(1);

}

}/*主函数*/

四:调试分析

1. 函数调用比较多,因而得仔细对待数值和地址的传递.

2. 由于魔王语言中’B’中仍然包含着大写字母(tAdA).所以考虑设置flag.

3. 函数数组遍历.进栈出栈.入队出队中都要牵扯指针的移动,所以要仔细考虑一循环的条件以及进栈元素的个数.

五:用户手册

1. 本程序运行环境为DOS/WINDOWS操作系统,执行文件为:魔王语言解释.exe。

2. 进入程序即显示提示信息:

WELCOME!

***************************************

Please Input The Demon's Words:

!: Less Than 30 Letters: )

!: Please Stopped By '#': )

***************************************

The Demon's Words:

等待用户输入.用户输入字符以’#’回车结束.

***************************************

The Human Words:

（翻译后的语言）

***************************************

THANK YOU!

六:测试结果

WELCOME!

***************************************

Please Input The Demon's Words:

!: Less Than 30 Letters: )

!: Please Stopped By '#': )

***************************************

The Demon's Words:

B（ehnxgz）B#

***************************************

The Human Words:

tsaedsaeezegexenehetsaedsae

***************************************

THANK YOU!

测试的数据和结果分别为:

1(要求): B（ehnxgz）B#－>tsaedsaeezegexenehetsaedsae 另外测试的数据有:

2:abcd#－>abcd ；

3:mBiM#－>mtsaedsaei??? ；

4:gcBA(oBifz)#－>gctsaedsaesaeozofoiotsaedsaeo ；

结果皆正确。

七.附录

源程序文件清单：

魔王语言解释.c //源程序文件

魔王语言解释.exe //可执行文件

魔王语言解释测试用例.doc

魔王语言解释-大数据结构课程设计

实习2、魔王语言解释一、需求分析 1. 问题描述有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没人能听的懂，但他的语言是可以逐步解释成人能懂得语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α->β1 β2 ... βn （2）(θδ1 δ2 ... δn) —>θδn θδn-1 ...θδ1 θ 在这两种形式中，从左到右均表示解释。试写一个魔王解释系统，把他的话解释成人能听懂得话。 2. 基本要求用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写或小写字母代换的变量。魔王语言可含人的词汇。（1）B—>tAdA （2）A—>sae 3. 测试数据 B（ehnxgz）B 解释成tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。 4. 实现提示将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考如何处理。应首先实现栈和队列的基本操作。二、概要设计 1、设定栈的抽象数据类型定义： ADT Stack { 数据对象：D= {a i| a i∈CharSet, i= 1,2,……n,. n≥0 } 数据关系：R1={ | a i-1,a i∈D, a i-1