利用栈实现表达式求解

理学院课程设计说明书课程名称:数据结构与算法A设计实践课程代码:6015059题目二:利用栈实现表达式求解开始时间:2015年12月28日完成时间:2016年01月10日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日西华大学理学院课程设计说明书数据结构与算法A设计实践任务书学院名称：理学院课程代码：_6015059________专业：信科年级：2012一、设计题目利用栈实现表达式求解（限最多1人完成）二、主要内容使用栈来解决表达式中的求解优先问题三、具体要求及提交的材料利用教材3.2.5节的理论实现表达式求解。（1）只考虑+、-、*、/四种数学运算（2）只考虑圆括号（）参与运算测试数据及测试结果请在上交的资料中写明；必须上机调试通过按《数据结构课程设计大纲》中的要求完成课程设计报告格式。设计结束后，每个学生必须上交的材料有：1《课程设计报告》打印稿一份2．课程设计的源代码电子文档一份四、主要技术路线提示根据运算符号的优先级来决定当前符号是否入栈；注意考虑多重括号匹配的问题。五、进度安排共计两周时间，建议进度安排如下：1．选题，应该在上机实验之前完成2.需求分析、概要设计可分配4学时完成2．详细设计可分配4学时4.调试和分析可分配10学时。2学时的机动，可提前安排部分提前结束任务的学生答辩六、推荐参考资料1.冯博琴等编著，《软件技术基础》（修改版），西安交通大学出版社，19972.严蔚敏等著，《数据结构》，清华大学出版社，20033.李芸芳等著，《软件技术基础》（第二版），清华大学出版社，20004.徐孝凯等著，《数据结构（C语言描述）》，清华大学出版社，2004指导教师签名日期年月日系主任审核日期年月日西华大学理学院课程设计说明书目录摘要...................................................................11引言..................................................................22系统分析................................................................32.1功能要求............................................................32.1.1总体要求........................................................32.1.2本人所做模块.....................................................32.2数据需求............................................................33详细设计与实现..........................................................33.1设计思路............................................................33.2整体设计方案........................................................43.3主函数..............................................................53.4编码................................................................54．系统测试：............................................................114.1设计测试数据.......................................................114.2测试结果及分析.....................................................12结论...................................................................13致谢...................................................................15参考文献.................................................................16附录.....................................................................17利用栈实现表达式求解1摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，数据结构与算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。数据结构与算法旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。栈是一种重要的线性结构，栈可以用作数制转换、括号匹配的检验、行编辑程序等等问题中。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它是和线性表大不相同的两类重要的抽象数据类型。栈实限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。栈又称为后进先出的线性表。这次的课程设计是利用栈实现表达式求解，要求只考虑+、-、*、/四种数学运算还有只考虑圆括号参与运算。关键词：数据结构与算法，栈，表达式求解，最优西华大学理学院课程设计说明书21引言1.1问题的提出栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底,最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和《数据结构与算法》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于用栈实现表达式求解，栈是计算机中常用的一种数据结构，具有广泛的使用。利用栈的性质及其操作原理编写一个使用栈计算表达式的程序有助于更好的掌握栈的使用规则和原理应用。1.2C语言C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。1.3C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年DennisM.Ritchie发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。1978年BrianW.Kernighian和DennisM.Ritchie出版了名著《TheCProgrammingLanguage》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.4任务与分析本程序用于解决一个可以带括号的表达式求值的问题，要运用到栈，而且会用到一种简单直观，广为使用的算法，通常称为“算符优先法”。进行表达式求值首先要了解利用栈实现表达式求解3算术四则运算的规则。即：(1）先乘除，后加减；（2）从左算到右；（3）先括号内后括号外；算符优先法根据这个算符优先关系的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由操作数、运算符和界限符组成。2系统分析2.1功能要求2.1.1总体要求利用教材3.2.5节的理论实现表达式求解。（1）只考虑+、-、*、/四种数学运算（2）只考虑圆括号（）参与运算2.1.2本人所做模块根据这次课程设计题目的要求，将这次任务分为了几个小的模块，具体模块的功能如下：Push(&S,e)：入栈函数模块Pop(&S,&e)：出栈函数模块In(Test,*TestOp)：判断是否为运算符Operate(a,theta,b)：根据theta对a、b进行四则运算操作ReturnOpOrd(op,*TestOp)：若TestOp为运算符，则返回此运算符在数组的下标precede(Aop,Bop)：根据运算符优先级表返回Aop与Bop之间的优先级EvaluateExpression()：用运算符优先级对算术表达式求值最后，通过主函数对以上几个函数的调用，实现该系统的功能。2.2数据需求输入一个表达式，利用优先级表对表达式求值。3详细设计与实现3.1设计思路为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。在输入表达式的最后输西华大学理学院课程设计说明书4入‘#’，设定‘#’的优先级最低，代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。3.2整体设计方案图1调用关系图通过以上的关系图，可以从中看出系统的流程以及函数之间的调用关系。EvaluateExpressiontmainInPushprecedePopReturnOpOrdOperate输出利用栈实现表达式求解53.3主函数//==========通过该函数对其他函数的调用，实现系统功能int_tmain(intargc,_TCHAR*argv[]){intnResult,n;while(1){manu();coutendl;cout请输入选项：;cinn;switch(n){case1:puts(**************************************************);puts(请输入一个运算式，以#结尾：);printf(\n);nResult=EvaluateExpression();printf(\n);printf(运算结果是：%d\n,nResult);printf(\n);break;case0:exit(0);break;}}return0;}西华大学理学院课程设计说明书63.4编码//==========预定义#defineok1#defineerror0#defineoverflow-1#defineOPSETSIZE7#defineSTACKINCREMENT100#defineSTACK_INIT_SIZE10//==========定义顺序栈结构模板templatetypenameTstructSqStack{T*top;T*base;intstacksize;};//==========初始化栈函数模板templatetypenameT1,typenameT2//传进来的T1，T2生成对应的类StatusInitStack