利用栈实现表达式求解

1、理学院课程设计说明书课 程 名 称: 数据结构与算法A设计实践课 程 代 码: 6015059 题 目 二: 利用栈实现表达式求解 开 始 时 间: 2015 年 12 月 28 日完 成 时 间: 2016 年 01 月 10 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日西华大学理学院课程设计说明书数据结构与算法A设计实践任务书学院名称： 理学院 课程代码：_6015059_专业： 信科 年级： 2012 一、设计题目 利用栈实现表达式求解（限最多1人完成）二、主要内容使用栈来解决表达式中的求解

2、优先问题三、具体要求及提交的材料利用教材3.2.5节的理论实现表达式求解。 （1）只考虑+、-、*、/四种数学运算（2）只考虑圆括号（ ）参与运算测试数据及测试结果请在上交的资料中写明；必须上机调试通过l按数据结构课程设计大纲中的要求完成课程设计报告格式。 设计结束后，每个学生必须上交的材料有：1 课程设计报告打印稿一份 2课程设计的源代码电子文档一份四、主要技术路线提示根据运算符号的优先级来决定当前符号是否入栈；注意考虑多重括号匹配的问题。五、进度安排共计两周时间，建议进度安排如下：1 选题，应该在上机实验之前完成 2. 需求分析、概要设计可分配4学时完成2 详细设计可分配4学时 4. 调试

3、和分析可分配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主函

4、数53.4编码54系统测试：114.1设计测试数据114.2测试结果及分析12结 论13致 谢15参考文献16附录17利用栈实现表达式求解摘 要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，数据结构与算法的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。数据结构与算法旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。栈是一种重要的线性结构，栈可以用作数制转换、括号匹配的检验、行编辑程序等等问题中。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的

5、子集，它是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它是和线性表大不相同的两类重要的抽象数据类型。栈实限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。栈又称为后进先出的线性表。这次的课程设计是利用栈实现表达式求解，要求只考虑+、-、*、/四种数学运算还有只考虑圆括号参与运算。关键词：数据结构与算法， 栈， 表达式求解，最优1 引 言 1.1问题的提出栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底,最后的数据在栈

6、顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据结构课程设计是重要地实践性教学环节。在进行了程序设计语言课和 数据结构与算法课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。本课程设计是数据结构中的一个关于用栈实现表达式求解，栈是计算机中常用的一种数据结构，具有广泛的使用。利用栈的性质及其操作原理编写

7、一个使用栈计算表达式的程序有助于更好的掌握栈的使用规则和原理应用。1.2 C语言C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。1.3 C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。1978年Brian W.K

8、ernighian和Dennis M.Ritchie出版了名著The C Programming Language，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.4任务与分析本程序用于解决一个可以带括号的表达式求值的问题，要运用到栈，而且会用到一种简单直观，广为使用的算法，通常称为“算符优先法”。进行表达式求值首先要了解算术四则运算的规则。即：(1）先乘除，后加减；（2）从左算到右；（3）先括号内后括号外；算符优先法根据这个算符优先关系的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由操作数、运算符和界限符组成。2 系统分析2.1功能要求2.1.1 总体要求利用教材3.

9、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之间的优先级Evalua

10、teExpression() ：用运算符优先级对算术表达式求值最后，通过主函数对以上几个函数的调用，实现该系统的功能。2.2 数据需求输入一个表达式，利用优先级表对表达式求值。3详细设计与实现3.1设计思路为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。在输入表达式的最后输入#，设定#的优先级最低，代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算

11、符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。3.2整体设计方案 ReturnOpOrdtmainPopprecedePushInEvaluateExpressionOperate输出图1调用关系图通过以上的关系图，可以从中看出系统的流程以及函数之间的调用关系。3.3主函数/=通过该函数对其他函数的调用，实现系统功能int _tmain(int argc, _TCHAR* argv)int nResult,n;while(1)manu();coutendl;coutn;swi

12、tch(n)case 1:puts ( * ); puts ( 请输入一个运算式，以#结尾： );printf(n);nResult = EvaluateExpression();printf(n);printf ( 运算结果是：%dn, nResult );printf(n);break;case 0:exit(0);break;return 0;3.4编码 /=预定义 #define ok 1 #define error 0 #define overflow -1#define OPSETSIZE 7#define STACKINCREMENT 100#define STACK_INIT_

13、SIZE 10/=定义顺序栈结构模板template struct SqStackT *top; T *base;int stacksize; /=初始化栈函数模板template /传进来的 T1，T2生成对应的类Status InitStack(T1 &S)S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return ok;/=入栈函数模板template Status Push(T1 &S,T2 e)if(

14、S.top-S.base=S.stacksize)S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return ok; /=出栈函数模板template Status Pop(T1 &S,T2 &e)if(S.top=S.base) return error;e=*-S.top;return ok; /=获取栈顶元素模板temp

15、late T2 GetTop(T1 S)if(S.top=S.base)return error;else return *(S.top-1);/=判断是否为运算符typedef int Status;Status In(char Test,char* TestOp) bool Find=false; for (int i=0; i, /*-*/, /*/, /*/*/, /*(*/, , /*#*/, ,=, ; /=对两操作数进行运算float Operate(float a,unsigned char theta, float b) switch(theta) case +: retur

16、n a+b;case -: return a-b;case *: return a*b;case /: return a/b;default : return 0; /运算 /=求解表达式float EvaluateExpression() / 算术表达式求值的算符优先算法。 / 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。SqStack OPTR; / 运算符栈，字符元素 SqStack OPND; / 运算数栈，实数元素 char TempData20; float Data,a,b; char theta,c,x,Dr2; InitStackSqStack,ch

17、ar (OPTR); Push (OPTR, #); InitStack SqStack,float(OPND); strcpy(TempData,0);/将TempData置为空 c=getchar(); while (c!= # | GetTopSqStack,char(OPTR)!= #) if (!In(c, OPSET) Dr0=c;Dr1=0;/存放单个数strcat(TempData,Dr);/将单个数连到TempData中，形成字符串c=getchar();if(In(c,OPSET)/如果遇到运算符，则将字符串TempData转换成实数，入栈，并重新置空 Data=(floa

18、t)atof(TempData); Push(OPND, Data); strcpy(TempData,0); else / 是运算符则进栈switch (precede(GetTopSqStack,char(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch / while return GetTopSqStack,float(OPND); / EvaluateExpression 4系统测试：运

19、行程序，显示系统主界面，如图2所示：图2 界面显示4.1设计测试数据输入表达式以#结尾，如图3所示：图3 输入表达式4.2测试结果及分析按erter显示结果，如图4所示：图4 结果显示分析：程序写出来后，也调试了没有错误，但是测试的时候有时能出来结果，但是有时候什么反应也没有，问同学也不能找出错在哪里，很无奈，不知道错在哪里就根本不知道怎么改，但是我觉得程序应该没有错误，后来在一次无意的测试中发现调试不出的情况中在键入数字时，测试界面底部有出现此字符“半：”而且括号也是中文环境下的括号，经过反复测试知道在键入表达式时应该保证是在英文环境下，才能出现结果。结 论 课程设计做完了，刚看题目还觉得没

20、有什么问题，可是这正做了才知道问题大了。细节等各方面没有考虑到的问题都出现了。做课程设计的过程就是一个不断调试不断改进程序的过程。经过学习，加上自己课外的时间，使我对C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，对C语言学习平时只是马马虎虎的过去了，真正自己去解决实际问题的时候才会发现自己学的多么糟糕，通过课程设计对自己的编程能力也有所提高；再有对C语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到

21、学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注重实践操作能力的培养，无论学习什么，亲自动手去做了才能得到最深刻的体会。致 谢本次课程设计能够顺利完成，首先感谢我的老师，老师在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。第二，我要感谢我的数据结构老师，在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。我的同学也对我进行了一系列的帮助，没有他们，也许就难以发现一些潜在的错误，在此表示感谢。参考文献1严蔚敏、吴伟民.

22、数据结构（C语言版）.清华大学出版社.20022殷人昆等.数据结构（C+版）.清华大学出版.20013金远平.数据结构（C+描述）.清华大学出版社.20054许卓群等.数据结构与算法.高等教育出版社.2004附录#include StdAfx.h#include#include #include #include#include/=调用库函数#define ok 1 #define error 0 #define overflow -1#define OPSETSIZE 7#define STACKINCREMENT 100#define STACK_INIT_SIZE 10/=预定义temp

23、late struct SqStackT *top; T *base;int stacksize;/=顺序栈结构模板typedef int Status;template /传进来的 T1，T2生成对应的类Status InitStack(T1 &S)S.base=(T2 *)malloc(STACK_INIT_SIZE*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return ok;/=初始化栈函数模板template Status Push(T1 &S,T2 e)if(S.t

24、op-S.base=S.stacksize)S.base=(T2 *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2);if(!S.base) exit (overflow);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return ok;/=入栈函数模板template Status Pop(T1 &S,T2 &e)if(S.top=S.base) return error;e=*-S.top;return ok;/=出栈函数模板template T2

25、 GetTop(T1 S)if(S.top=S.base)return error;else return *(S.top-1);/=/获取栈顶元素模板unsigned char Prior77 = / 运算符优先级表 / + - * / ( ) # /*+*/, /*-*/, /*/, /*/*/, /*(*/, , /*#*/, ,=, ; /= 运算符优先级Status In(char Test,char* TestOp) bool Find=false; for (int i=0; i OPSETSIZE; i+) if (Test = TestOpi) Find= true; ret

26、urn Find;/=判断是否为运算符float Operate(float a,unsigned char theta, float b) switch(theta) case +: return a+b;case -: return a-b;case *: return a*b;case /: return a/b;default : return 0; /=对两操作数进行运算char OPSETOPSETSIZE=+,-,*,/,(,),#; int ReturnOpOrd(char op,char* TestOp) int i; for(i=0; i OPSETSIZE; i+) if

27、 (op = TestOpi) return i; return 0;/=返回运算符的下标char precede(char Aop, char Bop) return PriorReturnOpOrd(Aop,OPSET)ReturnOpOrd(Bop,OPSET);/ReturnOpOrd和precede组合，/=判断运算符优先级float EvaluateExpression() / 算术表达式求值的算符优先算法。 / 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。SqStack OPTR; / 运算符栈，字符元素 SqStack OPND; / 运算数栈，实数元素 char TempData20; float Data,a,b; char theta,c,x,Dr2; InitStackSqStack,char (OPTR); Push (OPTR, #); InitStack SqStack,float(OPND); strcpy(TempData,0);/将TempData置为空 c=