《数据结构课程设计-表达式求值【完整版】》由会员分享，可在线阅读，更多相关《数据结构课程设计-表达式求值【完整版】（17页珍藏版）》请在金锄头文库上搜索。
1、XXX大学数据结构课程设计报告班级：学号：姓名：指导老师:目录一 算术表达式求值一、 需求分析二、 程序得主要功能三、 程序运行平台四、 数据结构五、 算法及时间复杂度六、 测试用例七、 程序源代码二 感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oeran）、运算符(operator）与界限符（deimiter)组成得。假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：(7+15）*（28/）#。引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术
2、表达式，输出正确得结果。(2）显示输入序列与栈得变化过程。三、程序运行平台sa C+6、0版本四、数据结构本程序得数据结构为栈。（1）运算符栈部分：struct SqStak /定义栈 char *base； /栈底指针 r *to; /栈顶指针 in stacsie； /栈得长度;inInitSack (Sqack &) /建立一个空栈S f （!(s、se= (char ）alloc(5 izeof（chr）)）) ext（0）； 、op=s、bse; s、staksi=0； retun OK； har GeTop（SqStack s,char &e) /运算符取栈顶元素 i (s、op=
3、s、ase) /栈为空得时候返回EROR prntf(运算符栈为空！n)； reurn ERR; else e*（s、o-1); /栈不为空得时候用做返回值，返回S得栈顶元素，并返回OK return; nt Push(SqStacs，cr ） /运算符入栈 if （s、tps、bae = 、tacksz） ritf（运算符栈满!n）; s、bas=（ca*）rello(s、be，(s、sackze+5)*izeo(car） ）； /栈满得时候,追加5个存储空间 f(！s、bas)ext （OVEROW）；s、top=s、s+s、acsize; s、taksi+=;(s、op）=e； /把e入
4、栈eturn OK; n Pop(SqStak &，char ） /运算符出栈 (s、to=s、base) /栈为空栈得时候，返回ERO rintf（运算符栈为空!n”）; return ERRO; elsee=-、tp；/栈不为空得时候用e做返回值，删除S得栈顶元素，并返回Kreturn OK； it StackTaerse（qStac&)/运算符栈得遍历 char t；t=s、 ；if (s、top=s、bae） print（”运算符栈为空！”)； /栈为空栈得时候返回ROR eturn ERO;hile（t！s、tp)rf（ %c,t)； /栈不为空得时候依次取出栈内元素 t+; etu
5、r ERR；（2） 数字栈部分： strt SqSackn/定义数栈 nt *bse; /栈底指针 nt tp； /栈顶指针 n sacksze； /栈得长度;inItStack (SqSackn &s) /建立一个空栈 s、base=（int）maloc（50*szeof(int）); if(！、ase）ei（OVEFLW）； /存储分配失败 s、top=s、base； s、stacksiz=5; reunOK； t GtTon(qtcn s,in e) /数栈取栈顶元素 if（s、op=s、base） prin(运算数栈为空!);/栈为空得时候返回ERROR rtur ERROR; ese
6、 e（s、to-1);/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回O retur K； int Pshn（SStckn s，int ) /数栈入栈 if（s、tps、as s、stacksie)prf（运算数栈满!）； /栈满得时候,追加5个存储空间 s、base=(int）realloc (s、bae,(s、stcksize5)szof（nt); f（!s、base) xit (ERFLOW)；s、top=、bs、stacsize;/插入元素e为新得栈顶元素 s、stackse+=5；*（s、top）+=e; /栈顶指针变化returOK; tPop(Sacn s，it &e)/
7、数栈出栈if （s、top=、base） pit（运算符栈为空！n);/栈为空栈得视时候，返回ERR retrn ERROR； lsee=-、tp； /栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OKreturOK；nt Stacravesn（SqStackn &s)/数栈遍历 i t;=s、bas ;if（s、top=s、bas） pinf(运算数栈为空！n”）；/栈为空栈得时候返回ERROR rrnER；wile（t！=、op) pritf(” d”，*); /栈不为空得时候依次输出 t; return ERRR；五、算法及时间复杂度、算法:建立两个不同类型得空栈,先把一个压入运
8、算符栈。输入一个算术表达式得字符串（以结束），从第一个字符依次向后读，把读取得数字放入数字栈，运算符放入运算符栈.判断新读取得运算符与运算符栈顶得运算符号得优先级，以便确定就是运算还就是把运算符压入运算符栈.最后两个#遇到一起则运算结束.数字栈顶得数字就就是要求得结果。2、时间复杂度:O(n）数据压缩存储栈，其操作主要有：建立栈in Push(SeqStak *S,chx)入栈int Pp(SeqStak , char x)出栈.以上各操作运算得平均时间复杂度为O(n)，其主要时间就是耗费在输入操作.六、 测试用例如图所示.最终结果如图所示：七、 源代码/*第七题 算术表达式求值问题描述一个算
9、术表达式就是由操作数(oan）、运算符（opeaor)与界限符（delmir）组成得。假设操作数就是正整数,运算符只含加减乘除等四种运算符，界限符有左右括号与表达式起始、结束符“”,如:#(7+15）（2-284)。引入表达式起始、结束符就是为了方便。编程利用“算符优先法求算术表达式得值。基本要求（1） 从键盘读入一个合法得算术表达式,输出正确得结果.（）显示输入序列与栈得变化过程。*incue sdio、hincldsting、nclude stdli、hnclude efine OK #define ROR 0efine STACKNIT_SIZE 100 /efine STACKNCRM
10、T 10/=/ 以下定义两种栈，分别存放运算符与数字/=/*运算符栈部分*ruct SqStak /定义栈 cha base； /栈底指针 char to; /栈顶指针 stackize； /栈得长度；int Inittack （SqStc s） /建立一个空栈S i （！（s、ase=（a *）mallo（0 sizef（char)）) eit（0）; 、to=s、se; s、stacsize=50; eurn K; chr GtTop(SSack s，c e） /运算符取栈顶元素 if （、to=s、base） /栈为空得时候返回ROR itf(”运算符栈为空!n); retu ERR; else e*（s、top1); 栈不为空得时候用e做返回值，返回S得栈顶元素,并返回OK rn O； intPus（Stack ,chre) /运算符入栈 if （s、t
