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

1、数据结构课程设计 实验报告数据结构课程设计 实验报告题目：2.3 表达式求值问题1.问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 *3/11 +）和前缀式（如：+ 11/*237 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计本题中使用顺序栈用来存取运算符和运算数，顺序栈类的定义如下：/顺序栈类定义templa

2、te class SqStack private: 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.算法设计

3、本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、将中缀表达式转换为前缀表达式、后缀表达式求值、前缀表达式求值。（1）中缀表达式求值首先定义了两个栈，分别用于存取运算符和运算数，如下：SqStack OP(20); SqStackOD(20);然后依次读取表达式的一个字符C，如果C是运算数，入运算数栈OP.Push(C)；如果C是运算符，把它与栈顶元素的优先级比较：若“”，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。这时需用到比较运算符优先级的函数：char Precede(char t1,char t2) /算符的优先级比较重复

4、上述过程直到把表达式扫描完，操作数栈的栈顶元素为计算结果。算法如下： 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进行

5、比较：若“f1f2”，从运算符栈退出一个运算符，从运算数栈里输出所有比f2优先级高的运算符，直至栈顶算符优先级小于f2，f2入运算符栈。具体算法如下：case:postexpi+=OP.Pop();break; / 运算符出栈输出（3）将中缀表达式转换为前缀表达式将中缀式入栈再依次从栈中读取元素：如果是操作数把它加入一个数组中;如果是运算符：若栈空或栈顶是右括号或此元素的优先级大于等于栈顶元素，则此运算符入栈；否则，栈顶运算符出栈并加入数组中；若是左括号，栈中元素逐个出栈加入数组中，直到遇到右括号。最后数组中的元素序列为中缀式的逆序，将数组中的元素入栈再出栈就得到前缀式。 部分算法如下： Sq

6、StackST(20); SqStackSP(20); SqStackOP(20); while(*exp!=) /利用栈得到中缀式的逆序 ST.Push(*exp+); while(!ST.StackEmpty() x=ST.Pop(); if(x=0&x|Precede(x,OP.GetTop()=) OP.Push(x); break; else sj+=OP.Pop(); if(x=() while(OP.GetTop()!=) sj+=OP.Pop(); OP.Pop(); while(!OP.StackEmpty() sj+= ; sj+=OP.Pop(); sj=0; while

7、(si!=0) SP.Push(si+); while(!SP.StackEmpty() preexpk+=SP.Pop(); /再次求逆序得到前缀式（4）后缀表达式求值创建一个栈，作为运算数栈读取表达式： 若是运算数，入运算数栈； 若是运算符，从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。最后，栈顶元素即为表达式的值。具体算法如下： SqStack OD(20); c=*postexp+; while(c!=0) if(c=0&c=0&c=9|c=.); zi=0; d=atof(z); / 将字符串数组转为浮点型存于d OD.Push(d); if(In(c)/c为运算符 b

8、=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是运算符，则从运算数栈退出两个运算数，进行运算，并把运算结果入运算数栈。最后，栈顶元素即为表达式的值。具体算法如下： SqStackST(20); SqStackOD(20); while(*preexp!=0) ST.P

9、ush(*preexp+); / 利用栈得到前缀表达式的逆序 while(!ST.StackEmpty() x=ST.Pop(); if(x=0&x=0&x=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-求

10、后缀表达式n; cout 4-后缀表达式求值n; cout 5-求前缀表达式n; cout 6-前缀表达式求值n; cout 7-显示表达式n; cout 8-退出n; coutEnter choice:;4.运行与测试（1）运行程序，显示菜单，如下图所示：（2）按“1”创建表达式。根据提示，输入表达式，如下图所示： （3）按“2”表达式求值。 （4）按“3”求后缀表达式。 （5）按“4”求后缀表达式的值。 （6）按“5”求前缀表达式。 （7）按“6”求前缀表达式的值。 （8）按“7”求显示中缀表达式。 （9）按“1”和“2”，输入一个错误的表达式，程序会判断表达式错误。 （10）按“8”退出

11、。5.调试记录及收获（1）学会理解运用栈的结构，使用栈的“先进后出”的特点；（2）前缀和后缀的变换借助于栈实现，理解前缀、中缀、后缀的不同之处；（3）调试程序要细致耐心，当程序的功能较多时，要仔细测试程序的每一个功能，发现错误要及时查错修改，不断完善程序。7.源程序#includeusing namespace std;/顺序栈类定义template class SqStack private: T *base;/栈底指针 int top;/栈顶 int stacksize;/栈容量 public: SqStack(int m);/构建函数 SqStack()delete base;top=0

12、;stacksize=0;/析构函数 void Push(T x);/入栈 T Pop();/出栈 T GetTop();/获取栈顶元素 int StackEmpty();/测栈空 void ClearStack();/清空栈 void StackTop();/返回栈顶指针 void StackTranverse();/显示栈中元素;/顺序栈类实现template SqStack:SqStack(int m) /创建一个空栈 base=new Tm; if(base=NULL) cout栈创建失败，退出!endl; exit(1); stacksize=m; top=-1;template v

13、oid SqStack:Push(T x) /入栈操作 if(top=stacksize-1) throw 栈满，无法入栈; top+; basetop=x; /couttop：topendl;template T SqStack:Pop() /出栈操作 T x; if(top=-1) throw 栈空，不能出栈; x=basetop-; /couttop：topendl; return x;template /获取栈顶元素T SqStack:GetTop() if(top=-1) throw 栈空，栈顶无元素; /couttop：topendl; return basetop;templat

14、e int SqStack:StackEmpty() /测栈空 if(top=-1) return 1; else return 0;template void SqStack:ClearStack() /清空栈 top=-1;template void SqStack:StackTop() /返回栈顶指针 cout栈顶top= top;template void SqStack:StackTranverse() /输出栈中元素 int i=top; while(i=0) coutbasei-t; coutendl; char pause;char Precede(char t1,char t

15、2) /算符的优先级比较 char f; switch(t2) case +: case -:if(t1=(|t1=) 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表达式有误!; break; case =:switch(t1) case =:f=; break; case (:cout表达式有误!; ret

16、urn 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(ch

17、ar *exp) /中缀表达式求值 SqStack OP(20);/建立容量为20的运算符栈 SqStack 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:theta=OP.Pop();/ 退栈并将运算结果

18、入栈 if(theta=(|theta=) cout表达式有误!; exit(0); b=OD.Pop(); if(b=0) cout表达式有误!endl; exit(0); if(OD.StackEmpty() cout表达式有误!=0&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 * &pree

19、xp) /由中缀式求前缀式 char x; char s20; int j=0,i=0,k=0; SqStackST(20); SqStackSP(20); SqStackOP(20); while(*exp!=) /利用栈得到中缀式的逆序 ST.Push(*exp+); while(!ST.StackEmpty() x=ST.Pop(); if(x=0&x|Precede(x,OP.GetTop()=) OP.Push(x); break; else sj+=OP.Pop(); if(x=() while(OP.GetTop()!=) sj+=OP.Pop(); OP.Pop(); whil

20、e(!OP.StackEmpty() sj+= ; sj+=OP.Pop(); sj=0; while(si!=0) SP.Push(si+); while(!SP.StackEmpty() preexpk+=SP.Pop(); /再次求逆序得到前缀式 preexpk=0; cout前缀表达式为:preexpendl;void CreatePostExp(char * exp,char * &postexp) /由中缀式求后缀式 char c,x; int i=0; SqStack 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:postexpi+=OP.Pop(); / 运算符出栈输出 break; postexpi=0; /while cout后缀表达式为:postexpendl;double Val_PostExp(char *postexp) /后缀表达式求值