数据结构实训表达式翻译.docx

《数据结构实训表达式翻译.docx》由会员分享，可在线阅读，更多相关《数据结构实训表达式翻译.docx（23页珍藏版）》请在三一办公上搜索。

1、数据结构课程设计报告设计任务书课题名称表达式翻译设计 目的通过一周的课程设计，实现利用顺序栈解决表达式翻译问题的方法，达到 巩固理论知识、锻炼实践能力、构建合理知识结构的目的。实验 环境Windows2000以上操作系统Visual C+6.0以上编译环境任务要求1. 搜集表达式翻译问题方面的资料；2. 编写代码，实现中缀表达式翻译成后缀表达式；3. 撰写课程设计报告；4. 参加答辩；工作进度计划序号起止日期工作内容1234指导教师：年_月日注意：1. 任务书格式参照“任务书范例”执行。2. 范例中的红色文字应根据你所选择的具体课题，修改为对应的内容。.范例中的其它内容不变。摘要:后缀表达式被

2、广泛应用于编译原理中，原因是后缀表达式有一个其他的算法 不能比拟的优点拆括号。标准的表达式如“A+B”，在数学上学名叫中缀表 达式，原因是运算符号在两个运算对象的中间。相对应的还有前缀表达式，如：“+ - A * B C D”，转换成中缀表达式为：“A - B * C + D” ；后缀表达 式，比如前所述的中缀表达式转换为后缀表达式为：“ A B C * - D +”。后 缀表达式的优点是显而易见的，编译器在处理时候按照从左至右的顺序读取后缀 表达式，遇到运算对象直接压入堆栈，遇到运算符就从堆栈提取后进的两个对象 进行计算，这个过程正好符合了计算机计算的原理。后缀表达式比前缀表达式更 加易于转

3、换，并且它的最左面一定为数字，这一点在实际编程的时候就会体会到 它的好处了。后缀表达式有一个更大的优点，就是拆括号，根据运算符的级别将 中缀表达式转换成后缀表达式后，运算顺序就已经替代了运算符的级别，这样也 避免了括号提高运算级别的特殊处理。关键字：顺序栈；优先级；中缀表达式；后缀表达式1需求分析11.1任务要求11.2课程设计思想11.3运行环境12概要设计12.1总体功能结构12.2数据结构设计22.3程序原理23详细设计和实现33.1模块功能33.2算法原理43.3流程图114调试与操作说明12总结15致谢16参考文献17指导教师评语181需求分析1.1任务要求本次的课程设计实践周，我做

4、的课题是表达式翻译。此次课程设计的任务是 收集一些有关中缀表达式翻译成后缀表达式知识的资料，还有括号匹配方面的资 料。编写完整程序，将中缀表达式翻译成后缀表达式。认真主动完成课程设计的 要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能 力，充分利用时间，安排好课程设计的时间计划，设计程序并调试。在课程设计 周，主要是进行课程设计的答辩工作，期间也继续进行的调试与完善工作，上机 时数通常为1215小时，参加答辩。1.2课程设计思想一般来说，课程设计要比教学实验复杂一些，涉及的深度广些，而且更加实 用一些。其主要目的是通过课程设计的综合训练，培养学生分析解决实际问题和 编程等

5、实际动手能力，最终目标是想通过这种形式，帮助学生系统掌握数据结构 这门课程的主要内容，使老师更好的完成教学任务。数据结构是一门涉及多门课 程的课程，难度较大，需要较好的C/C+语言的程序设计和调试能力，如果学生 能够按照要求，从时间和精力上保证完全的投入，相信能够有很大的收获，几分 投入几分收获。1.3运行环境Windows2000以上操作系统、Visual C+6.0以上编译环境。2概要设计21总体功能结构编写一个完整的程序，将中缀表达式翻译成后缀表达式。表达式由操作数（变 量）、操作（运算符）以及小括弧（”和“）”组成，其中：操作包括算术运算、关 系运算和逻辑运算三类；操作数应能够识别但个

6、字符或由字母和数字任意多个字 符构成；能够识别出简单的错误，如括弧不匹配。设计一个顺序栈类SeqStack，作为程序的头文件SeqStack.h。再设计四个函数：栈内优先级函数isp(),栈外优先级函数icp(),表达式检查函数ExpIsCorrect()和表达式转换函数postfix()。2.2数据结构设计利用一个顺序栈可以实现将中缀表达式转换为后缀表达式，也能实现对括号 是否匹配进行检测。用一个字符型数组存放从键盘输入的中缀表达式，经运行后 由屏幕输出转化后的后缀表达式。2.3程序原理栈(stack)是最常用和最重要的数据结构。局部变量是放在栈中的，表达式 的优先级处理也是基于栈来实现的，

7、函数调用时的参数传递和函数值的返回都是 由栈来实现的。栈是限制在表的一端进行插入和删除的线性表(即一维数组)。 允许插入删除的一端为栈顶，另一固定端为栈底。当表中没有元素时称为空栈。 如图2-1所示，栈中有三个元素，进栈的顺序是a、b、c，当需要出栈时其顺序 为c、b、a。所以栈又称为后进先出的线性表(Last In First Out)，简称LIFO表。在日常生活中，有很多后进先出的例子。在程序设计中，常常需要使得与 保存数据时相反顺序来使用这些数据，这时就需要用一个栈来实现。对于栈，常做的基本运算有：(1)栈初始化：Init_Stack(s)初始条件：栈s不存在操作结果：构造了一个空栈。(

8、2) 判断栈空：Empty_Stack(s)初始条件:栈s已存在操作结果：若栈s为空栈返回为1，否则返回为0.(3) 入栈：Push_Stack(s,x)初始条件：栈s已存在操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生 变化。(4) 出栈：Pop_Stack(s)初始条件：栈s存在且非空操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。(5) 读栈顶元素：Top_Stack(s)初始条件：栈s存在且非空操作结果：栈顶元素作为结果返回，栈不变化。栈可以用顺序表实现，称为顺序栈；也可以用链表实现，称为链栈。顺序栈和链 栈的逻辑功能一样。顺序栈必须先开一定大小的

9、内存空间，执行起来简单并且速 度快，但可能溢出；链栈的内存空间随用随开，不会溢出；但执行复杂(不断地 动态分配)且速度慢。3详细设计和实现3.1模块功能定义一个顺序栈类SeqStack，首先构造一个空栈，包含的操作有进栈Push()， 出栈Pop()，取栈顶元素GetTop()，判栈空否NotEmpty()。利用这个顺序栈对中 缀表达式进行检测，若出错(主要为括号比匹配)，给出出错提示；否则，将中 缀表达式转换为后缀表达式。表达式检测函数ExpIsCorrect()，实现对表达式中的括号进行匹配检验。算 术表达式中右括号和左括号匹配的次序正好符合后到括号要最先被匹配的“后进 先出”栈操作特点，

10、因此可以借助一个栈来进行判断。表达式转换函数postfix(),当表达式正确时，利用此函数将中缀表达式转换 成对应的后缀表达式。将中缀表达式转换成后缀表达式过程中，要注意的是” 无论入栈中级别为何，直接入栈，在遇到“)”时候，找到最后进入的(”，并 把(”前面所有的符号都压入出栈。由于在表达式转换过程中，需要比较新读入元素与当前栈顶元素的优先级， 所以，需要定义两个优先级函数：栈外优先级函数icp()和栈内优先级函数isp()。 3.2算法原理栈的抽象数据类型有两种典型的存储表示：基于数组的存储表示和基于链表 的存储表示。基于数组的存储表示实现的栈称为顺序栈，基于链表的存储表示实 现的栈称为链

11、栈。顺序栈可以采用顺序表作为其存储表示，为此，可以在顺序栈的声明中用顺 序表定义它的存储空间。本次课程设计中，实用一维数组作为栈的存储空间。存 放栈元素的数组的头指针为*、，该数组的最大允许存放元素个数为maxsize，当 前栈顶位置由数组下标指针top指示。如果栈不空时，s0是栈中第一个元素。顺序栈的类定义class SeqStackpublic:SeqStack()top=0; 构造一个空栈SeqStack()void Push(const char x);char Pop();char GetTop()const;bool NotEmpty()constreturn(top!=0);pr

12、ivate:char smaxsize;int top; top指示的是最后加入的元素的存储位置。在实现进栈操作时，应先判断栈是否 已满。栈的最后允许存放位置为maxsize，如果栈顶指针top=maxsize，则说明 栈中所有位置均已使用，栈已满。这时若再有新元素进栈，将发生溢出，程序转 入溢出处理。如果topmaxsize，则先让栈顶指针进1，指到当前可加入新元素 的位置，再按栈顶指针所指位置将新元素插入。这个新插入的元素将成为新的栈 顶元素。另一个极端情况出现在栈底：如果在退栈时发现是空栈，即top=0，则退 栈操作将执行栈空处理。栈空处理一般不是出错处理，而是使用这个栈的算法结 束时需

13、要执行的处理。若当前topN0，则可将栈顶指针减1，等于栈顶退回到次 栈顶位置。栈的成员函数的实现void SeqStack:Push(const char x)if(top=maxsize)cout栈已满endl;exit(0);stop=x; 先存储 x top+; 然后 top 加 1char SeqStack:Pop()if(top=0)cout栈已空endl;exit(0);top-; /top 先减 1return stop; 然后去元素返回char SeqStack:GetTop()const 取栈顶数据元素if(top=0)cout栈已空endl;exit(0);return

14、stop-1; 返回当前栈顶元素举例说明，在一个字符串“(a*(b+c)-d)”中位置1和位置4有左括号“(七 位置8和位置11有右括号“)”。位置1的左括号匹配位置11的右括号，位置4 的左括号匹配位置8的右括号。而对于字符串(a+b)(”，位置6的右括号没 有可匹配的左括号，位置7的左括号没有可匹配的右括号。我们的目的是建立一个算法，输入一个字符串，输出括号匹配的信息。算法思想：算术表达式中右括号和左括号匹配的次序正好符合后到括号要最 先被匹配的“后进先出”栈操作特点，因此可以借助一个栈来进行判断。括号匹配共有四种情况：(1) 左、右括号配对次序不正确；(2) 右括号多于左括号；(3) 左

15、括号多于右括号；(4) 左、右括号匹配正确。具体方法是：顺序扫描算术表达式(表现为一个字符串)，当遇到三种类型 的左括号时，让该括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶括 号是否与之匹配，若匹配，则退栈，继续进行判断；若当前栈顶括号与当前扫描 的括号不相同，则左、右括号配对次序不正确；若字符串当前为某种类型左括号 而栈已空，则右括号多于左括号；字符串循环扫描结束时，若栈非空(即粘中尚 有某种类型左括号)，则说明左括号多于右括号；否则，左、右括号匹配正确。函数设计如下：void ExpIsCorrect(char exp,int n) 判断有n个字符串exp左、右括号是否配对正确Se

16、qStack myStack; 定义顺序栈类对象myStackint i;for(i=0;in;i+)if(expi=()myStack.Push(expi); /入栈else if(expi=)&myStack.NotEmpty()&myStack.GetTop()=() myStack.Pop(); 出栈else if(expi=)&myStack.NotEmpty()&myStack.GetTop()!=()cout左右括号配对次序不正确！请检查表达式endl;return;else if(expi=)&!myStack.NotEmpty()cout右括号多于左括号！请检查表达式endl

17、;return;if(myStack.NotEmpty()cout左括号多于右括号！请检查表达式endl;elsecout表达式正确，请再输入上式(以#结束)isp(op)，令ch进栈，读入下一个字符ch。若icp(ch)isp(op)，退栈并输出。若icp(ch)=isp(op)，退栈但不输出，若退出的是(号读入下一个字 符ch。 算法结束，输出序列即为所需的后缀表达式。例如，给定中缀表达式为A+B*(C-D)-E/F，应当转换成ABCD-*+EF/-，按上述算法应执行的转换过程(包括栈的变化和输出)如图3-1所示。止 步扫描项项类型动作栈的变化输出0#进栈#1A操作数#A2+操作符isp(

18、#)icp(+)，进栈# +A3B操作数# +A B4*操作符isp(+)icp(*)，进栈# + *A B5(操作符isp(*)icp()，进栈# + * (A B6C操作数# + * (A B C7-操作符isp()icp()，退栈# + *(A B C D -(=)，退栈# + *A B C D -10-操作符isp(*)icp(-)，退栈# +A B C D- *isp(+)icp(-)，退栈#A B C D - * +isp(#)icp(-)，进栈# -A B C D- * +11E操作数# -A B C D - * + E12/操作符isp(-)icp(#)，退栈# -A B C

19、D - * + E F /isp(-)icp(#)，退栈#A B C D - * + E F / -结束图3-1利用栈的转换过程中缀表达式转换成后缀表达式的算法void postfix() 把中缀表示转换成后缀表示并输出之SeqStack s; 定义栈的对象s char ch=#;s.Push(ch); 栈底放了一个 #cin.get(ch); 读入一个字符while(s.NotEmpty()=true&ch!=#) 连续处理if(isdigit(ch) 是操作数，输出之coutch;cin.get(ch);elseif(isp(s.GetTop()icp(ch) 新输入操作符优先级低 cou

20、ts.Pop(); 退栈并输出elseif(s.Pop()=()cin.get(ch);couts.Pop();coutendl;该算法对输入表达式只进行一次自左向右的扫描，对每个操作数只执行一次 输出，其执行时间为0（1）。对每一个操作符，执行进栈和退栈各一次，其时间 也为0（1）。若设表达式中符号的总数为n，则总的执行时间复杂度为O（n）。栈内优先级算法int isp（char x） 栈内优先级switch（x）case#:return 0;break;case（:return 1;break;case/:case*:return 5;break;case+:case-:return 3;

21、break;case):return 6;break;栈外优先级算法int icp(char x) 栈外优先级switch(x)case#:return 0;break;case(:return 6;break;case/:case*:return 4;break;case+:case-:return 2;break;case):return 1;break;3.3流程图4调试与操作说明运行后的初始界面如图4-1所示此时表达式已被检测为正确，则将它转换成后缀表达式，结果如图4-3所示输入山 不结束，在输入一个错误的中缀表达式，如图4-4所示图4-4参考文献1殷人昆，陶永雷等编著.数据结构用面向

22、对象方法与C+语言描述.北 京：清华大学出版社，19972徐孝凯编著.数据结构实用教程（C/C+描述）.北京：清华大学出版社， 19993朱站立编.数据结构一一使用C+语言.先西安：西安电子科技大学出版社， 20014陈慧南编.数据结构一一使用C+语言描述.南京：东南大学出版社，20015王晓东编.数据结构与算法设计.北京：电子工业出版社，2002指导教师评语学号姓名班级选题 名称表达式翻译序号评价内容权重（）得分1考勤记录、学习态度、工作作风与表现。52自学情况：上网检索机时数、文献阅读情况（笔记）。103论文选题是否先进，是否具有前沿性或前瞻性。54成果验收：是否完成设计任务；能否运行、可操作性 如何等。205报告的格式规范程度、是否图文并茂、语言规 范及流畅程度；主题是否鲜明、重心是否突出、 论述是否充分、结论是否正确；是否提出了自 己的独到见解。306文献引用是否合理、充分、真实。57答辩情况：自我陈述、回答问题的正确性、用语准确 性、逻辑思维、是否具有独到见解等。25合计指导教师（签章）：年月日