《数据结构课程设计》表达式求值实验报告

实验课程名称 专业班级学生姓名学号指导教师20至20学年第学期第至周算术表达式求值演示概述数据结构课程设计•要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面•加深对课程基本内容的理解。同时•在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一•也是栈的应用的一个典型例子。设计一个程序•演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性.以便在解决实际问题中灵活运用它们.同时加深对这种结构的理解和认识。二、系统分析以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的算符优先关系•实现对算术四则混合运算表达式的求值•并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。一般来说•计算机解决一个具体问题时.需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型•然后设计一个解决此数学模型的算法•最后编出程序•进行测试.调试直至得到想要的答案。对于算术表达式这个程序•主要利用栈•把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法.可以使用两个栈•一个用以寄存运算符•另一个用以寄存操作数和运算结果。演示程序是以用户于计算机的对话方式执行•这需要一个模块来完成使用者与计算机语言的转化。程序执行时的命令：本程序为了使用具体•采用菜单式的方式来完成程序的演示•几乎不用输入什么特殊的命令•只需按提示输入表达式即可。（要注意输入时格式•否者可能会引起一些错误）测试数据。三、概要设计一个算术表达式中除了括号、界限符外•还包括运算数据和运算符。由于运算符有优先级别之差.所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的.这与栈的特性相吻合•故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。算法设计程序包含三个模块主程序模块•其中主函数为voidmain{输入表达式；根据要求进行转换并求值；输出结果；}表达式求值模块——实现具体求值。表达式转换模块——实现转换。各个函数之间的调用关系栈的抽象数据类型定义ADTSqStack{数据对象：D={a|aWEIemSet,i二1,2,3 .n,n$O}TOC\o"1-5"\h\zi i数据关系：R1={<a,a>|a,aWD,i=1,2,3,…….n}i-1i i-1i约定其中a端为栈底.a端为栈顶。i n操作集合：voidInitStack1(SqStackl&S1);//声明栈建立函数voidInitStack2(SqStack2&S2);//声明栈建立函数voidevaluate(SqStack1&S1,SqStack2&S2)；//确定如何入栈函数voidPush1(SqStack1&S1,chare);//声明入栈函数voidPush2(SqStack2&S2,floate);//声明入压栈函数charGetTop1(SqStack1&S1);//声明取栈顶元素函数floatGetTop2(SqStack2&S2);//声明取栈顶元素函数charPop1(SqStack1&S1);//声明出栈函数floatPop2(SqStack2&S2);//声明出栈函数charCompare(charm,charn);//声明比较函数floatOperate(floata,charrheta,floatb);//声明运算函数voidDispStack1(SqStack1&S1);//从栈底到栈顶依次输出各元素voidDispStack2(SqStack2&S2);//从栈底到栈顶依次输出各元素}ADTSqStack结构分析：栈中的数据节点是通过数组来存储的。因为在C语言中数组是用下标从零开始的.因此我们在调用他们的数据是要特别注意。指针变量的值要么为空(NULL)•不指向任何结点；要么其值为非空.即它的值是一个结点的存储地址。注意.当P为空值时•则它不指向任何结点•此时不能通过P来访问结点•否则会引起程序错误。如果输入的数字不符合题目要求则会产生错误结果。算法的时空分析：时间和空间性能分析：时间上•对于含n个字符的表达式•无论是对其进行合法性检测还是对其进行入栈出栈操作n次.因此其时间复杂度为O(n)。空间上.由于是用数组来存储输入的表达式.用栈来存储运算中的数据和运算符.而栈的本质也用到的数组•数组在定义时必须确定其大小。在不知表达式长度的情况下确定数组的长度确非易事•此时极易造成空间的浪费.因此空间性能不是很好。四、详细设计源程序#include<iostream>usingnamespacestd;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct//运算符栈{char*base;char*top;intstacksize;}SqStack1;typedefstruct//运算数栈{float*base;float*top;intstacksize;}SqStack2；voidInitStack1(SqStack1&S1);//声明栈建立函数voidInitStack2(SqStack2&S2);//声明栈建立函数voidevaluate(SqStack1&S1,SqStack2&S2)；//确定如何入栈函数voidPush1(SqStack1&S1,chare);//声明入栈函数voidPush2(SqStack2&S2,floate);//声明入压栈函数charGetTop1(SqStack1&S1);//声明取栈顶元素函数floatGetTop2(SqStack2&S2);//声明取栈顶元素函数charPop1(SqStack1&S1);//声明出栈函数floatPop2(SqStack2&S2);//声明出栈函数charCompare(charm,charn);//声明比较函数floatOperate(floata,charrheta,floatb);//声明运算函数voidDispStack1(SqStack1&S1);//从栈底到栈顶依次输出各元素voidDispStack2(SqStack2&S2);//从栈底到栈顶依次输出各元素/*主函数*/voidmain(){SqStack1S1;//定义运算符栈SqStack2S2;//定义运算数栈//freopen("data1.in","r",stdin);//freopen("data1.out","w",stdout);InitStack1(S1);//调用栈建立函数InitStack2(S2)；//调用栈建立函数evaluate(S1,S2)；//调用确定如何入栈函数cout<<"按任意键结束！"<<endl;}/*运算符栈函数*/voidInitStack1(SqStack1&S1)//构造一个空栈S1{S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S1.base)cout<<"存储分配失败！"；//存储分配失败S1.top二S1.base;S1.stacksize二STACK_INIT_SIZE;}voidPush1(SqStackl&S1,chare)//入栈{if(S1.top-S1.base>二S1.stacksize)//如果栈满.追加存储空间{S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base) cout<<"存储分配失败！"；else{S1.top二S1.base+S1.stacksize;S1.stacksize二S1.stacksize+STACKINCREMENT;}}*S1.top二e;S1.top=S1.top+1;//将元素压入栈中.指针上移}charGetTop1(SqStackl&S1)//取栈顶元素{chare;if(S1.top二二S1.base)cout<<"\n\t\t\t运算符栈已空！\n";elsee=*(S1.topT);returne;}voidDispStack1(SqStackl&S1)//从栈底到栈顶依次输出各元素{chare,*p;if(S1.top二二S1.base)cout<<"”；else{p二Sl.base;while(p<S1.top){e=*p;P++；cout<<e;}}}charPop1(SqStackl&S1)//出栈{chare;if(S1.top二二S1.base)cout<<"\n\t\t\t运算符栈已空！\n";e=*(一S1.top);returne;}/*运算数栈函数*/voidInitStack2(SqStack2&S2)//构造一个空栈S2{S2.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));if(!S2.base)cout<<"存储分配失败！"；//存储分配失败S2.top二S2.base;S2.stacksize二STACK_INIT_SIZE;}voidPush2(SqStack2&S2,floate)//入栈{if(S2.top-S2.base>二S2.stacksize)//栈满.追加存储空间{S2.base=(float*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));if(!S2.base)cout<<"存储分配失败！"；else{S2.top=S2.base+S2.stacksize;S2.stacksize二S2.stacksize+STACKINCREMENT;}}*S2.top二e;S2.top=S2.top+1;//将元素e入栈.指针上移}voidDispStack2(SqStack2&S2)//从栈底到栈顶依次输出各元素{floate,*p;if(S2.top二二S2.base)cout<<"”；elsep二S2.base;while(p<S2.top){e=*p;P++；cout<<e;}}}floatGetTop2(SqStack2&S2)//取栈顶元素{floate;if(S2.top==S2.base)cout<<"\n\t\t运算数栈已空！"；elsee=*(S2.top-1);returne;}floatPop2(SqStack2&S2)//出栈{floate;if(S2.top==S2.base)cout<<"\n\t\t运算数栈已空！"；e=*(一S2.top);returne;}/*确定如何入栈函数*/voidevaluate(SqStack1&S1,SqStack2&S2){charc;floatt,e;intn=O,i=1,j=O,k=O,l=O；charch[STACK_INIT_SIZE];ints—1;intflag=0,flag2=0；floatp1,p2；charch1;Push1(S1,'#');//将'#'入栈•作为低级运算符cout<<"・请输入不含变量的表达式(以#结束！)：\n";cin>>ch;c=ch[0];cout<<"\n•对表达式求值的操作过程如下："<<"\n __\n"<<"步骤\t运算符栈S1\t运算数栈S2\t输入字符\t\t主要操作"；while(c!='#'||GetTop1(S1)!='#')cout<<"\n \n";cout<<i++<<"\t";DispStack1(S1);cout<<"\t\t";DispStack2(S2)；cout<<"\t\t";if(flag==1){k——;flag=0;}if(flag2){k+=flag2;flag2=0；}for(l=0;l<k;l++)cout<<'';for(j=k;ch[j]!='\0';j++)cout<<ch[j];if(ch[k]!二’#'&&flag!=1){k++；flag=0；}as:if(!(c二二'+'||c二二'—’||c二二'*'||c二二'/'||c二二’(’||c二二’)’||c二二'#')){//输入的字符如果不是运算符号•则继续输入直到输入的是运算符为止•将非运算符转换成浮点数if(!(c二二'.')&&・>二0){e二float(c—48);n++;if(n=1)t；e;elseif(n>1)t二t*10+e;c=ch[s++];}if(n=-1){e=float(c—48);t二t+e/10;c=ch[s++];}if(c='.'){・二—1；c=ch[s++];}if((c>二'O'&&c<='9')||c二二'.'){flag2++；gotoas;}if(c<'0'||c>9){Push2(S2,t);}cout<<"\t\tPush2(S2,"<<t<<")";}else//输入的是运算符{n=0;//非运算型数据计数器清零switch(Compare(GetTop1(S1),c))//比较运算符的优先级{case'<'://栈顶元素优先级低.则入栈且继续输入Push1(S1,c);cout<<"\t\tPush1(S1,"<<c<<")";c=ch[s++];break;case'='://栈顶元素优先级相等•脱括号并接收下一字符Pop1(S1);cout<<"\t\tPop1(S1)";c=ch[s++];break;case'>'://栈顶元素优先级高•则退栈并将运算结果入栈p仁Pop2(S2);p2=Pop2(S2);ch仁Pop1(S1);Push2(S2,Operate(p2,ch1,p1));cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';flag=1;break;}}}cout<<"\n \n";cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";for(j=0;j<k;j++)cout<<'';cout<<"#"<<"\t\t"<<"RETURN(GETT0P(S2))"；cout<<"\n \n";if(S2.top-1二二S2.base)//显示表达式最终结果cout<<"\n•表达式的结果为："<<GetTop2(S2)<<endl;elsecout<<"\n表达式出错!\n";}charCompare（charm,charn）//运算符的优先级比较{if（n二二'+'||n二二'一'）//输入符号为"+"、"-"{if（m二二’（’||m二二'#'）return'<';//栈顶元素为"（"、"#",此时栈顶符号优先级低•返回"<"elsereturn'>';//否则.栈顶符号优先级高，返回">"}elseif（n二二'*'||n二二'/'）//输入的符号为"*"、"/"{if（m二二'）’||m二二'*'||m二二'/'）return'>';//栈顶元素为"）"、"*"、"/",此时栈顶符号优先级高•返回">"elsereturn'<';//否则.栈顶符号优先级低，返回"<"}elseif（n二二’（'）return'<';//输入的符号为"（"，则直接返回"<"elseif（n二二'）’）//输入的符号为"）"{if（m二二’（'）return'二’；//栈顶元素为"（"，此时优先级同•返回"二"elsereturn'>';//否则.栈顶符号优先级高，返回">"}else //输入符号为其他{if（m二二'#'）return'二’；//栈顶元素为"#",此时优先级同•返回"二"elsereturn'>';//否则.栈顶符号优先级高，返回">"}}floatOperate（floata,chartheta,floatb）//运算函数{floattmp=0;if （theta二二'+'）tmp二a+b;//从运算符栈取出的符号为"+".则运算数栈的两元素相加.并返回elseif（theta二二'-'）tmp二a-b;//从运算符栈取出的符号为"-".