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

数据结构课程设计 实验报告题目：2.3 表达式求值问题1. 问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 *3/11 +）和前缀式（如：+ 11/*237 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2. 数据结构设计本题中使用顺序栈用来存取运算符和运算数，顺序栈类的定义如下：/顺序栈类定义template <class T> class SqStackprivate:T *base;/栈底指针int top;/栈顶int stacksize;/栈容量public:SqStack(int m);/构建函数SqStack()delete base;top=0;stacksize=0;/析构函数void Push(T x);/入栈T Pop();/出栈T GetTop();/获取栈顶元素int StackEmpty();/测栈空void ClearStack();/清空栈void StackTop();/返回栈顶指针void StackTranverse();/显示栈中元素;3. 算法设计本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。（1） 中缀表达式求值首先定义了两个栈，分别用于存取运算符和运算数，如下：SqStack<char> OP(20); SqStack<double>OD(20);然后依次读取表达式的一个字符C，如果C是运算数，入运算数栈OP.Push(C)；如果C是运算符，把它与栈顶元素的优先级比较：若“<”:该运算符进栈，读入下一个字符，OP.Push(c)；若“=”:运算符退栈，消去一个括号读入下一个字符;若“>”，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。这时需用到比较运算符优先级的函数：char Precede(char t1,char t2) /算符的优先级比较重复上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果。算法如下： 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进行比较：若“f1<f2”:该运算符入运算符栈；若“f1=f2”:从运算符栈退出一个运算符，不输出;若“f1>f2”，从运算符栈退出一个运算符，从运算数栈里输出所有比f2优先级高的运算符，直至栈顶算符优先级小于f2，f2入运算符栈。具体算法如下：case'<':OP.Push(c); / 栈顶元素优先权低 c=*exp+;break;case'=':x=OP.Pop(); / 脱括号并接收下一字符 c=*exp+;break;case'>':postexpi+=OP.Pop();break; / 运算符出栈输出（3）将中缀表达式转换为前缀表达式将中缀式入栈再依次从栈中读取元素：如果是操作数把它加入一个数组中;如果是运算符：若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素，则此运算符入栈；否则，栈顶运算符出栈并加入数组中；若是左括号，栈中元素逐个出栈加入数组中，直到遇到右括号。最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到前缀式。 部分算法如下：SqStack<char>ST(20);SqStack<char>SP(20);SqStack<char>OP(20);while(*exp!='=') /利用栈得到中缀式的逆序ST.Push(*exp+);while(!ST.StackEmpty()x=ST.Pop();if(x>='0'&&x<='9')|x='.')sj+=x;if(x=')')OP.Push(x);while(x='+')|(x='-')|(x='*')|(x='/')sj+=' 'if(OP.StackEmpty()|OP.GetTop()=')'|Precede(x,OP.GetTop()='>'|Precede(x,OP.GetTop()='=')OP.Push(x);break;elsesj+=OP.Pop();if(x='(')while(OP.GetTop()!=')')sj+=OP.Pop();OP.Pop();while(!OP.StackEmpty()sj+=' 'sj+=OP.Pop();sj='0'while(si!='0')SP.Push(si+);while(!SP.StackEmpty()preexpk+=SP.Pop(); /再次求逆序得到前缀式（4）后缀表达式求值创建一个栈，作为运算数栈读取表达式： 若是运算数，入运算数栈； 若是运算符，从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。最后，栈顶元素即为表达式的值。具体算法如下：SqStack<double> OD(20);c=*postexp+;while(c!='0')if(c>='0'&&c<='9')|c='.')/为操作数i=0;dozi+=c;c=*postexp+;while(c>='0'&&c<='9'|c='.');zi='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是运算符，则从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。最后，栈顶元素即为表达式的值。具体算法如下：SqStack<char>ST(20); SqStack<double>OD(20);while(*preexp!='0')ST.Push(*preexp+); / 利用栈得到前缀表达式的逆序while(!ST.StackEmpty()x=ST.Pop();if(x>='0'&&x<='9')|x='.')k=0;do zk+=x; x=ST.Pop();while(x>='0'&&x<='9')|x='.'); k-;for(p=0;k>=0;p+,k-)sp=zk;d=atof(s);OD.Push(d);if(In(x)a=OD.Pop();b=OD.Pop();OD.Push(Operate(a,x,b);v=OD.Pop();return v;（6）界面设计程序包含多个功能，所以，采用菜单，以方便用户进行功能选择。菜单如下：/显示主菜单cout<<"-* 主 菜 单 *-n"cout<<" 1-创建表达式n"cout<<" 2-表达式求值n"cout<<" 3-求后缀表达式n"cout<<" 4-后缀表达式求值n"cout<<" 5-求前缀表达式n"cout<<" 6-前缀表达式求值n" cout<<" 7-显示表达式n"cout<<" 8-退出n"cout<<"Enter choice:"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.源程序#include<iostream>using namespace std;/顺序栈类定义template <class T> class SqStackprivate:T *base;/栈底指针int top;/栈顶int stacksize;/栈容量public:SqStack(int m);/构建函数SqStack()delete base;top=0;stacksize=0;/析构函数void Push(T x);/入栈T Pop();/出栈T GetTop();/获取栈顶元素int StackEmpty();/测栈空void ClearStack();/清空栈void StackTop();/返回栈顶指针void StackTranverse();/显示栈中元素;/顺序栈类实现template <class T>SqStack<T>:SqStack(int m) /创建一个空栈base=new Tm;if(base=NULL) cout<<"栈创建失败，退出!"<<endl;exit(1);stacksize=m;top=-1;template <class T>void SqStack<T>:Push(T x) /入栈操作if(top=stacksize-1) throw "栈满，无法入栈"top+;basetop=x;/cout<<"top："<<top<<endl;template <class T>T SqStack<T>:Pop() /出栈操作T x;if(top=-1) throw "栈空，不能出栈"x=basetop-;/cout<<"top："<<top<<endl;return x;template <class T> /获取栈顶元素T SqStack<T>:GetTop()if(top=-1) throw "栈空，栈顶无元素"/cout<<"top："<<top<<endl;return basetop;template <class T>int SqStack<T>:StackEmpty() /测栈空if(top=-1) return 1;elsereturn 0;template <class T>void SqStack<T>:ClearStack() /清空栈top=-1;template <class T>void SqStack<T>:StackTop() /返回栈顶指针cout<<"栈顶top= "<<top;template <class T>void SqStack<T>:StackTranverse() /输出栈中元素int i=top; while(i>=0) cout<<basei-<<'t' cout<<endl; char pause;char Precede(char t1,char t2) /算符的优先级比较 char f; switch(t2) case '+': case '-':if(t1='('|t1='=') f='<' else f='>' break; case '*': case '/':if(t1='*'|t1='/'|t1=')') f='>' else f='<' break; case '(':if(t1=')') cout<<"表达式有误!"<<endl; exit(0); else f='<' break; case ')':switch(t1) case '(':f='=' break; case '=':cout<<"表达式有误!"<<endl; exit(0); default: f='>' break; case '=':switch(t1) case '=':f='=' break; case '(':cout<<"表达式有误!"<<endl; exit(0); default: f='>' return f; int In(char c) / 判断c是否为运算符 switch(c) case'+': case'-': case'*': case'/': case'(': case')': case'=':return 1; default:return 0; double Operate(double a,char theta,double b) /进行一次运算 double c; switch(theta) case'+':c=a+b;break; case'-':c=a-b;break; case'*':c=a*b;break; case'/':c=a/b;break; return c; double Val_Exp(char *exp) /中缀表达式求值 SqStack<char> OP(20);/建立容量为20的运算符栈 SqStack<double> OD(20);/建立容量为20的运算数栈 char theta; double a,b,d; char c,x; / 存放由键盘接收的字符 char z6; / 存放符点数字符串 int i; OP.Push('='); / =是表达式结束标志 c=*exp+; /每次从表达式中读取一个字符 x=OP.GetTop(); while(c!='='|x!='=') if(In(c) / 是7种运算符之一 switch(Precede(x,c) 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); else if(c>='0'&&c<='9'|c='.') / c是操作数 i=0; do zi=c; i+; c=*exp+; while(c>='0'&&c<='9'|c='.'); zi='0' d=atof(z); / 将字符串数组转为符点型存于d OD.Push(d); else / c是非法字符 cout<<"表达式有误!"<<endl; exit(0); x=OP.GetTop(); d=OD.GetTop(); return d; void CreatePreExp(char * exp,char * &preexp) /由中缀式求前缀式 char x;char s20;int j=0,i=0,k=0;SqStack<char>ST(20);SqStack<char>SP(20);SqStack<char>OP(20);while(*exp!='=') /利用栈得到中缀式的逆序ST.Push(*exp+);while(!ST.StackEmpty()x=ST.Pop();if(x>='0'&&x<='9')|x='.')sj+=x;if(x=')')OP.Push(x);while(x='+')|(x='-')|(x='*')|(x='/')sj+=' 'if(OP.StackEmpty()|OP.GetTop()=')'|Precede(x,OP.GetTop()='>'|Precede(x,OP.GetTop()='=')OP.Push(x);break;elsesj+=OP.Pop();if(x='(')while(OP.GetTop()!=')')sj+=OP.Pop();OP.Pop();while(!OP.StackEmpty()sj+=' 'sj+=OP.Pop();sj='0'while(si!='0')SP.Push(si+);while(!SP.StackEmpty()preexpk+=SP.Pop(); /再次求逆序得到前缀式preexpk='0'cout<<"前缀表达式为:"<<preexp<<endl;void CreatePostExp(char * exp,char * &postexp) /由中缀式求后缀式char c,x;int i=0;SqStack<char> OP(20);OP.Push('='); / =是表达式结束标志c=*exp+;while(c)if(c>='0'&&c<='9')|c='.')postexpi+=c;c=*exp+;if(In(c) / 是7种运算符之一postexpi+=' ' x=OP.GetTop();switch(Precede(x,c)case'<':OP.Push(c); / 栈顶元素优先权低 c=*exp+; break; case'=':x=OP.Pop(); / 脱括号并接收下一字符 c=*exp+; break; case'>':postexpi+=OP.Pop(); / 运算符出栈输出 break;postexpi='0'/whilecout<<"后缀表达式为:"<<postexp<<endl;double Val_PostExp(char *postexp) /后缀表达式求值int i;char z6;double v=0,d=0,a,b;char c;SqStack<double> OD(20);c=*postexp+;while(c!='0')if(c>='0'&&c<='9')|c='.')/为操作数i=0;dozi+=c;c=*postexp+;while(c>='0'&&c<='9'|c='.');zi='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 ();return v;double Val_PreExp(char * preexp) /前缀表达式求值int k,p=0;char z6,s6;char x;double v,d=0,a,b;SqStack<char>ST(20); SqStack<double>OD(20);while(*preexp!='0')ST.Push(*preexp+); / 利用栈得到前缀表达式的逆序while(!ST.StackEmpty()x=ST.Pop();if(x>='0'&&x<='9')|x='.')k=0;do zk+=x; x=ST.Pop();while(x>='0'&&x<='9')|x='.'); k-;for(p=0;k>=0;p+,k-)sp=zk;d=atof(s);OD.Push(d);if(In(x)a=OD.Pop();b=OD.Pop();OD.Push(Operate(a,x,b);v=OD.Pop();return v; /主函数void main() char exp20;/="(2.2+5)+4*(5-3.1)="char *postexp,*preexp;postexp=new char20; preexp=new char20;*postexp='0'*preexp='0'double v1,v2;system("cls");/执行系统命令cls，清屏int choice; do/显示主菜单cout<<"-* 主 菜 单 *-n"cout<<" 1-创建表达式n"cout<<" 2-表达式求值n"cout<<" 3-求后缀表达式n"cout<<" 4-后缀表达式求值n"cout<<" 5-求前缀表达式n"cout<<" 6-前缀表达式求值n" cout<<" 7-显示表达式n"cout<<" 8-退出n"cout<<"Enter choice:"cin>>choice;switch(choice)case 1:/创建表达式cout<<"请输入表达式，以=结束"<<endl;cin>>exp;cin.get(pause);system("pause");break;case 2:/表达式求值v1=Val_Exp(exp) ;cout<<exp;cout<<v1<<endl;cin.get(pause); system("pause");break;case 3:/求后缀表达式CreatePostExp(exp,postexp);cin.get(pause);system("pause");break;case 4:/后缀表达式求值v1=Val_PostExp(postexp);cout<<postexp<<"="<<v1<<endl;cin.get(pause);system("pause");break; case 5:/求前缀表达式CreatePreExp(exp,preexp);system("pause");cin.get(pause);break; case 6:/前缀表达式求值 v2=Val_PreExp(preexp); cout<<preexp<<"="<<v2<<endl; cin.get(pause);system("pause");break;case 7:/ 显示表达式cout<<endl;cout<<"中缀表达式为:"cout<<exp<<endl;CreatePostExp(exp,postexp);CreatePreExp(exp,preexp);cin.get(pause);system("pause");break;case 8:/退出cout<<"结束运行，Bye-Bye!"<<endl;break; default: /选择不合理cout<<"Invalid choicen"break;cout<<endl;while(choice!=8);/end main