数据结构课程设计报告_算术表达式求值.docVIP

软 件 学 院 课程设计报告书 课程名称 数据结构 设计题目 算术表达式求值 专业班级 学 号 姓 名 指导教师 刘金亮 2010 年 12 月 1 设计时间 2 2 设计目的 2 3设计任务 2 4设计内容 3 4.1 需求分析 3 4.1.1程序的功能 3 4.1.2基本要求： 3 4.1.3测试数据： 3 4.2总体设计 3 4.2.1程序用到的抽象数据类型 3 4.2.2主程序流程图： 4 4.2.3说明各模块之间的调用关系： 4 4.3详细设计 4 4.3.1程序中用到的抽象数据类型： 4 4.4测试与分析 6 4.4.1测试 6 4.4.2调试分析 8 4.5附录 8 5 总结与展望 12 1 设计时间 2010年12月27至2010年12月30 2 设计目的 加强我们的实践能力，掌握数据结构的应用，算法的编写，类C语言的算法转换成C程序并上级调试的基本方法。对我们基本的程序设计素养的培养和软件工作者作风的训练，起到显著的促进作用。 3设计任务 设计一个程序，演示用算符优先法对算术表达式求值的过程。 4设计内容 4.1 需求分析 4.1.1程序的功能 （1）完成运算符和运算数的识别处理。 （2）在识别出运算数的同时，将字符序列形式转换成整数形式。 （3）实现对算数四则混和运算表达式的求值。 4.1.2基本要求： 1、在本次演示中，要输入以字符序列的形式，语法正确且不含变量的整数表达式 然后咦“#”结束。 2、由于算符有优先关系，故用栈来实现。设置运算符栈接收运算符，优先权低的压入栈内，优先权高的进行运算，设置运算数栈，来接收运算数，并存储运行的结果。 3、在读入字符序列的同时，完成运算符合运算数（整数）的识别处理，以及相应的运算，在识别出是运算数的同时，将当前字符序列转换成整数形式。 4.1.3测试数据： 1）8+2-3 2）3*(7-2) 3）8/(4-2) 4.2总体设计 4.2.1程序用到的抽象数据类型 本程序利用栈的概念，利用栈“先进后出”的原则，利用链表的存储结构，进而设计的。 4.2.2主程序流程图： (1) 首先定义一个栈，将字符x入栈定义栈结点，之后x出栈,既得到栈顶元素初始化的一个栈； (2) 对输入的字符判断是否为运算符，并比较其优先级； (3) 在读入字符序列的同时，完成运算符合运算数（整数）的识别处理。 在读入字符序列的同时，完成运算符合运算数（整数）的识别处理在读入字符序列的同时，完成运算符合运算数（整数）的识别处理。 4.2.3说明各模块之间的调用关系： 本算法一共进行了两次调用，第一次调用是char Eval_Exp()对void PushOptr(SNode *top,char x)和char PopOptr(SNode *top)的调用，第二次是char Eval_Exp()的调用，完成了运算符的操作，完成字符串对整形的转换。 4.3详细设计 4.3.1程序中用到的抽象数据类型： 栈 #includecstdio #includemalloc.h #define NULL 0 typedef struct node{ //栈结点 char date; struct node *next; }SNode; SNode *InitStack(){ //初始化top SNode *top; top=(SNode *)malloc(sizeof(SNode)); top-next=NULL; return top; } 4.3.2对主程序和其它主要函数写出伪码算法： char Eval_Exp(){ //完成运算符操作 char a,b,c,r,f,z; int result; SNode *top[2]; top[0]=InitStack(); PushOptr(top[0],#); top[1]=InitStack(); c=getchar(); while(c!=#||(GetTop(top[0]))!=#){ if(!In(c)){ PushOptr(top[1],c); c=getchar(); }