《课程设计报告-魔王语言翻译.docx》由会员分享，可在线阅读，更多相关《课程设计报告-魔王语言翻译.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、合肥手浣行靠机科学与技木系课程设计报告20122013 学年第二学期2013printf (魔王语言解释成人能听懂的语言：);char e;while (S-top!= T) 栈不空e=S-elemS-top ;/e 为栈顶元素S-top; 指针后移Translation2(e);执行翻译函数(输出函数)进行转化成汉字void main ()(Stack S;定义栈对象InitStack(&S ); 初始化一个栈printf (*魔士语言解释*n);printf (魔王请说话(至多含一个括号)：n)；char str100;while (scanf (s，str) !=E0F)不停止 (int
2、 flag=0, j, m=0, n=0;for (j二strlen (str) T ; j=0; j) 从后遍历字符串 (if(strj=)如果为)(flag+; /标记加 1 n二j; 记下右括号位置)()如果为(flag+;m=j; 记下左括号位置 )if(flag=0)即用户输入的是无括号的(01(尸5宣16!1(5丘)-1打=0；/-)从后入栈(因为栈的是先进后出，所以 从后入栈)(Push(&S, strj);进栈操作Translation! (&S);直接调用翻译函数 printf (n);if(flag=2)有括号(至多一对)for (j=strlen (str)-l; jn;
3、 j) /将右括号后的字母入栈Push (&S,str j);)Push(&S, strm+l);左括号后的第一个字母入栈 for(j=m+2;j 0 8n0 5 n-1- 0810 if (flag2| |flag=l)一个开扩号,或者多于一对括号printf (input wrongnz，);一、问题分析与任务定义：【问题描述】有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能昕得懂，但他的 语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规那么由人的语言 逐步抽象上去的：。一笈用乩(2)(第2可)-助维T比。在这两种形式中，从左到右均表示解释。试写一个魔王语
4、言的解释系统，把他的话解释 成人能听得懂的话。【基本要求】用下述两条具体规那么和上述规那么形式实现。设大写字母表示魔王语言的词汇；小写 字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可 含人的词汇。(1) B tAclA.(2) A f sae【测试数据】B(ehnxgz)B 解释成 tsaedsaeezegexenehetsaedsae假设将小写字母与汉字建立下表所示的对应关系，那么魔王说的话是“天上一只鹅地上一只 鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdSaeZgXnh天地上一只鹅追赶下蛋恨【实现提示】将魔王的语言自右至左进栈，总是处理栈顶字符。
5、假设是开括号，那么逐一出栈，将字母顺 序入队列，直至闭括号出栈，并按规那么要求逐一出队列再处理后入栈。其他情形较简单，请 读者思考应如何处理。应首先实现栈和队列的基本操作。【选作内容】(1)由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。(2)代换变量的数目不限，那么在程序开始运行时首先读入一组第一种形式的规那么，而不是把规那么固定在程序中(第二种形式的规那么只能固定在程序中)。二、数据结构的选择和概要设计：本程序采用的是顺序栈。1、基本操作列表：(1)据括号的个数设一个标记。记下括号的位置。(2)根据标记来执行依次的操作。(3)没有括号，直接进队，据翻译函数2输出人的语言。(4)有括号
6、，分为括号内的和括号外的。，根据括号的位置：括号外的从右到左入栈；括 号内的从左到右入栈，并且依次插入括号内的第一个字符。据翻译函数2出栈并且翻译(5)数据类型：栈类型typedef struct声明(char elemsize;int top;Stack;2、各模块之间的关系图：三、详细设计：L基本操作函数数据元素：可以是任何类型的数据，但必须属于同一个数据对象。关系：栈中数据元素之间是线性关系。基本操作：(1)InitStack(S)操作前提：S为初始化的栈。操作结果：将S初始化为空栈。(2)ClearStack(S)操作前提：栈S已经存在。操作结果：将S置为空栈。Isempty (S)操
7、作前提：栈S已经存在。操作结果：判栈空函数，假设栈为空，那么函数为真；反之，为假。(4)IsFull(S)操作前提：栈S已经存在。操作结果：判栈满函数，假设栈为满，那么函数为真，反之，为假。(5) Push (S)操作前提：栈S已经存在。操作结果：在S的顶部插入与元素x,假设栈未满，那么将x插入栈顶位置；反之，那么返回 假，表示操作失败，否那么返回真。(6)Pop(S)操作前提：栈S已经存在。操作结果：删除栈顶元素，并用x带回该元素的值，假设栈为空，返回值为假，表示操作 失败；反之，那么返回真。(7)GetTop(S)操作前提：栈S已经存在。操作结果：取栈顶元素，但是不改变栈顶位置。void
8、InitStack (Stack *S ) 初始化栈(S-top=-l;int Push (Stack *S, char x)进栈(if(S-top=size-l) return 0; 栈满S-top+;S-elemS-top=x;return 1;)局部解决问题函数语句：1 f (f lag=0) 即用户输入的是无括号的(for (j=strlen(str)-l; j二0; j)/从后入栈(因为栈的是先进后出，所以从后入栈)(Push(&S, strj)；Translation! (&S);直接调用翻译函数printf (n)；if(flag=2)有括号(至多一对)1 (110为核心语句)(
9、for(j=strlen(str)-1; jn; j一)从后入栈(因为栈的是先进后出，所以从后入栈) (Push(&S, strj);)Push (&S, str m+1); 因为规那么(1) (。8 18 2- 5 n) 6no 8 n-b- 0 5 10 for(j=m+2;jn;j+)(Push(&S, strj);Push(&S, strm+l)；将括号的第一个元素进栈for(j=m-l; j=0; j)(Push(&S, strj);)Translation!(&S);printf (n);因为规那么(1) ( 0 8 1 8 2- 5n) - 0 5no 6 n-l- e 8 1
10、0 if (flag2| |flag=l)一个开扩号，或者多于一对括号(printf (input wrongn，z);)2 .用伪码给出主程序的主要处理过程Main ()求出flag数；if (flag-0)(队列模块一一实现队列的抽象数据类型；翻译函数1;if(flag=2)(栈模块一一实现栈的抽象数据类型；翻译函数1；)if(flag=l|flag2)(输入错误！四、上机调试过程：1、进入程序后即显示用户界面4-1：* 魔王语言解考 * 魔王请说话(至多含一个括号)：图4-1用户界面2、依次输入AB、BehnxgzB得到下列图4-2所示：充*鹰干语 g 解”辛克XKXNXXMNMXMta
11、w (至多含一个括号)：AB腐王语言解释成人能听懂的语管上一只耦天上一只跳上一只耦BehnxgzB王聒解释成人能听懂的悟等天上一只觎上一只嬲恨蛋下赶追天上一只榭也上一只图4-2没有括号情况3、再次输入B(ehnxgz)B得到下列图4-3所示:AB魔王语言解释成人能听懂的语等上一只科天上一只翘地上一只相BehnxgzB原王语言解释成人能听懂的语言沃上一只鹅地上一只鹅雕蛋下赶追天上一只鹅地上一只B input wrong (ehnxgz input wrong ,魔王语言解释成人能听懂的语言:鹅追鹅赶鹅下鹅蛋鹅恨鹅图4-4括号不匹配情况五.测试结果及其分析：1 .假设是括号外的从左到右入栈，并进行
12、翻译，那么出来的运行结果是反着的，并未到达要 求的结果。所以进行调试，发现应该从右到左入栈，根据出栈的顺序，先进后出，正好可以 到达相应的结果。2 .括号内的字符的入栈错误。本来只是将括号内的字符也是据1从右到左入栈。并且循 环插入括号内的第一个字符。发现结果又是反的。据调试，发现括号内的字符应该是从左到 右入栈，正好符合规那么1,结果未相反。3 .将括号内的第一个字符按照循环，进一个字符，再插一个括号内的第一个字符。发现 结果与规那么1不符，所以据调试，应在循环外先插入一个括号内的第一个字符，后再进行以 上的循环,这样输出的结果与规那么1相符,并且第一个输出的不会少了括号内的第一个字符, 也
13、不会重复第一个字符的输出。4 .在翻译函数2中，即为输出函数中，原来一直用if,但是据题意来看，if很多，导 致许多不必要低级编译错误，所以改为switch。原来一直没怎么用过switch,据这次机会 真的锻炼了许多。六、用户使用说明：1、运行程序，进入用户界面；2、根据提示输入魔王说的语言。注意：只能按要求输入以下字母及括号，字母有A、B、 t、d、s、a e、z、g、x、n、h；3、输入魔王说的语言后，按Enter键输出人能听得懂的语言。七、参考文献：1王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。2陈锐.零基础学编程.北京：机械工业出版社，2010年1月。3汪沁，奚
14、李峰,数据结构.北京：清华大学出版社，2009年9月。4严蔚敏，吴伟民.数据结构(c语言版).北京：清华大学出版社，2004年2月八、附录：源程序：include #include#includettdefine FALSE 0ttdefine TRUE 1#define size 300typedef struct 顺序栈定义(char elemsize;int top;Stack;void InitStack(Stack *S )初始化栈(S-top=-l;int Push (Stack *S, char x)进栈(if(S-top=size-l) return 0; 栈满S-top+;S
15、-elemS-top=x;return 1;void Translation2(char e)/翻译函数2 (即为输出函数)，栈的参数e为传递参数switch （e）（case，B:printf （天上一只鹅地上一只鹅）；规那么 break;case A:printf （上一只鹅）；规那么break;case，t:printf （天）;break;case，s:printf （上）;break;case，a:printf （一只）;break;case，e :printf （鹅”）;break;case，h:printf （恨）;break;case，n :printf （蛋）;break;case x:printf （下）;break;case g :printf （赶）；break;case，z :printf （追）;break;case，d:printf （地）；break; 以上为对应的汉字void Translation! （Stack *S）