数据结构课程设计-表达式求值.doc

XXX大学数据结构课程设计报告班级：学号：姓名：指导老师:目录一 算术表达式求值一、 需求分析二、 程序得主要功能三、 程序运行平台四、 数据结构五、 算法及时间复杂度六、 测试用例七、 程序源代码二 感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oeran）、运算符(operator）与界限符（deimiter)组成得。假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：(7+15）*（28/）#。引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。(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=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入栈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+; etur 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 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)/数栈出栈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；五、算法及时间复杂度、算法:建立两个不同类型得空栈,先把一个压入运算符栈。输入一个算术表达式得字符串（以结束），从第一个字符依次向后读，把读取得数字放入数字栈，运算符放入运算符栈.判断新读取得运算符与运算符栈顶得运算符号得优先级，以便确定就是运算还就是把运算符压入运算符栈.最后两个#遇到一起则运算结束.数字栈顶得数字就就是要求得结果。2、时间复杂度:O(n）数据压缩存储栈，其操作主要有：建立栈in Push(SeqStak *S,chx)入栈int Pp(SeqStak , char x)出栈.以上各操作运算得平均时间复杂度为O(n)，其主要时间就是耗费在输入操作.六、 测试用例如图所示.最终结果如图所示：七、 源代码/*第七题 算术表达式求值问题描述一个算术表达式就是由操作数(oan）、运算符（opeaor)与界限符（delmir）组成得。假设操作数就是正整数,运算符只含加减乘除等四种运算符，界限符有左右括号与表达式起始、结束符“”,如:#(7+15）（2-284)。引入表达式起始、结束符就是为了方便。编程利用“算符优先法求算术表达式得值。基本要求（1） 从键盘读入一个合法得算术表达式,输出正确得结果.（）显示输入序列与栈得变化过程。*incue sdio、hincldsting、nclude stdli、hnclude efine OK #define ROR 0efine STACKNIT_SIZE 100 /efine STACKNCRMT 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-s、bs 、stacks） rintf（运算符栈满!）； s、bse=(char）alc (s、base，（s、stckze+5)sizof（car） );/栈满得时候,追加5个存储空间 if(！、)xit (OVERFLOW);s、tp=s、base+、taksize; s、stacsize+=5；（s、to）+=； /把e入栈returnOK; ntPop（SqSta ,car ) /运算符出栈if(、to=s、bae) /栈为空栈得时候，返回RROR int（”运算符栈为空!n”）； er ERROR; ese=-s、to； /栈不为空得时候用e做返回值,删除S得栈顶元素,并返回OKn OK； n tckTrrse（SStack &s) /运算符栈得遍历 chart;=s、ase； （s、top=s、b） prit（”运算符栈为空!n”)； /栈为空栈得时候返回ERROR eturn RROR；wie(！=s、top）prinf(” c”，*t)； /栈不为空得时候依次取出栈内元素 t+; return RO；/*数字栈部分* strcSqSackn /定义数栈 t *base; /栈底指针 in to; /栈顶指针 t stacsze; 栈得长度；intnitStackn (SSakn &s） 建立一个空栈S s、base（int）alc（50sizeof(nt）; i（！s、bs)exi(OERFLOW）； /存储分配失败 、op=、base; 、sacksiz=50; retrnK; nt etopn(qStackn ,int &e） /数栈取栈顶元素 if（s、op=s、bse) pintf(运算数栈为空!”）； /栈为空得时候返回ROR eturn RRO; lse =*（、to1）; /栈不为空得时候,用e作返回值，返回S得栈顶元素,并返回 reur O； i ushn（Stan &s，int e) /数栈入栈 if (s、ops、s =s、stace）prntf(运算数栈满!”); /栈满得时候，追加5个存储空间 s、be(it)roc (、bas,（s、stcsie+）*sieof(in) ）; if（！、bas） exit （OVRFL)；s、o=s、base+s、scksiz； /插入元素e为新得栈顶元素 s、tacksz+=5；(s、top）+e； /栈顶指针变化trn OK; it Pop（SSkn &s,int e) /数栈出栈if（、top=、base) prit（” 运算符栈为空！n）; /栈为空栈得视时候，返回OR retrnEROR; else=*-s、op;/栈不空得时候,则删除得栈顶元素，用e返回其值,并返回OKetun OK;in takTvese(qStacns)数栈遍历 in *t；t=s、a ;if(s、top=s、bae） prntf（运算数栈为空!”）； /栈为空栈得时候返回ERROR tu ERR;ile（！s、op) prntf（d,*）； /栈不为空得时候依次输出 +； retun ERRO；/=/ 以下定义函数/=int Isoprator（cah) /判断就是否为运算符，分别将运算符与数字进入不同得栈wic（c）ase +:cae-：cs *:cs /:cse（:case ）：ase #:retur 1;dfat：rurn 0;in Operat（in , chr o, int b)/运算操作it slt；sitch（p)cse +：esult=a+b;break；case ：result=ab;break；cae*：rsut=a；brek；ase/：rsua/b；r；retn reult；ca Precde（car c1, char c2) /运算符优先级得比较 r p； switch（h1) cae +: cas ： i （ch2=|ch2=ch2=）|ch2=#） p= ； /ch运算符得优先级小于c2运算符 es p ； ba； cae *： case /: i （h = （) =; ese p = ; brek； cas （: if（ch2 ）)p = =; leif ( #) printf（” 表达式错误！运算符不匹配！n）;eit(0）； else = ； eak ; ase #： f （ch2 = )） prt( 表达式错误！运算符不匹配！） ； xit(）； lse （2 )p = =； esp=； break; reurn p; /=/ 以下就是求值过程/=n EvauatExression() /参考书p53算法3、 it a, ， temp， answer; cha ch，op，e； ca *sr； intj= 0； SStacn OND； /OPND为运算数字栈 qStackOPTR； /OR为运算符栈 IiSa(PT）; uh（OPT,）； /，所以此栈底就是#,因为运算符栈以作为结束标志 InStakn(OPND); / printf(nn按任意键开始求解：n”）； / c=gech()； prin(n请输入表达式并以#结束：n); str =(char）mallc（5sizef（char）； gets(str); c=rj; /h就是字符型得,而e就是整型得整数 j+； GetTp(OPTR,e)； /e为栈顶元素返回值 wh （！=e!=） if (！soerato（ch) /遇到数字，转换成十进制并计算 temp=ch-0； /将字符转换为十进制数 =strj；j； hi(!Isopraor（ch） tep=ep10 + ch0; /将逐个读入运算数得各位转化为十进制数 h=srj； j+; Pushn(O,temp)； els i （soptor(h）) /判断就是否就是运算符,不就是运算符则进栈 sitch (Prece（e,c)） cse :Puh(OPTR，c）; /栈顶元素优先权低 ch strj+;rintf（”nn 运算符栈为：n）； /输出栈,显示栈得变化StckTraers（PTR)；printf(n 运算数栈为:n”）；Sackraversen(OND);beak; case : Po（OPTR,op)； / 脱括号并接收下一字符 ch =sr+ ；rintf(n 运算符栈为:n”)；StckTavrs（OPTR）;rintf(” 数栈为：”）;StackTravesen(N）；break; cs ： Pop(OP,op）; /弹出最上面两个，并运算，把结果进栈 Popn(PND，b);opn（OP,a）;Ph（D,Operae（a，,b）；rintf（”nn 运算符栈为：n）;StaTraverse(P)；rntf（”数栈为：”）；StcTaves(OPN); else pintf(”您得输入有问题,请检查重新输入！）; exit（0)； etTp（OPTR,e）； /取出运算符栈最上面元素就是否就是# /while Topn(OPD，anser）; /已输出.数字栈最上面即就是最终结果 return aswe；/=/ 执行部分/= ShowMenu（）rnf(nn”）；nt( 表达式求值系统n);voidQit（）；vidage()int answer;/ShoMenu(）;awe=valtExpreion(）；pint（nn表达式结果就是: dn，anse）;Quit（）；oid Quit()ch ch; prinf（ 本次运算结束.n)； pintf( 继续本系统吗？nn”）；pritf(”继续运算请按/y ”）;pinf(n 退出程序请按N/n )；printf( n_n）;ch=getch（）；ch=oupp（h）; /将c字符转换成大写字母i（ = )intf(”nn 系统退出。n”)；et();Manae(）;n an(）howenu(); Manage(）;return ；感想体会与总结好得算法+编程技巧+高效率好得程序。1、 做什么都需要耐心，做设计写程序更需要耐心.一开始得时候,我写函数写得很快，可就是等最后调试得时候发现错误很隐蔽,就很费时间了。后来我先在纸上构思出函数得功能与参数,考虑好接口之后才动手编,这样就比较容易成功了。2、 做任何事情我决定都应该有个总体规划。之后得工作按照规划逐步展开完成。对于一个完整得程序设计,首先需要总体规划写程序得步骤,分块写分函数写，然后写完一部分马上纠错调试。而不就是像我第一个程序,一口气写完,然后再花几倍得时间调试。一步步来,走好一步再走下一步。写程序就是这样,做项目就是这样，过我们得生活更就是应该这样。3、 感觉一开始设计结构写函数体现得就是数据结构得思想,后面得调试则更加体现了人得综合素质,专业知识、坚定耐心、锲而不舍,真得缺一不可啊。4、 通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于栈与排序得算法等知识,更磨练了我得意志.