数据结构课程设计 实验报告

数据结构课程设计实验报告题目：2.3表达式求值问题1.问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：2274—*3/11+）和前缀式（如：+11/*23—743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计本题中使用顺序栈用来存取运算符和运算数，顺序栈类的定义如下：//顺序栈类定义templateclassTclassSqStack{private:T*base;//栈底指针inttop;//栈顶intstacksize;//栈容量public:SqStack(intm);//构建函数~SqStack(){delete[]base;top=0;stacksize=0;}//析构函数voidPush(Tx);//入栈TPop();//出栈TGetTop();//获取栈顶元素intStackEmpty();//测栈空voidClearStack();//清空栈voidStackTop();//返回栈顶指针voidStackTranverse();//显示栈中元素};3.算法设计本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。（1）中缀表达式求值①首先定义了两个栈，分别用于存取运算符和运算数，如下：SqStackcharOP(20);SqStackdoubleOD(20);②然后依次读取表达式的一个字符C，如果C是运算数，入运算数栈OP.Push(C)；如果C是运算符，把它与栈顶元素的优先级比较：若“”:该运算符进栈，读入下一个字符，OP.Push(c)；若“=”:运算符退栈，消去一个括号读入下一个字符;若“”，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。这时需用到比较运算符优先级的函数：charPrecede(chart1,chart2)//算符的优先级比较重复上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果。算法如下：case'':OP.Push(c);//栈顶元素优先权低c=*exp++;break;case'=':x=OP.Pop();//脱括号并接收下一字符c=*exp++;break;case'':theta=OP.Pop();//退栈并将运算结果入栈if(theta=='('||theta==')'){cout表达式有误!;exit(0);}b=OD.Pop();if(b==0){cout表达式有误!endl;exit(0);}if(OD.StackEmpty()){cout表达式有误!endl;exit(0);}a=OD.Pop();OD.Push(Operate(a,theta,b));}（2）将中缀表达式转换为后缀表达式①从左向右读取表达式，读到运算数把它输出；②读到运算符f2，把运算符栈顶元素的算符优先级f1进行比较：若“f1f2”:该运算符入运算符栈；若“f1=f2”:从运算符栈退出一个运算符，不输出;若“f1f2”，从运算符栈退出一个运算符，从运算数栈里输出所有比f2优先级高的运算符，直至栈顶算符优先级小于f2，f2入运算符栈。具体算法如下：case'':OP.Push(c);//栈顶元素优先权低c=*exp++;break;case'=':x=OP.Pop();//脱括号并接收下一字符c=*exp++;break;case'':postexp[i++]=OP.Pop();break;//运算符出栈输出（3）将中缀表达式转换为前缀表达式①将中缀式入栈再依次从栈中读取元素：如果是操作数把它加入一个数组中;如果是运算符：若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素，则此运算符入栈；否则，栈顶运算符出栈并加入数组中；若是左括号，栈中元素逐个出栈加入数组中，直到遇到右括号。②最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到前缀式。部分算法如下：SqStackcharST(20);SqStackcharSP(20);SqStackcharOP(20);while(*exp!='=')//利用栈得到中缀式的逆序ST.Push(*exp++);while(!ST.StackEmpty()){x=ST.Pop();if((x='0'&&x='9')||x=='.'){s[j++]=x;}if(x==')')OP.Push(x);while((x=='+')||(x=='-')||(x=='*')||(x=='/')){s[j++]='';if(OP.StackEmpty()||OP.GetTop()==')'||Precede(x,OP.GetTop())==''||Precede(x,OP.GetTop())=='='){OP.Push(x);break;}elses[j++]=OP.Pop();}if(x=='('){while(OP.GetTop()!=')')s[j++]=OP.Pop();OP.Pop();}}while(!OP.StackEmpty()){s[j++]='';s[j++]=OP.Pop();}s[j]='\0';while(s[i]!='\0'){SP.Push(s[i++]);}while(!SP.StackEmpty())preexp[k++]=SP.Pop();//再次求逆序得到前缀式（4）后缀表达式求值①创建一个栈，作为运算数栈②读取表达式：若是运算数，入运算数栈；若是运算符，从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。③最后，栈顶元素即为表达式的值。具体算法如下：SqStackdoubleOD(20);c=*postexp++;while(c!='\0'){if((c='0'&&c='9')||c=='.')//为操作数{i=0;do{z[i++]=c;c=*postexp++;}while(c='0'&&c='9'||c=='.');z[i]='\0';d=atof(z);//将字符串数组转为浮点型存于dOD.Push(d);}if(In(c))//c为运算符{b=OD.Pop();//退出两个运算数运算a=OD.Pop();OD.Push(Operate(a,c,b));c=*postexp++;}c=*postexp++;}v=OD.Pop();（5）前缀表达式求值①创建栈ST和栈OD用于存取表达式逆序和运算数，利用栈得到前缀表达式的逆序存入栈ST；②栈ST出栈，为X:若X是运算数，则把X存入数组，直至X不是运算数；若X是运算符，则从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。③最后，栈顶元素即为表达式的值。具体算法如下：SqStackcharST(20);SqStackdoubleOD(20);while(*preexp!='\0'){ST.Push(*preexp++);//利用栈得到前缀表达式的逆序}while(!ST.StackEmpty()){x=ST.Pop();if((x='0'&&x='9')||x=='.'){k=0;do{z[k++]=x;x=ST.Pop();}while((x='0'&&x='9')||x=='.');k--;for(p=0;k=0;p++,k--)s[p]=z[k];d=atof(s);OD.Push(d);}if(In(x)){a=OD.Pop();b=OD.Pop();OD.Push(Operate(a,x,b));}}v=OD.Pop();returnv;}（6）界面设计程序包含多个功能，所以，采用菜单，以方便用户进行功能选择。菜单如下：//显示主菜单cout--------*主菜单*-------\n;cout1-创建表达式\n;cout2-表达式求值\n;cout3-求后缀表达式\n;cout4-后缀表达式求值\n;cout5-求前缀表达式\n;cout6-前缀表达式求值\n;cout7-显示表达式\n;cout8-退出\n;coutEnterchoice:;4.运行与测试（1）运行程序，显示菜单，如下图所示：（2）按“1”创建表达式。根据提示，输入表达式，如下图所示：（3）按“2”表达式求值。（4）按“3”求后缀表达式。（5）按“4”求后缀表达式的值。（6）按“5”求前缀表达式。（7）按“6”求前缀表达式的值。（8）按“7”求显示中缀表达式。（9）按“1”和“2”，输入一个错误的表达式，程序会判断表达式错误。（10）按“8”退出。5.调试记录及收获（1）学会理解运用栈的结构，使用栈的“先进后出”的特点；（2）前缀和后缀的变换借助于栈实现，理解前缀、中缀、后缀的不同之处；（3）调试程序要细致耐心，当程序的功能较多时，要仔细测试程序的每一个功能，发现错误要及时查错修改，不断完善程序。7.源程序#includeiostreamusingnamespacestd;//顺序栈类定义templateclassTclassSqStack{private:T*base;//栈底指针inttop;//栈顶intstacksize;//栈容量public:SqStack(intm);//构建函数~SqStack(){delete[]base;top=0;stacksize=0;}//析构函数voidPush(Tx);//入栈TPop();//出栈TGetTop();//获取栈顶元素intStackEmpty();//测栈空voidClearStack();//清空栈voidStackTop();//返回栈顶指针voidStackTranverse();//显示栈中元素};//顺序栈类实现templateclassTSqStackT::SqStack(intm)//创建一个空栈{base=newT[m];if(base==NULL){cout栈创建失败，退出!endl;exit(1);}stacksize=m;top=-1;}templateclassTvoidSqStackT::Push(Tx)//入栈操作{if(top==stacksize-1)throw栈满，无法入栈;top++;base[top]=x;//couttop：topendl;}templateclassTTSqStackT::Pop()//出栈操作{Tx;if(top==-1)throw栈空，不能出栈;x=base[top--];//couttop：topendl;returnx;}templateclassT//获取栈顶元素TSqStackT::GetTop(){if(top==-1)throw栈空，栈顶无元素;//couttop：topendl;returnbase[top];}templateclassTintSqStackT::StackEmpty()//测栈空{if(top==-1)return1;elsereturn0;}templateclassTvoidSqStackT::ClearStack()//清空栈{top=-1;}templateclassTvoidSqStackT::StackTop()////返回栈顶指针{cout栈顶top=top;}templateclassTvoidSqStackT::StackTranverse()//输出栈中元素{inti=top;while(i=0)coutbase[i--]'\t';c