《C语言数据结构大作业之魔王语言题》由会员分享，可在线阅读，更多相关《C语言数据结构大作业之魔王语言题（5页珍藏版）》请在金锄头文库上搜索。
1、C 语言数据结构课程设计之魔王语言一、 【问题描述】 ： 有一个魔王总是使用自己的一种非常精炼而抽象的语言讲话，没人能听得 懂，但他的语言总是可以解释成人能听得懂的语言，因为他的语言是以下两种规 则逐步抽象上去的： （1）（1）12m （2） （12n）nn11 在这两种形式中， 从左到右均表示解释。 试写一个魔王语言折解释系统，把他的 话解释成人能听得懂的话。 基本要求： 用下述两条规则实现。 设大写字母表示魔王语言的词汇；小写字母表 示人的语言词汇； 希腊字母表示可以用大写字母或小写字母代替的变量。魔王语 言可含人的词汇。 （1）BtAdA （2）Asae 二、 【基本要求】： 用下列两条
2、具体规则和上述规则形式（2）实现。设大写字母表示魔王语言， 小写字母表示人的语言词汇， 希腊字母表示可以用大写字母或小写字母代替的变 量。魔王语言可包含人的词汇， 例如： （1）BtAdA （2）Asae 三、 【选做内容】： 代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规 则，而不是吧规则固定在程序中（第二种规则只能固定在程序中）。四、 【程序设计的基本思想，原理和算法描述】：(1) 以一维数组 lan i 表示魔王语言 (2) 魔王语言由用户输入 , 初始保存在 lan i 中 (3) 魔王语言与人类语言的规则一手动输入，规则二固定在程序中 (4) 实现过程： A：初始，
3、魔王语言接收后存放在lan i 中 B：初次遍历数组，将数组中括号内的元素从左到右入栈； C：栈中栈顶元素依次出栈，依次处理栈顶元素。 D：如果栈顶元素为左括号，则flag=1 ，套用规则二；若栈顶元素为右括号，则 flag=0 ， 套用规则一。 括号内元素存入数组中， 再将数组逆置， 套用规则一输出。1：设定栈的抽象数据类型定义： ADT stack 数据对象： Dai|aiCharSet,i 1,2, ,n,n=0 数据关系： R1|ai-1,aiD,i 2, ,n 基本操作：initstack (s) 操作结果 : 构造一个空栈 s. push (s,e) 初始条件 : 栈 s 已存在
4、. 操作结果 : 在栈 s 的栈顶插入新的栈顶元素e. pop(s, e) 初始条件 : 栈 s 已存在 . 操作结果 : 删除 s 的栈顶元素 , 并以 e 返回其值 . ADT stack 2: 本程序包含四个模块 : 1) 主函数模块 . 2) 元素入栈处理模块 . 3) 翻译大写处理模块 . 4) 翻译括号内元素模块。各模块之间调用关系 : 主函数模块 元素入栈处理模块 ; 翻译模块 翻译括号内元素处理模块 ; 五、 【我的源代码】 ：#include #include #include #include #include #define OK 1 #define OVERFLOW -
5、1 #define status int #define elemtype char #define STACK_INIT_SIZE 100 #define STACKINCREAMENT 10 #define maxn 10010 typedef struct elemtype *base; elemtype *top; int stacksize; Sqstack; status Init(Sqstack *S) S-base=(elemtype *)malloc(STACK_INIT_SIZE*sizeof(elemtype); if(!S-base) exit (OVERFLOW);
6、S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK; status Pop(Sqstack *S,elemtype *e)/ 删除栈顶元素，并用e 返回其值； if(S-top=S-base) return 0; *e=*-S-top; return *e; status Push(Sqstack *S,elemtype e)/插入栈顶元素 if(S-top-S-base=S-stacksize) S-base=(elemtype *)realloc(S-base,(S-stacksize+STACKINCREAMENT)*sizeof(e
7、lemtype);if(!S-base) exit (OVERFLOW); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREAMENT; *S-top+=e; return OK; int main() Sqstack s; Init(/ 建立栈；char amaxn,bmaxn,lanmaxn,fmaxn,dmaxn; char c1,c2,c3; printf(“ 请输入规则一：n“); scanf(“%c-%s“,/printf(“%c-%sn“,c1,a); getchar(); scanf(“%c-%s“,/printf(“%c-%s
8、n“,c2,b); getchar(); int len_a=strlen(a); int len_b=strlen(b); int f_len=0; for(int i=0;i=0;i-)/将魔王语言从右往左进栈； Push( char e; int flag=0; int d_len=0; printf(“ 翻译后的语言为：“); for(int i=0;i=0;j-)/右括号占据一个空间，所以长度减二； if(j) printf(“%c%c“,c3,dj); else printf(“%c“,dj); else if(flag!=1) printf(“%c“,e); putchar(n); return 0; 三、运行结果：
