还剩30页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》课程设计报告题目栈的应用表达式求值UUipULLXl-小结6文件F编辑E格式0查看V帮助Hq.4—
2.a2-C
4.4—
3.1C2—F g—
44.000000一5—81+N C2/0296通过此次的课程设计,
2.462289巩固和加深了我对栈、队列、字符串等02—4-
3.1-
8.
0000002.5%22%
2.52-1-3C—5C C C2-3C-
0.125000一〉・理论知识的理解;掌握现实复杂问题的分析建模和解决方法;提CC2335/Cl—1・强ErrorC56—N035%C
3.2—
2.1Error・3O.2-Fl
1.+++11高利用计算机分析解决综合性实际问题的基本能力井]ErrorError在细节问题的分析上,较以往有了很大的提高在寻求最优解ErrorError的问题上,也能够找到多种Error解决方案来使自己的程序收放自如如,Error在处理实数的问题上,我采用的是每取得一个字符,就立刻对此字符进行处理的方法其实,我们可以用一个字符数组,来存储连接着的一系列数字字符,然后再通过atof函数,直接得到字符数组中所存储的数字再如,对负数问题的处理上,我最初的想法是通过一个标志mark来记录前面的字符是否是负号或减号,再在后面取到除符号外的数字时,选择是否添加负号另外,与其他人不同的是,在我的课程设计中,Compare函数与其他有着很大的区别通常情况下,同学们参照课本,都会采用占用7*7=49个空间的数组来分别存储对应两个字符的优先级符号,并对两个字符进行预算之后得到数组中的位置虽然7*7的数组所占的空间并不是非常大,但在我看来这也是一种浪费,并且空间的浪费并没有换回时间一定的节省因此,我采用了一种常规的思路将各种运算符按照数学逻辑上的优先顺序进行排序,并得到两个字符之间的优先级关系这样一来,我们将不再需要那7*7的数组,且时间复杂度并不大幅增涨在这个课程设计中,运用到的数据结构的知识主要是栈的知识栈在各种软件系统中,应用非常广泛栈的的存储特性LIFO先进后出,使得在用栈来编程时,思路清晰明了在使用递归算法时,栈也是一种很好的选择此外,这次的课程设计进一步加强了我们运用C语言进行编程,调试,处理问题的能力,加深了我们对算法及数据结构的认识同时我也意识到,开发程序的早期计划要做的充分,以免出现程序完成后发现不足而带来的修改麻烦虽然这只是一个小小的软件,但对我们之后的影响确实很大的参考文献
[1]范策,周世平,胡哓琨.《算法与数据结构(C语言版)》[M].北京机械工业出版社,2004
[2]严蔚敏.《数据结构(C语言版)》.北京清华大学出版社,2004
[3]许卓群,杨冬青,唐世渭,张铭.《数据结构与算法》.北京高等教育出版社,2004
[4]徐孝凯.《数据结构实用教程(第二版)》.北京清华大学出版社,2006
[5]何钦铭等编著.数据结构课程设计.杭州浙江大学出版社,
2007.
[2]耿国华等编著.数据结构一用C语言描述.北京高等教育出版社.
2011.
[3]徐健等编著.数据结构上机指导与习题解析.南京南京大学出版社,
2007.
[4]陈建新等编著.数据结构实验指导与课程设计教程.北京科学出版社,
2010.附录源程序清单1ttinclude stdio.h ftincludestdlib.h ftincludemath.h intPrintError=0;/*全局变量,0代表正常,I代表表达式出错*/typedef structNode*PtrToNode;/*栈的定义*/typedefPtrToNode Stack;typedefstruct FNode*Ptr_Fn;typedefPtr_Fn FStack;typedefstruct FNode{float Element;Ptr_Fn Next;;typedef structNodechar Element;PtrToNode Next;};/xlx xlxvL*xlx xlxvL*VL*xt*vL*viz vlxsix vlx vlxvlxvl*vix xlxvlx vL*vlx xtx/XJX XjX XJX xjx xjs xjx xjx xjx xp*xjx xjx xjx xjx xp*xjx XJX XjX xjx xjx xjx xjx XJX xp*Xp*ZJX xjx xjx xy*xjx函数声明/int、XTX XJXXgX XTXxj XIX XIXXIX XjXX|X XTX XTX XIX XTS XT^X1X ZT%XIX ZjX XTX XTxjx XjXXIX✓TX XjX XTX XTX XIXXTSxTx/FisEmptyFStack S;void FPushfloatX,FStack S;float FTopFStack S;void FPopFStackS;int IsEmptyStackS;void MakeEmptyStackS;void Pushchar X,StackS;char TopStackS;void PopStackS;void ConvertToPostFILE*In,Stack Whereat,FILE*Temp;void ReverseStack Rev;void CalculateFILE*Change,Stack Whereat,FILE*Temp;void cover;void mainmenu;printoutput;voidiovoid author;//xjx XTX xjs ZTX XTX XT*zjx xvjL x*zv jl xx XTX✓TX ZTSxjx XTX XTXKTX xjx XTX xjs ZTX XTX XTX XTS主函数vj KLZKLX✓r%Xix xTxZjX//void maincover;mainmenu;/1^/^rx xTx^T%^r%封面函数/〃、力、xps xTs✓Tx^T%^T%^7%^7%^7%xTx xT^✓Ts xTx xTx^Tx✓Tx*TX✓Tx^7x7x xTx✓T%#rs^7^^7x Tx7%xTx^T%✓TsxTxxTx✓Tx xT^^T%/void coversystem/zcolor f0〃;printf〃\n\n\n〃;printf〃\t\t\t《数据结构》课程设计之\n〃;表达式求值\n〃;printf〃\n\n\n\n\n\n〃;printf z/\t\t\t madeby薛国庆、n\n〃;软件工程1102\n\n〃;2013年6月\n\n\n\n;printf z/\t\t\t\t\t\t\t按Enter继续〃;getchO;//xjx XTX xjsZTXX7^XTX XT*vL z*jx xjxzjx XTX✓TX ZTSxjx XK TT XX XTX xjxXTX xjsZTX XTX XTX XXv f T SXTS关于作者vL^vj KLZKLX^Tx✓Is*r%XiS Xrx xTx xr^JX ZjXZjs//void author{intc;system〃cls〃;printf〃\n\n〃;printf〃\t---------一关于作者一\n\n〃;printf〃\t\t\t程序员:\n\n〃;printf〃\t\t\t测试员:\n\n〃;printf〃\t\t\t文档员:\n\n〃;printf〃\n\n\n\n〃;printf zz\t\t\n〃printfC\t\t|
[0]返回主菜单|\n〃printf\t\t|
[1]退出|\n〃printf〃\t\t||\n〃printf\t\t\t请选择操作0—1:〃;scanf〃%d〃,c;switch ccase0:mainmenuO;break;case1:exit0;default:mainmenu;}/、、、、、、、/、^TS^TS^TS#TS^TS ZTS^T%7%^TS^TS XTSXT^T%XTS^TX XjXjX ZTX^TS TS^TX|X T%XTS ZjXTS^TXX|XXT%XTS^TX XTS^TX XjXjX ZTX^TS TS^TX|X T%XTS ZjXTS^TXX|XXT%XTS qXTS^TX XjX|X ZTX4rs q|X T%rs操作目的将用户输入的Input,txt文件中的中缀表达式计算结果存如Output.txt文件中初始条件用户将中缀表达式,逐行输入到Input,txt文件中操作结果自动生成一个Output.txt文档将结果逐行输出v*X£*jp X***✓A pxJ*X*xXX jjx xXv xXljJx xS*/xJ jx xv✓lx p**J xx jx XjXXjX✓Jx XJXxjx✓p*XJX XJX XjX XJSslXz JXvl✓x p*si xY*xjx xjx xjx✓Jx✓JX XJXXjX xjx XJX xv jl xxx p9*x XxJl Xx Xs Ji Xx xs pi*x XvJi Szxvjl xx xs ji xx*s*i px»x Xl Jz XXjX XJSXJX✓p*xjx xjxXjX✓Jx XJXxjxI xxp»xl XxJXsi XxJXl xxp*si xxjsvl xxjx xjx**p»XJXXjX XJS XxJl Xx✓/p*xjx xjxintsave{int c;FILE*InputFile,*OutputFile,*Temp;/*Temp用来存放后缀表达式*/Stack Whereat;/*记录后缀表达式中操作数与运算符的顺序*/char sample;/*用来存放*/InputFile=fopenInput.txt〃,〃r〃;OutputFile=fopenz/Output.txt〃,〃w〃;Whereat=malloc sizeofstructNode;Whereat-Next=NULL;if!InputFile||!OutputFile{printf^intput oroutput filesdo notexist.\n〃;return1;}sample=getc InputFile;whilesample!=EOF{/*EOF为文件结束的标志*/Temp=fopen zzTemp.txt〃,〃w+〃;ungetcsample,InputFile;/*将sample字符退回至输入流中*/ConvertToPost InputFile,Whereat,Temp;/*中缀-----------------------》》后缀*/if PrintError{fprintf OutputFile,/zError/z;fscanf InputFile,\sample;PrintError=0;}else if IsEmptyWhereat==1{/*跳过在input文件中的空格*/else if IsEmptyWhereat!=1{Reverse Whereat;/*将Whereat栈倒置*/if TopWhereat==B{/*B表示运算符*/PrintError=1;/*后缀表达式第一个元素是运算符号则表达式错误*/fclose Temp;Temp=fopenTemp.txt〃,〃r+〃;CalculateOutputFile,Whereat,Temp;/*计算后缀表达式的结果*/fclose Temp;MakeEmptyWhereat;/*将Whereat栈置空*/putcC\n,OutputFile;/*在输出文件中换行*/sample=getcInputFile;}freeWhereat;fclose InputFile;fclose OutputFile;/*释放空间*/remove/zTemp.txt〃;system/zclsz/;printf〃\n\n\n\n\t\t\t恭喜!Output,txt文件已经生成!\n〃;printf〃\n\n\n\n〃;printf〃\t\t表达式求值\n\n/zprintf,z\t\t|
[0]返回主菜单l\n\nprintfz/\t\t|
[1]退出|\n\n〃printf||\n〃;printf〃\t\t\t scanf级d〃,请选择操作0—1〃;c;switch c{case0:mainmenuO;break;case1:exit0;default:mainmenu;return1;//x Xl Jx Xx XljxXv XLJ*XxXl JxX xjxx xl jxxv Xl Jx Xv xL p**v Xl Jx Xvxl jx xx Xtjx XxXl JxXv XLf**v XiJz Xv XlJxXs Xijx XvXlJxXvXlJx Xvlxvl*vix xlXx jXvlxx jxvLX*JX xp*Xp*ZJs Xi*xjs xixX|X XJXXv fl*xXs JiXxXJXXjX XJX XJXXIXXjX xjx XJX xp*Xp*ZJX xjxX|X XJXXf*XJX**P*✓JX|X XJXxj xjxXjX xjxX|X操作目的将自动生成的Output,txt中每一行的结果读取输出初始条件生成一个Output,txt文档将结果逐行输出操作结果在窗口逐行输出结果/«、^TX^TX XTV^TX^TS^7%XTX XTX XTS^TX TS^TX^TX XT%XTX ZTX^TS^TX XTXXTV XTX^TS^7%XTX XTX XTS^TX^TS^TX^TXXT%XTX ZTX^TS^TX XTXXTV XTX^TS^7%XTX XTXXTS^TX^TS^TX^TX XTX XTXXTS XTS^TX^T%^TS XTX^TX ZTX✓TS^TS^TS#TV//*J*Jx*A1«Jx«1*Jx1**J*1*A«J/zjx xjx xTx xrx xTs ZTXzlx zTxTx TsxTs^Tx Ts^Ts^Ts^Ts zTx^TxOutput输出函数K|^xj vfv|/*T*^7^^7xxT^#Tv xT^^Tx#TS^Tx^7xxT^^Ts^TS^7^^7^xT^^TS^TS XTV^TV^TV^TS/void printOutput{int c;int i=0;char str
[100]
[100];/*二维数组用来存放字符串*/char a
[100];/*中间变量*/FILE*fp;system//cls,/;fp=fopen/zOutput.txt〃,〃rb〃;if fp=二NULLprintf z/0pen Fileerror!/z;while!feof fpstrcpy str[i++],a;/*将@赋给str[i++]*/fscanf fp,zz%sz/,a;printf z/欢迎使用--------------------------\n\n〃;printf〃\t\tlnput.txt文件中每一行的中缀表达式的计算结果如下\n\n;for i=0;i38;i++/*可以根据Output,txt中结果的个数改变循环次数*/printf〃\t\t%s\n〃,str[i];fclose fp;printf〃\n\n\n\n〃;printf〃\t\t\n〃printf|
[0]返回主菜单|\nprintfzz\t\t|
[1]退出l\n〃printf〃\t\t||\n〃printf\t\t\t请选择操作0—1:;scanf〃%d〃,c;switch c{case0:mainmenuO;break;case1:exit0;default:mainmenu;//K XL T*XS XL T*X K✓L T*xS✓L*jX XTX xjx zlxKJ✓J T*x*X1T*X XTXxL**1*XIKL X*XjX XTXXTX KL*KL*S XLT*X✓TXxjx xTx xK TJ xJ*Xjs Xi*X7XXTXv✓t T*xK ZLj*X xTx XTX KL*K✓LT*s*1*x zLT*s KZL l*X*1**JL x*jxvt*sL**✓l Tx xKL z*TxKL x*Tx*1x*Tx zTx操作目的将Input,txt每一行的结果读取输出初始条件Input.txt文档存在操作结果在窗口逐行输出Input,txt文件中的中缀表达式vL*zx pL**xx jjxx xx jl xx✓si Jxs*Jx xjx xx jl xx xx jl xx xv yisz^v Jls*✓xl fxs xjx xjs zys zys zp*xps xjx✓Jsxlx xjx xjx xys✓Js✓fs xjXxL*xjs xjx zys z^s xp*xjx xjx✓Js✓fsx xljxx*xX j*x xysxjx xjs xjxzyszp*xjx xjx1s////✓Ts Zr%*Tx%z ZT%^XzInput输出函数v*f4^Kl xTxXTX✓rs xrsyjx xTx KTr^KI KT//void printinput{int c;int i=0;char str
[100]
[100];char a
[100];FILE*fp;system〃cls〃;fp=fopenInput.txt〃,〃r〃;if fp==NULL{printf,z0pen Fileerror!/z;}while!feof fpfscanffp,〃%s〃,a;strcpystr[i++],a;printf〃欢迎使用------------------------\n\n〃;printf z,\t\tlnput.txt文件中每一行的中缀表达式如下\n\n;for i=0;i38;i++printf〃\t\t%s\n〃,str[i];}fclose fp;printf〃\n\n\n\n〃;printf,z\t\t\n〃;printf,z\t\t|
[0]返回主菜单l\n〃;printf,z\t\t|
[1]退出l\n〃;printf〃\t\t||\n〃;printf\t\t\t请选择操作0-T”;scanf级d〃,c;switch c{case0:mainmenuO;break;case1:exit0;default:mainmenu;/vlx lzJz lz lz1*lz xlz^lz lz xlz^Iz*lz Iz six^lz slz xlz1^*Jz*lz xlzslz lzlz主菜单函数/^TS^TXXTXXTX ZT%ZT%ZTX XTX ZTX✓TX IZT%XTS XJXXTX TSXT ZTS ZTS^TS JXXTXXTXZT%ZT%ZTS XTX ZTX✓TX I✓!XTS XJXXTX T%#TS^T%vlx zvrL x*x*TJ xx xx jl xx sri%x zsTi sx✓Ts zrs xr%xTx xrs✓Tx rsxrs^TS^TS XTS TS ZTSZTS^TXXTSVS XTx*lx ZTSZTS XTS XTSXTS XTX TXTS^TSXTSZTS#TS//void mainmenuint c;system〃cls〃;printf〃\n\n\n\n〃;printf〃\t\t_____________________表达式求值___________________\n\n〃printf〃\t\t
[1]自动生成Output,txt文件\n\nprintf〃\t\t
[2]显示Output,txt文件结果\n\n〃printf〃\t\t
[3]显示Input,txt中的表达式\n\n〃printf〃\t\t
[4]关于作者\n\n〃printf〃\t\t
[5]返回课程设计总菜单\n\n〃printf〃\t\t
[0]退出\n\n〃printf〃\t\t\n〃;printf〃\t\t\t请选择操作0—5:〃;scanf级d〃,c;switch c{case1:save;break;case2:printOutput;break;case3:printlnputO;break;case4:author;break;case5:system〃数据结构课程设计.exe〃;break;case0:exit0;default:mainmenu;/^LZ KLZKI sXxKLX KLZXLZ Sj^Xz XzKLZ/*TSZT^ZT^XTV XTVXT*ZT%*T%ZTX#T%检查两种类型的栈是否为空KL KfW K]KT VF/*T^/int IsEmptyStackS{return S-Next==NULL;目录目录21概述
11.1课程设计目的
11.2课程设计内容12系统需求分析
11.1系统目标
12.2主体功能
13.3开发环境13系统概要设计
23.1系统的功能模块划分
24.2系统流程图24系统详细设计35测试
65.1测试方案
65.2测试结果66小结8参考文献9附录1源程序清单10int FIsEmptyFStackSreturnS-Next==NULL;//xp*xjx xjx✓Jsxlx vlx xjx xjx xys fs✓fs xjx xjs zyszys✓p*xps xjx✓Js xjx xjx xys✓Js✓fs xjx xjsxjxzysz^s xp*xjx xjx✓Js✓fs xjx xjxxysxjx xjsxjx两种类型的弹出栈顶元素six xxjlx*xxjl xxxxjlxxx*fJ*xxxjlxx xspi*x xlx*Jx*Jx xvyl s*xs fisx xjsxjx xjsxjs✓Jx xxjlxx xs ji xxxsji1x**xJ jxs^xL j*xx xljxxXxI jXxx xljxx*xJ jxsv✓lJxss xi jxxxjxxjsxp*xfs zj%xf*x1j^xv xljxxxI px*1*vlx✓p*xfs xjxxj%V✓IX p*l ZxJS✓JX///**************弹出堆栈栈顶元素***************************/void PopStack SPtrToNode FirstCell;if IsEmptySprintf〃栈为空〃;else{FirstCell=S-Next;S-Next=S-Next-Next;freeFirstCell;/********************弹出float栈顶元素****************/void FPopFStack SPtr_Fn FirstCell;if FIsEmptySprintf〃栈为空〃;else{FirstCell=S-Next;S-Next=S-Next-Next;freeFirstCell;/six si*six vizsix six six lxsix six xlx lxsix Lzxlx six six lzsix sixvlx/xjx xjx xjx xjx p*xjx xjx xjx xp*xjx xjx xjx xjxxp*xjx XJXXjX xjx xjx p*xjx xjxXJX xp*Xp*ZJX xjxX|XXJXxp*xjxXJXXjXxjx xjxp*xjxxjxxjx两种类型的置空栈xTx xlxxjxxjx xTx xTx xTx xjxXTX xrx xjxxjxxTx xlxXT^XT^XTXZTX*ZJ TxX zjxxrx xrx xTx xTx xTx xjxXTX xrxxjxxjxzTx*A xxTx xlxxrx xr^XTXZTXzTx zjxxrxxjx xrxxTsxjx✓Tx xjx[XTX//********************将堆栈置空******************/void MakeEmptyStack Sif S==NULLprintf〃你必须先建立一个栈!”;elsewhile!IsEmptySPopS;/******************将fl oat堆栈置空****************/void FMakeEmptyFStackSif S==NULLprintf〃你必须先建立一个栈!”;elsewhile!IsEmptySPopS;//xjxxjxxjxxjxxjx✓s Jixxxsjixxxjxxjsxy*xy*s xi jx xs xijxxx xljxxxxl pz*s xipx*sxijxxxjxxjxxjx xlxsi✓x Jxsixxjx^L x*jx%L x*jsxt zxjssi zxjxxl xxjxxl xzjxsi xxy*✓p*两种类型的元素进栈*lxx*jJ xxxxjlxxxvji xz*Jx%tx x*pA*xxj*xjxxjxxjx✓JX zjxxjxxjxxj x9xxjs xix xjxlx✓Js xixxjv xlxxjsxixxj*xjxxjxxjxxjxXJ%Xlx ZJs Xix XjsXix XgXxjx XjXsXlJzsix%jxxjxXJX///*X*7*4**A**J*X*xL**Jx*JL*vt**J*X*vt**J*JL*―r■A-tTK太1二*»t**X**Jx*Jx*JL**Jvt*vl*vt*L**A*vL**J*Jx*Jxvt**J*JL*//不不不不不不不不不不不不不不不不不不不不不不1】行、尺]/px不不不不不不不不不不不不不不不不不不不/void PushcharX,StackSPtrToNodeTmpCell;TmpCell=PtrToNodemallocsizeofstruct Node;if TmpCell==NULLprintf空间不够!”;else{TmpCell-Element=X;TmpCell-Next=S-Next;S-Next=TmpCell;/*********************fl oat元素进栈*****************/void FPushfloatX,FStackSPtr_Fn TmpCell;TmpCell=Ptr_Fnmallocsizeofstruct FNode;if TmpCell==NULLprintf空间不够!“;else{TmpCell-Element=X;TmpCell-Next=S-Next;S-Next=TmpCell;//xTx XTVxTx✓rx两种类型的返回栈顶元素/♦卜力、xpsxTs「、q、q、#T%x7xTq、q、r^x7xxTx✓Tx/、〃、xj、xTs xrxxrxq、力、力、xrs x7xxj、xj、x7xxTxxjx/、✓pw^Tx^7x//***************返回栈顶元素**************/char TopStackSif!IsEmptySreturn S-Next-Element;printf〃栈为空〃;exit1;return0;}/**************返回float栈顶元素**********/float FTopFStackSif!FIsEmptySreturn S-Next-Element;printf〃栈为空〃;exit1;return0;/Kf vf^Y KLx!vL*K]KL vf/r%*r^*r**r*T*将堆栈元素倒置v!/xTx xTx*Ts^Tx^7%XTX^Tx^T%#7%^T%XT^*Tx*Ts^Ts*T%^T%^Tx^TXXT^#T^^TS^TS^7%^7^^7^^Tv^Tx^Ts^7XXTXXTS^T%/void ReverseStack RevStackTempstack;Tempstack=mallocsizeofstruct Node;Tempstack-Next=NULL;while!IsEmptyRev{Push TopRev,Tempstack;/*将元素压栈到一个临时堆栈*/Pop Rev;}Rev-Next=Tempstack-Next;/*指向新的堆栈*///^7^^Tx xTv✓rK^T*T**T%K*fT%*TX*T%v frs中缀表达式转换为后缀表达式vf^^1KI/*T*^Txx7%XTX^r\^r\^r\^T%xr^xT%/void ConvertToPostFILE*In,Stack Whereat,FILE*TempStack OpHolder;char holder;/*中间变量,用来存放操作数和运算符*/char lastseen;int digitcounter=0;/*digitcounter用来计数*/OpHolder=mallocsizeof structNode;/*初始化*/OpHolder-Next=NULL;holder=getc In;/*从In中取字符赋给holder*/lastseen=@;/*用来防止输入格式错误*/putc,Temp;/*输入空格字符到存放后缀表达式的文件中*/while holder!=,\n,holder!=EOF{if holder={/*当holder为空格时,开始计数*/digitcounter=0;else ifIsOperatorholder=二-1{/*如果holder不是操作数或运算符号,则表达式有误*/PrintError=1;else ifIsOperator holder==0{/*判断holder是否为操作数*/if lastseen==holderlastseen==.{/*错误处理*/PrintError=1;elselastseen=holder;if digitcounter==0{/*digitcounter开始计数*/PushA,Whereat;/*操作数进栈*/digitcounter++;/*digitcounter力口一*/putc,Temp;putc holder,Temp;else{digitcounter=0;if lastseen==holderlastseen!二‘‘lastseen!=’/*将〃〃视为特殊情况处理*/PrintError=1;elselastseen=holder;ifIsEmptyOpHolder==1{/*当OpHolder为空*/Push holder,OpHolder;/*将holder压入栈OpHolder中*/Else if OperatorValue Top OpHolder6{/*如果OpHolder的栈顶是〃”的情况*/ifOperatorValueholder=5/*如果holder是〃的情况*/Pop OpHolder;/*则弹出OpHo1der的栈顶元素*/elsePushholder,OpHolder;else ifOperatorValueholder6{/*如果holder是〃的情况*/Pushholder,OpHolder;else ifOperatorValueholder二二5{/*如果OpHolder是的情况*/while IsEmptyOpHolder!=1OperatorValueTop OpHolder!=6{/*0pHolder不为空栈且OpHolder栈顶元素不为〃〃*/putc,Temp;Push,W,Whereat;/*将运算符压入到Whereat栈中*/Pop OpHolder;/*则弹出OpHo1der的栈顶元素*/putc TopOpHolder,Temp;ifIsEmptyOpHolder==1{/*错误处理,括号不匹配*/PrintError=1;elsePop OpHolder;elseifOperatorValue holder==OperatorValue TopOpHolder OperatorValueholder==3{/*幕运算情况*/Push holder,OpHolder;else ifOperatorValueholderOperatorValueTopOpHolder OperatorValueTopOpHolder==3{/*塞运算情况*/putc,Temp;Push,B,Whereat;putcTopOpHolder,Temp;PopOpHolder;whileIsEmptyOpHolder!=1OperatorValueTopOpHolder==3Push CB,Whereat;/*将运算符压入到Whereat栈中*/putc,Temp;putcTopOpHolder,Temp;Pop OpHolder;}Push holder,OpHolder;如果当前运算符号的优先级小于或者等于堆栈中的运算符号的优先级,则将其放入temp中,并且将堆栈中的运算符号出栈,放入temp中,直到堆栈为空或者优先级小于堆栈顶元素的优先级else ifOperatorValueTopOpHolder=OperatorValueholder{whileIsEmptyOpHolder!=1OperatorValueTopOpHolder=OperatorValueholder OperatorValueTopOpHolder!=6|putc,Temp;putc TopOpHolder,Temp;Push B,Whereat;Pop OpHolder;}Pushholder,OpHolder;else ifOperatorValueTopOpHolderOperatorValueholder{/*如果当前运算符号的优先级大于堆栈中的运算符号的优先级,则将其压入堆栈中Push holder,OpHolder;holder=getcIn;/*While循环结束*/whileIsEmptyOpHolder!=1{/*最后如果堆栈中还有运算符号,则一并放到temp中Push,B,Whereat;putc,Temp;putc TopOpHolder,Temp;Pop OpHolder;MakeEmptyOpHolder;free OpHolder;/slz xlzslz xlz*Jz*lzxlz^lz1^Iz^Ix Iz*X**lz^lzlzxlz*Jz lz£*xlz1*lzxlzxlz*lz^Iz-[、/^TS^T%^TSZTS^T%^TS^TSXTSZTSZTSZT%^TS^TSTS^T%^TS^TSXT%^TSZTS^T%^T%^TSXTSZT%ZT%#T%#T%#TXXT^^T%TSZTSTS^TX^TXT%ZTS判断类型vL*z*r1x^xTx XjXr%zTs✓Ts zlrs Jxxrs rs zrs zrsxr xTxxTx xTs xrs✓Ts✓*xrxxTxxrs ZTSzrs xrs7xxxlrz ssi rxszrszrsxrx*Tl xzx*rl xxxTsxrsT%rs^TSXTX/xjx^rs zl^/int IsOperatorcharToCompareif ToCompare==ToCompare=||ToCompare==+ToCompare|ToCompare=二*||ToCompare=二/||ToCompare二二==,%ToComparereturn1;/*运算符*/else ifToCompare==,T ToCompare==2ToCompare==3ToCompare==4ToCompare==5ToCompare=,6,ToCompare==7ToCompare==8ToCompare=,9,ToCompare==O ToCompare==.return0;/*操作数*/}else{return-1;/KL*SL**1X*xJ rXx*xX j*xK✓L r*xSL XT*X*xJ lx**J rXxK xJjJ x*x*r1x*x*jlxx*A**JL*xL**1*KL*S£**1X*JX KL*KL*SL**J*JX KJJ*si**JL**JL*\L*vt*KL*S£**1X*JX KL*/zTx zTx^Tx zjx^7^^Tx✓Tx zTsxjxxr^xr^zTx xrxxtx^TxxT^xjx^7^T^^Tx✓T%返回运算符号优先级vxLT*xxTxxTs vxl TxxK!TX s*x1T*x^TxXTXvlx*X*7xxlxKTx✓TxxT^Txv^LT^xvlx KL*z*71^*xrx vl//int OperatorValuechar ValueToGive{if ValueToGive==return6;if ValueToGive==return5;if ValueToGive==~return3;if ValueToGive==%return2;if ValueToGive==*return2;if ValueToGive==/return2;if ValueToGive==+return1;if ValueToGive==,return1;return0;//sXiJxXs XiJxXs xijx%sixXjX X|XxjsXJXxs pl*zsixv✓l JxXXjX xjxXJsSix XJsXix✓sjixx sXi JxXvXi JzXsxijx%sixsiXxjX X|XXJSXJXxp*✓s JiXx Xv|l XxXJXXJSXJXsi✓x jxsix|Xsi XxJXvi xzj%ixsixsixXjX X|XxjsXJ xp*✓sJiXx vXl|Xx^xL jxzxy*计算后缀表达式*X**X**Jx*JL**X*vL*xt**X*vL**Jx*Jx*Ax*JL**X**Jx*JxvL**J*X**JL*vL**Jx*Jx*Ax*JL**X**Jx*Jx/XTXXjXXgXXjXXTXXTXXTXXJXxjx✓TxXTXXlXXIXX7XXTXXTXXjXZTXxlx✓JxX7XXTXXTXXTXXjXZIX✓jXXaXXTXXIXXTXxlxXjX✓jXXTXXTXXTX^7XXjXXjXXTXXTXXTXXjXZIXXjXXaX✓TxXTSXTXXjX✓TX✓TxXT^/void CalculateFILE*Change,Stack Whereat,FILE*TempFStack Operands;float looker;char Op;char spacefinder;float answer=0;float NumA;float NumB;Operands=PtrFnmallocsizeofstruct FNode;Operands-Next=NULL;while IsEmptyWhereat!=1PrintError!=1{/*循环直到Whereat空,或者遇到错误*/if TopWhereat==A{fscanfTemp,〃〃,spacefinder;fscanf Temp,〃%f〃,looker;/*如果是A,则是操作数*/FPushlooker,Operands;PopWhereat;}else ifTopWhereat二二B{fscanf Temp,/z/z,spacefinder;/*如果是B,则是运算符*/Op=getc Temp;switchOp{/*判断是什么运算符*/caseC:/*嘉运算*/NumB=FTopOperands;FPop Operands;if FIsEmptyOperands{/*错误处理*/PrintError=1;else{NumA=FTopOperands;FPop Operands;if NumA==0NumB0||NumA0NumB-intNumB!=0PrintError=1;else{answer=powNumA,NumB;FPush answer,Operands;break;case%:/*取模运算*/NumB=FTopOperands;FPopOperands;if FIsEmptyOperands{/*错误处理*/PrintError=1;else{NumA二FTopOperands;FPop Operands;if NumA-intNumA!=0||NumB-intNumB!=0||NumB==0PrintError=1;else{answer=intNumA%intNumB;/*x modb*/表达式求值概述1课程设计目的
1.
11.要求学生达到熟练掌握C语言的基本知识和技能
2.了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力
3.提高程序设计和调试能力学生通过上机实习,验证自己设计的算法的正确性学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改
4.培养算法分析能力分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平
5.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能课程设计内容
1.2设计一个表达式求值的程序该程序必须可以接受包含(,),+,-,*,/,%,和八(求幕运算符,a^b=ab)的中缀表达式,并求出结果如果表达式正确,则输出表达式的结果;如果表达式非法,则输出错误信息系统需求分析2系统目标
2.1利用栈设计一个程序,该程序能够用于表达式求值,程序将读入的中缀表达式转换为后缀表达式,然后读取后缀表达式,输出结果输入要求程序从“input.txt”文件中读取信息,在这个文件中如果有多个中缀表达式,则每个表达式独占一行,程序的读取操作在文件的结尾处停止输出要求对于每一个表达式,将其结果放在“output,txt”文件的每一行中这些结果可能是值(精确到小数点后两位),也可能是错误信息“ERROR ININFIX NOTATION主体功能
3.2能够处理以字符序列的形式输入的不含变量的实数表达式,正确处理负数与小数,判断表达式是否语法正确(包含分母不能为零的情况),正确实现对算术四则混合运算表达式的求值,能够将计算中遇到的问题和结果以文件的形式予以存储开发环境
4.3Microsoft VisualC++
6.0表达式求值FPushanswer,Operands;}break;case*:/*乘法运算*/NumB=FTopOperands;FPop Operands;if FIsEmptyOperands{PrintError=1;else{NumA=FTop Operands;FPop Operands;answer=NumA*NumB;/*x*y*/FPush answer,Operands;}Break;case:/*除法运算*/NumB=FTopOperands;FPop Operands;if FIsEmptyOperands{PrintError=1;else{NumA=FTop Operands;FPopOperands;if NumB==0{PrintError=1;/*分母不为0*/else{answer=float NumA/NumB;/*x/y*/FPushanswer,Operands;break;case/*加法运算*/NumB=FTopOperands;FPop Operands;if FIsEmptyOperands{PrintError=1;}else{NumA=FTopOperands;FPop Operands;/*x+y*/answer=NumA+NumB;FPush answer,Operands;}break;/*减法运算*/case-:NumB=FTopOperands;FPop Operands;if FIsEmptyOperands{PrintError=1;}else{NumA=FTopOperands;/*x-y*/FPop Operands;answer=NumA-NumB;FPush answer,Operands;}break;default:PrintError=1;break;Pop Whereat;if!PrintError{answer=FTop Operands;FPopOperands;if FIsEmptyOperands!=1{fprintf Change,z/Errorzz;/*如果还有操作数*/PrintError=0;}elsefprintf Change,〃%f〃,answer;else{fprintfChange,“Error;PrintError=0;FMakeEmptyOperands;free Operands;任务分配程序员主要任务负责算法设计,并完成源代码测试员主要任务负责设计测试用程序main,并对实验结果进行整理分析,最后完成实验报告的第五部分内容,即测试方案与测试结果部分文档员主要任务负责撰写实验报告的第
一、
二、三部分,即实验内容概述、系统需求分析和系统概要设计同时完成整个文档的整合,使整篇报告排版、文字风格统一实验报告完成日期:系统概要设计3系统的功能模块划分
4.
11.判断操作数的函数isnumO判断当前所指字符是否属于数字,是就返回“,不是就返回
02.求运算符优先级函数priority为了方便判断运算符优先级,先利用switch函数将不同的运算符返回不同的整型数字,在根据数字的大小判断优先级+优先级相同,返回数字相同,也是
3.表达式求值函数infix_value此函数是直接按照设计思路完成问题要求的函数,其中要调用到判断操作符的函数isnumO和求运算符优先级的函数priority循环结束弹出栈2的数值,并返回
4.主函数main定义一个数组存储表达式整个字符串,将返回的数值直接赋值到浮点型的result,输出resulto
5.两个栈的函数设计栈的初始化函数charInit_SeqStackInit_SeqStack栈判空Empty_SeqStack charEmpty_SeqStack入栈函数PushSeqStack charPush_SeqStack出栈函数Pop_SeqStack charPop_SeqStack取栈顶函数GetTop_SeqStack charGetTop_SeqStack销毁栈Destory_SeqStack charDestorySeqStack系统流程图
5.2开始优先级比较算法图系统流程图1系统详细设计
41.基本分析在计算机中,算术表达式的计算往往是通过使用栈来实现的所以,本表达式求值程序的最主要的数据结构就是栈可以使用栈来存储输入表达式的操作符和操作数输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子表达式求值是高级语言编译中的一个基本问题,是栈的典型应用实例任何一个表达式都是由操作数operand>运算符operator和界限符delimiter组成的操作数既可以是常数,也可以是被说明为变量或常量的标识符;运算符可以分为算术运算符、关系运算符和逻辑运算符三类;基本界限符有左右括号和表达式结束符等
2.中缀表达式求值中缀表达式每个二目运算符在两个运算量的中间,假设操作数是整型常数,运算符只含加、减、乘、除等四种运算符,界限符有左右括号和表达式起始、结束符“#,如#7+15*23-28/4#要对一个简单的算术表达式求值,首先要了解算术四则运算的规则,即1从左到右;2先乘除,后加减;3先括号内,后括号外运算符和界限符可统称为算符,它们构成的集合命名为OPSo根据上述三条运算规则,在运算过程中,任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一的优先权低于02的优先权等于020102,01的优先权高于02实现算符优先算法时需要使用两个工作栈一个称作perator,用以存放运算符;另一个称作perand,用以存放操作数或运算的中间结果算法的基本过程如下首先初始化操作数栈operand和运算符栈operator,并将表达式起始符“#压入运算符栈;依次读入表达式中的每个字符,若是操作数则直接进入操作数栈operand,若是运算符,则与运算符栈perator的栈顶运算符进行优先权比较,并做如下处理:1若栈顶运算符的优先级低于刚读入的运算符,则让刚读入的运算符进operator栈;2若栈顶运算符的优先级高于刚读入的运算符,则将栈顶运算符退栈,送入9,同时将操作数栈perand退栈两次,得到两个操作数a、b,对a、b进行运算后,将运算结果作为中间结果推入perand栈;3若栈顶运算符的优先级与刚读入的运算符的优先级相同,说明左右括号相遇,只需将栈顶运算符左括号退栈即可operator栈的栈顶元素和当前读入的字符均为“:T时,说明表达式起始符与表达式结束符相遇,整个表达式求解结束int ExpEvaluationO{/*读入一个简单算术表达式并计算其值*/InitStack operand;InitStackoperator;PushStackfeoperator,#;printf,z\n\n Pleaseinput anexpression Endingwith#;ch=getchar;/*读入表达式中的一个字符*/whilech!=#||GetTopoperator!={if!Inch,OPS/*判断ch是否运算符*/{a=GetNumber ch;/*用ch逐个读入操作数的各位数码,并转化为十进制数a*/PushStackoperand,a;}elseswitchCompareGetTopoperator,ch{case zz:PushStackoperator,ch;ch=getchar;break;case,=’:PopStackfeoperator,x;ch=getchar;break;case:PopStackoperator,op;PopStackoperand,b;PopStackoperand,a;v=Execute a,op,b;PushStackoperand,v;break;v=GetTopoperand;return v;}为了处理方便,编译程序常把中缀表达式首先转换成等价的后缀表达式,后缀表达式的运算符在运算对象之后在后缀表达式中,不再引入括号,所有的计算按运算符出现的顺序,严格从左向右进行,而不用再考虑运算规则和级别中缀表达式“a+b*c-d/e”的后缀表达式为:式bc*+de/-”
3.后缀表达式求值计算一个后缀表达式,算法上比计算一个中缀表达式简单的多这是因为表达式中即无括号又无优先级的约束具体做法只使用一个对象栈,当从左向右扫描表达式时,每遇到一个操作数就送入栈中保存,每遇到一个运算符就从栈中取出两个操作数进行当前的计算,然后把结果再入栈,直到整个表达式结束,这时送入栈顶的值就是结果下面是后缀表达式求值的算法,在下面的算法中假设,每个表达式是合乎语法的,并且假设后缀表达式已被存入一个足够大的字符数组A中,且以为结束字符,为了简化问题,限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换问题double calcul_expchar*A/*本函数返回由后缀表达式A表示的表达式运算结果*/{SeqStarck s;ch=*A++;InitStacks;whilech!=#{if ch!二运算符PushStack s,ch;else{PopStack s,a;PopStacks,b;/*取出两个运算量*/switch ch{case ch==,+c=a+b;break;case ch=-c=a-b;break;case ch=二’*c=a*b;break;case ch二/c二a/b;break;二’case ch%c=a%b;break;二二}c;PushStack s,}ch=*A++;PopStack s,resultreturn result;}
4.中缀表达式转换成后缀表达式将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似,但只需要运算符栈,遇到运算对象时直接放后缀表达式的存储区,假设中缀表达式本身合法且在字符数组A中,转换后的后缀表达式存储在字符数组B中具体做法遇到运算对象顺序向存储后缀表达式的B数组中存放,遇到运算符时类似于中缀表达式求值时对运算符的处理过程,但运算符出栈后不是进行相应的运算,而是将其送入B中存放读者不难写出算法,在此不再赘述程序的整体算法分两步第一步,从“input.txt”文件中读取中缀表达式,并应用运算符栈OpHolder把中缀表达式转换为后缀表达式,将输出结果存放在一个temp文件中第二步,从temp文件中读取中缀表达式,并应用操作栈Operands计算后缀表达式结果,将结果输出到output.txt”文件中测试
55.1测试方案设计针对程序的input.txt文件,并将运行结果与期望测试进行比较
5.2测试结果图一J——Desktop新建文件夹\Debcig\表达式求宜exe___________________表达式求值________________自动生成文件显下[11Out put.txt[2J Output文件结果显丁中的表达式-txt[3J Input.txt【】关于作者4返回课程设计总菜单E5]退出[0J请选择操作<〉0—5图
22.基本测试在input文件中输入表达式如下图2则输出结果如下图3Inputtxt-记事本Outputtxt-记事本文件F编后E格式0建文件F兼辑E格式0宣^
003.0000001+2+3-
42.0000001+
23.
0000004.99+
5.99+
6.99*
1.
0618.3893993*5*4+8«
20.0000002V
3256.000000225-
350535.164063-
8.0000002-4厂
32.扩展测试则输出结果如下图6在input文件中输入表达式如下图5记事本Output.txt-|Input.txt-记事本文件编辑格式亘看V|
2.F EO文件编辑格式查看智同800000F EO V-
19.90000095—34/9+1*
22.513-2+
5.6-190%3^271+
16.0000001+2+
36.0000001*2*
312.7044451+2*3+4/5+1*4+
3.
268.3000003+4-
6.7+
84.
4800002.9*
1.2+
0.5-4%3/2+旷5-5-
1.0000002-
36.
2500002.5”-
8.000000I2-4^3图6图5则输出结果如下图
83.容错测试在input文件中输入表达式如下图7。