算数计算表达式沈明明200911120.doc

数据结构课程设计实验报告黑龙江大学数据结构课程设计实验报告学 院软件学院年 级2009级专 业软件工程学 号200911120姓 名沈明明日 期2012.12.25成 绩黑龙江大学计算机科学技术学院黑龙江大学软件学院1. 算数运算表达式问题描述及分析【问题描述】以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值【基本要求】自己设计界面，使用适当的数据结构对运算符、操作作数进行处理。【问题分析】一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为、-、/，用表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。2概要设计2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即 topbase 可作为栈空的标记，每当插入新的栈顶元素时，指针 top 增 1，删除栈顶元素时，指针 top 减 1。2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为 OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进 OPND 栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕。功能模块及数据结构的描述（1） 实现加、减、乘、除、功能，可以区分运算符优先级关系。2. 主要算法流程描述3. 主要算法流程描述自定义函数实现菜单功能void main()elemtype m=0,result;Sqstack opnd0;Sqstack1 optr0;Linklist opnd; /操作数栈Linklist1 optr; /操作符栈opnd=&opnd0;optr=&optr0; while(m=1) initstack1(optr); initstack(opnd); push1(optr,=); printf(n *n); printf(n 输入运算表达式，以=结尾n); printf(n *nn); result=evaluate(opnd,optr); printf(n表达式的结果为 %dnn,result); getchar(); 4使用说明（1）进入主界面（如图）(2) 加法测试用例：（如图）(3) 减法测试用例：（如图）(4) 乘法测试用例：（如图）(5) 除法测试用例：5/0 0不能为除数 所以报错（如图）40/2 是正常运算 所以得到正常结果（如图）（6）算数优先级比较计算：（如图）5.实验总结1设置运算符栈和运算数栈辅助分析算符优先关系2在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算3识别出运算数的同时，要将其自负序列形式转换成整数形式4在程序的适当位置输出运算符栈，运算数栈，输入字符和主要操作内容实验初期对系统进行了分析，查资料，编译了起初的代码，在多次的错误修改后系统初具雏形，在老师的细心帮助和讲解下系统终于完成。参考文献1.数据结构（C语言版） 严蔚敏著 清华大学出版社第18页-39页 第118页-152页第214页-259页 第263页-288页2.学通C语言的24堂课（第一版） 刘彬彬 孙秀敏著 清华大学出版社第548-575页第657-668页3. 数据结构（第一版） 齐景嘉著