数据结构课程设计-表达式求值【完整版】.docx
XXXXXX大学数据结构课程设计报告班级：学号：姓名：指导老师:-算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数(OPerand)、运算符(OPeratOr)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符，如：#(7+15)*(23-28/4)引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能(1)从键盘读入一个合法的算术表达式，输出正确的结果。(2)显示输入序列和栈的变化过程。三、程序运行平台VisualC+6.0版本四、数据结构本程序的数据结构为栈。(1)运算符栈局部：structSqStack定义栈(char*base;栈底指针char*top;栈顶指针intstacksize;栈的长度intInitStack(SqStack&s)建立一个空栈S(if(!(s.base=(char*)malloc(50*sizeof(char)exit(O);s.top=s.base;s.stacksize=50;returnOK;charGetTop(SqStacks,char&e)运算符取栈顶元索if(s.top=s.base)栈为空的时候返回ERROR(Printf("运算符栈为空!n");returnERROR;)elsee=*(s.top-1);栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;intPush(SqStack&s,chare)运算符入栈if(s.top-s.base>=s.stacksize)(Printf("运算符栈满!n")；s.base=(char*)realloc(s.base,(s.stacksize+5)*sizeof(char);栈满的时候，追力口5个存储空间if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e;把e入栈returnOK;)intPo(SqStack&s,char&e)运算符出栈(if(s.top=s.base)栈为空栈的时候，返回ERROR(Printf("运算符栈为空!行)；returnERROR;else(e=*-s.top;栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturnOK;intStackTraverse(SqStack&s)/运算符栈的遍历(char*t;t=s.base;if(s.top=s.base)(Printf(“运算符栈为空!n“)；栈为空栈的时候返回ERRORreturnERROR;while(t!=s.top)(printf(,%c,',*t);栈不为空的时候依次取出栈内元素t+；)returnERROR;(2)数字栈局部：structSqStackn定义数栈int*base;栈底指针i11t*top;栈顶指针intstacksize;栈的长度；intInitStackn(SqStackn&s)建立一个空栈S(s.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);存储分配失败s.top=s.base;s.stacksize=50;returnOK;intGetTopn(SqStackns,int&e)数栈取栈顶元素if(s.top=s.base)(Prirltf(“运算数栈为空!r);栈为空的时候返回ERRORreturnERROR;)else'e=*(stoP-1);栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturnOK;intPushn(SqStackn&s,inte)数栈入栈(if(s.top-s.base>=s.stacksize)(Printf("运算数栈满!n");栈满的时候，追加5个存储空间s.base=(int*)realloc(s.base,(s.stacksize+5)*sizeof(int);if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;插入元素e为新的栈顶元素s.stacksize+=5;)*(s.top)+=e;栈顶指针变化returnOK;)intPopn(SqStackn&s,int&e)/数栈出栈(if(s.top=s.base)(printf("运算符栈为空!n”);栈为空栈的视时候，返回ERRoRreturnERROR;else(e=*-s.top;栈不空的时候，那么删除S的栈顶元素，用e返回其值，并返回OKreturnOK;)intStackTraversen(SqStackn&s)数栈遍历int*t;t=s.base;if(s.top=s.base)(printf("运算数栈为空!r);/栈为空栈的时候返回ERRORreturnERROR;while(t!=s.top)(printf(%d",*t);栈不为空的时候依次输出t+；)returnERROR;)五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个#'压入运算符栈。输入一个算术表达式的字符串(以#结束)，从第一个字符依次向后读，把读取的数字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后两个#'遇到一起那么运算结束。数字栈顶的数字就是要求的结果。2、时间复杂度：0(n)数据压缩存储栈，其操作主要有：建立栈intPush(SeqStack*S,charx)入栈intPop(SeqStack*S,charx)出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是消耗在输入操作。六:测试用例如下图。最终结果如下图:表达式结果是：-66继续运算请接Y/y退由程序请按N/n七、源代码第七题算术表达式求值问题描述一个算术袤达式是由操作数(OPerand)、运算符(OPeratOr)和界限符(delim计ej组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#"，如：#(7+15)*(23-28/4)#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。根本要求(1)从键盘读入一个合法的算术表达式，输出正确的结果。(2)显示输入序列和栈的变化过程。#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<conio.h>#include<ctype.h># defineOK1# defineERROR0# defineSTACKNIT_SIZE100/#defineSTACKINCREMENT10/=/以下定义两种栈，分别存放运算符和数字/=IIit/戋3jstructSqStack定义栈(char*base;/栈底指针char*top;栈顶指针intstacksize;栈的长度)；intInitStack(SqStack&s)建立一个空栈Sif(l(s.base=(char*)malloc(50*sizeof(char)exit(O);s.top=s.base;s.stacksize=50;returnOK;)charGetTop(SqStacks,char&e)运算符取栈顶元素if(s.top=s.base)栈为空的时候返回ERRORPrintf("运算符栈为空!俏;returnERROR;)elsee=*(s.top-1);栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturnOK;)intPush(SqStack&s,chare)运算符入栈if(s.top-s.base>=s.stacksize)Printf("运算符栈满!n”)；s.base=(char*)realloc(s.base,(s.stacksize+5)*sizeof(char);栈满的时候，追加5个存储空间if(s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;)*(s.top)+=e;把e入栈returnOK;)intPop(SqStack&s,char&e)运算符出栈(if(s.top=s.base)栈为空栈的时候，返回ERRoR(Printf("运算符栈为空!n)returnERROR;)elsee=*-s.top;栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturnOK;)intStackTraverse(SqStack&s)运算符栈的遍历char*t;t=s.base;if(s.top=s.base)Printf(“运算符栈为空!n”)；栈为空栈的时候返回ERRORreturnERROR;while(t!=s.top)printf('%c',*t);栈不为空的时候依次取出栈内元素t+；)returnERROR;)y*-P*structSqStackn定义数栈int int int)；*base;栈底指针*top;栈顶指针stacksize;栈的长度intInitStackn(SqStackn&s)/建立一个空栈Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);存储分配失败s.top=s.base;s.stacksize=50;returnOK;)intGetTopn(SqStackns,int&e)数栈取栈顶元素if(s.top=s.base)Primf("运算数栈为空!n");栈为空的时候返回ERRORreturnERROR;)
