《带括号算术表达式的计算》实验报告

四川大学数据结构与算法分析实验报告实验名称：带括号的算术表达式求值指导老师：________孙界平________学院：_______软件学院_______专业：_______软件工程_______姓名：________马健________学号：_____2013141463026____班级：________5班________日期：___2014年10月24日___带括号的算术表达式求值2/16目录一实验题目................................................................3二实验目的和要求......................................................3三实验环境................................................................3四算法描述................................................................3五源程序清单........................................................附录六运行结果................................................................6七实验运行情况分析...................................................7带括号的算术表达式求值3/16一、实验题目:带括号的算术表达式求值二、实验目的和要求:采用算符优先数算法,能正确求值表达式;熟练掌握栈的应用;熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C程序;上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:硬件环境:联想笔记本电脑软件环境:操作系统:windows7旗舰版编译软件:VisualC++6.0四、算法描述:程序框图否开始判断表达式是否正确从键盘读入算术表达式存入单链表中是用栈计算显示算数表达式是是否继续计算？显示错误信息否带括号的算术表达式求值4/16文字解释:1.用户从键盘读入算术中缀表达式，以”=”结尾;2.程序判断用户输入表达式是否正确;3.若表达式正确，则用栈计算算术表达式;4.打印输出计算过程和最终结果;5.程序询问用户是否继续计算;6.若继续，则执行第1步;若否定，则退出程序7.若表达式错误，则打印错误信息，提示用户重新输入8.返回第1步;函数及结构说明:结构体:1)存储算数表达式的单链表:structExpression{charsign;structExpression*next;};2)操作符和操作数栈:typedefstruct{char*top;char*bottom;intstack_size;}Stack;构造函数:1)栈相关操作函数:①初始化空栈intStackCreate(Stack*s);②入栈操作intPUSH(Stack*s,charc);③出栈操作intPOP(Stack*s,charc);④获取栈顶元素charGetTop(Stack*s);带括号的算术表达式求值5/162)计算相关操作函数:①利用栈计算算术表达式intCalculate(structExpression*exp);②子式的值的计算intCount(charnum1,charsign,charnum2);③判断字符是否为运算符intIsOpOrNum(charc);④判断运算符优先级charJudgeLevel(charc1,charc2);⑤判断表达式正确性intIsExpresiion(structExpression*exp);⑥输出计算结果voidPrintResult(structExpression*exp,intresult);3)算术表达式输入函数:①键盘读入存于单链表structExpression*GetExp();构造操作符优先级表+-*/()=(#)+-*/(=)=(#)=五、源程序清单见附录六、运行结果测试表本次测试采用用户从键盘输入算数表达式，共进行16组测试序号测试功能测试内容输入项预期输出实际输出结果符号2符号1比较带括号的算术表达式求值6/161基本计算操作单括号运算2*(3+4)+5*3=2929通过2基本计算操作多括号运算3+((4+3)*6)/3=1717通过3基本计算操作不能除整运算6*(2+(3/2))=2118有误差4基本计算操作不能除整运算(1+2+3)/4=1.51有误差5式子正误判断括号不匹配1+(1+3*2=输出错误信息输出错误信息通过6式子正误判断计算符多余1++2*3+6=输出错误信息输出错误信息通过7式子正误判断含非计算符x+y*z+w=输出错误信息输出错误信息通过8式子正误判断未输入”=”1+2*377通过9容错能力除数为02+3/0=输出除数为0输出除数为0通过10容错能力自动去空格1+2*(3+4)=1515通过11容错能力“=”输为”#”2*(3+2)#1010通过12拓展功能多位正数计算10*(2+13)=150输出错误信息未通过13拓展功能负数计算4+3*(-4)+5=-3输出错误信息未通过15拓展功能小数计算1+10*0.1/2=6输出错误信息未通过16全体测试最终测试2*(4–(3+3))+3#-1-1通过部分运行截图基本计算操作带括号的算术表达式求值7/16式子正误判断容错能力全体测试多括号运算(2)不能整除运算(3)带括号的算术表达式求值8/16七、实验运行情况分析优点:用户输入格式较为自由。增添了一些能想到的容错系统，如用户未输入”=”，或是用户将”=”错输成”#”，或是用户在字符间输入空格，程序都会智能识别出正确的算数表达式，计算正确答案。防错报错系统较为完善。多方面考虑输入方面的错误，如括号不匹配、计算符少输多输、输入非计算符等方面均考虑，并提示用户错误信息，便于用户检查输入状况。存储方式较为规范。采用单链表存储用户输入的算术表达式，更加清晰简单,头结点存储表达式中符号的个数，方便在必要的时候统计对照最终结果的正确性。缺点:只能实现数字之间的四则运算，不能实现其他算数功能如平方，开方等。仅仅局限于个位数之间的运算，无法运算两位数或两位以上数字的运算。计算数字只能为0-9的整数，无法对负数或者小数进行计算。在除法中若遇到无法除尽的结果，只能保留其整数部分，造成最终结果跟预期结果存在误差由于控制台系统的限制，与用户交互性较差，界面太过简单单调。感受:带括号的算术表达式求值9/16通过本次“带括号算数表达式的计算”实验，我不光复习了之前学习的单链表的相关知识并加以采用，而且还巩固了有关于栈的相关操作；在实现题目要求基本功能的基础上，还增加拓展了一些内容。在为期两周的实验中，从刚开始的整理思路，到接下里的编写代码，到最后的填写实验报告，都是我自己一步步完成。唯独可惜的是，由于知识掌握不够全面，导致只能实现最基本的功能，无法进行进一步的扩展和完善，致使用户输入一些运算式未得到预期的结构，这是比较遗憾的方面。附录(源程序代码)/**实验一：带括号的算数表达式求值*实现：栈*语言：C*作者：马健*/#includestdio.h#includestdlib.h#includeconio.h#defineSTACK_SIZE_FIRST100//栈的初始空间大小#defineSTACK_SIZE_INCREASE20//栈的增加空间大小/*---------------------------------算术表达式单链表----------------------------------*/structExpression{charsign;structExpression*next;};/*---------------------------------操作符和操作数栈----------------------------------*/typedefstruct{char*top;char*bottom;intstack_size;//栈的空间大小}Stack;structExpression*GetExp();//键盘读入表达式存入单链表/*---------------------------------栈相关的操作函数-----------------------------------*/intStackCreate(Stack*s);//初始化一个空栈函数intPUSH(Stack*s,charc);//入栈函数intPOP(Stack*s,charc);//出栈函数charGetTop(Stack*s);//取出栈顶元素/*---------------------------------计算相关操作函数----------------------------------*/intCalculate(structExpression*exp);//带括号的算数表达式计算函数intCount(charnum1,charsign,charnum2);//两个数的计算intIsOpOrNum(charc);//判断一个字符是不是运算符带括号的算术表达式求值10/16charJudgeLevel(charc1,charc2);//判断两运算符优先级voidPrintResult(structExpression*exp,intresult);//打印最终结果intIsExpresiion(structExpression*exp);//判断是否为正确的算术表达式voidmain(){structExpression*head;intResult=0;//定义最终计算结果inttemp=0;//定义循环参数charselect;while(temp==0){head=GetExp();//创建算术表达式单链表if(IsExpresiion(head)==0||head==NULL)//算术表达式错误，重新输入{printf(算术表达式错误，请认真检查并重新输入);getch();system(cls);}else{Result=Calculate(head);//计算算术表达式PrintResult(head,Result);//输出最终计算结果printf(是否继续计算?是(y)否(n)\n);//是否继续select=getch();if(select=='n'||select=='N')temp=1;elsesystem(cls);}}}//读入算术表达式并存储于链表structExpression*GetExp(){printf(\t带括号的算术表达式求值\n);printf(请输入需要计算的算数表达式:(以'='结尾)\n);charc;intnumber=0;structExpression*head=NULL,*p1,*p2,*first=NULL;//定义指针变量head=(structExpression*)malloc(sizeof(structExpression));while((c=getchar())!='\n'){if(c!='')//若出现空格,自动删除{p1=(structExpression*)malloc(sizeof(structExpression));if(c=='=')c='#';p1-sign=c;if(first==NULL)first=p1;else带括号的算术表达式求值11/16p2-next=p1;p2=p1;number++;}}if(p2-sign!='#')//若未输入'=',则自动补齐{p1=(