淮海工学院计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：表达式求值姓名：学号：专业班级：系（院）：计算机工程学院设计时间：设计地点：软件工程实验室、教室指导教师评语：成绩：签名：年月日1．课程设计目的1、训练学生灵活使用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。

2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

2．课程设计任务和要求：任务根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择使用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。

设计题目从任务书所列选题表中选取，每班每题不得超过2人。

学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度和难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。

学生自选课题需在18周前报课程设计指导教师批准方可生效。

要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。

前期准备工作完备和否直接影响到后序上机调试工作的效率。

在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。

2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。

3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。

3．课程设计说明书一 需求分析[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。

假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。

引入表达式起始、结束符是为了方便。

编程利用“算符优先法”求算术表达式的值。

[基本要求]（1） 从键盘读入一个合法的算术表达式，输出正确的结果。

（2） 显示输入序列和栈的变化过程。

二 概要设计1、设定“操作数”的栈的抽象数据类型定义： ADT SqStack_f{数据对象：D={i a },+∈∈N i R a i数据关系：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定n a 端为栈顶，i a 端为栈底。

基本操作：InitStack_f(&S)操作结果：构造一个空栈S 。

GetTop_f(&S,&e) 初始条件：栈S 已存在。

操作结果：用e 返回S 的栈顶元素。

Push_f(&S ，ch)初始条件：栈S 已存在。

操作结果：插入元素ch 为新的栈顶元素。

Pop_f(&S,&e)初始条件：栈S 已存在。

操作结果：删除S 的栈顶元素，并以e 返回其值。

}ADT SqStack_f2、设定“操作符”的栈的抽象数据类型定义：ADT SqStack_c{数据对象：D={i a {}},'^'/'''*'''''+∈-+∈N i a i数据关系：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定n a 端为栈顶，i a 端为栈底。

基本操作：InitStack_c(&S)操作结果：构造一个空栈S 。

GetTop_c(&S,&e) 初始条件：栈S 已存在。

操作结果：用e返回S的栈顶元素。

Push_c(&S，ch)初始条件：栈S已存在。

操作结果：插入元素ch为新的栈顶元素。

Pop_c(&S,&e)初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。

}ADT SqStack_c3、本程序包含六个模块1）主程序模块void main( ){初始化；while(命令==“继续”){接受数据；处理数据；接受命令；｝｝2）栈模块——实现栈抽象数据类型3）判断运算符优先级模块——判断运算符的优先级别4）后缀表达式转换模块——将中缀表达式转换为后缀表达式，方便操作5）无括号表示式求值运算模块——根据后缀表达式求值，并输出中间和最终结果6）运算结果输出模块——以正确形式输出表达式的值三详细设计1、主程序中需要的全程量#define TTACK_INIT_SIZE 100 //初始分配最大空间量#define STACKINCREMENT 10 //（默认）增补空间量2、结点类型、指针类型typedef struct{float *base; //存储实型数据元素的一位数组float *top; //栈顶指针int stacksize; //栈数组容量}SqStack_f; //有序存储实型的顺序表类型typedef struct{char *base; //存储字符数据元素的一位数组char *top; //栈顶指针int stacksize; //栈数组容量}SqStack_c; //有序存储字符型的顺序表类型void InitStack_f(SqStack_f *s)void InitStack_f(SqStack_f *s)//构造一个存储实型（字符型）的空栈，预设空间为100，分配失败就退出void GetTop_f(SqStack_f *s,float *e)void GetTop_c(SqStack_c *s,char *e)//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序void Push_f(SqStack_f *s,float e)void Push_c(SqStack_c *s,char e)//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间void Pop_f(SqStack_f *s,float *e)void Pop_c(SqStack_c *s,char *e)//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序其中部分操作的伪码算法（由于比较类似，以浮点型的栈为例）void InitStack_f(SqStack_f *s){//构造一个存储实型的空栈，预设空间为100，分配失败就退出s->base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s->base)exit(1);s->top=s->base;s->stacksize=TTACK_INIT_SIZE;}void GetTop_f(SqStack_f *s,float *e){//若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序if(s->top==s->base){printf("ERROR!\n");exit(1);}*e=*(s->top-1);}void Push_f(SqStack_f *s,float e){//在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间if(s->top-s->base>=s->stacksize){s->base=(float *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float));if(!s->base){printf("OVERFLOW!\n");exit(1);}s->top=s->base+s->stacksize;s->stacksize+=STACKINCREMENT;}*s->top++=e;}void Pop_f(SqStack_f *s,float *e){//若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序if(s->top==s->base)exit(1);*e=*--s->top;}3、判断运算符优先级的算法：算符间的优先关系如下：+ - * / ( ) # + >= < < < < > >- > >= < < < > >* > > >= > < > >/ > > > >= < > >( < < < < < =) > > > > > ># < < < < < = 伪码算法：int precede(char Top_char,char s1_char){//栈顶的运算符赋给Top_char，新读入的运算符赋给s1_char。

判断它们的优先级//若栈顶运算符优先级高，则返回1，否则返回0int i,pre[2];char op[2];op[0]=Top_char; //栈顶的运算符赋给op[0]op[1]=s1_char; //新读入的运算符赋给op[1]for(i=0;i<2;i++)switch(op[i]){case'(':case')':pre[i]=0;break; //将括号的优先级设为0case'+':case'-':pre[i]=1;break; //将+ - 运算符的优先级设为1case'*':case'/':pre[i]=2;break; //将* / 运算符的优先级设为2case'^':pre[i]=3;break; //将^ 运算符的优先级设为3}if(pre[0]>=pre[1]) //栈顶元素优先级高返回1return 1;elsereturn 0; //否则返回0}4、中缀表达式转换为后缀表达式的算法：算法过程描述：1)首先将左括号“(”压进栈，作为栈底元素；2)从左而右对算数表达式进行扫描，每次读入一个字符s1[i]；3)若遇到数字或小数点，则立即写入s2[i]，若遇算数运算符，将“”（空格）写入s2[i]；4)遇到左括号“(”则压栈；5)若遇算术运算符，如果它们的优先级比栈顶元素高，则直接进栈，否则弹出栈顶元素输出到s2[i]，直到新栈顶元素的优先级比它低，然后将它压栈；6)若遇到右括号“）”，则将栈顶元素输出到s2[i]，直到栈顶元素为“（”，然后相互抵消；7)当扫描到“#”符号，表明表达式串已全部输入，将栈中的运算符全部输出到s2[i]，并删除栈顶元素。