数据结构课程设计-表达式求值问题.doc

(完整word版)数据结构课程设计-表达式求值问题实验 表达式求值问题1.问题描述 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计 （1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： 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(); /显示栈中元素; （2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。Step1：申请一组连续的内存空间为顺序栈使用：base=new Tm;if(base=NULL) cout栈创建失败，退出!endl;exit(1);Step2：给栈顶、栈容量赋相应的值：stacksize=m;top=-1;（2）顺序栈入栈：入栈需要在栈顶插入一个新元素并相应的调整栈顶。Step1：首先判断是否栈满，如果栈满，抛出“上溢”信息，无法入栈，否则转入Step2；if(top=stacksize-1) throw 栈满，无法入栈;Step2：栈顶指针增加1；top+;Step3：新元素插入栈顶位置；basetop=x;（3）顺序栈出栈：出栈需要取出栈顶元素，并相应的调整栈顶指针。Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2；if(top=-1) throw 栈空，不能出栈;Step2：取出栈顶元素，栈顶指针减1；T x;x=basetop-;Step3：返回栈顶元素；return x；（4）顺序栈取栈顶元素：取栈顶元素是取出栈顶元素的值，但不改变栈。Step1：首先判断是否栈空，如果栈空，抛出“下溢”信息，无法出栈，否则转入Step2；if(top=-1) throw 栈空，栈顶无元素;Step2：取出栈顶元素，返回栈顶元素；return basetop;（5） 判断栈空：判断是否栈空，返回Step1：如果栈空，返回1，否则转Step2；if(top=-1) return 1;Step2：否则返回0；return 0;（6） 清空栈：将栈清空。top=-1（7） 返回栈顶指针：cout栈顶top= =0) coutbasei-t; coutendl;3. 算法设计本实验要求读入中缀表达式，求中缀表达式，将中缀表达式转换成前，后缀表达式，利用前，中，后缀表达式求值，并且能够输出等等操作，这就需要构建相关算法。（1） 首先要将表达式中操作符优先级进行排序，优先级从高到低依次为（，），*，/，+，-，算法如下，利用选择语句比较：char Precede(char t1,char t2) /运算符的优先级比较 char f; switch(t2) case +: case -:if(t1=(|t1=) f=; break; case *: case /:if(t1=*|t1=/|t1=) f=; else f=; break; case (:if(t1=) coutERROR1endl; exit(0); else f=; break; case ):switch(t1) case (:f=; break; case =:coutERROR2; break; case =:switch(t1) case =:f=; break; case (:coutERROR2; return f; （2） 其次，就是判断输入元素是否为运算符，若为运算符，就输出1，否则输出0； int In(char c) / 判断c是否为运算符 switch(c) case+: case-: case*: case/: case(: case): case=:return 1; default:return 0; （3） 构造表达式的运算算法，利用选择语句将运算分类：float Operate(float a,char theta,float b) /实施一次运算 float c; switch(theta) case+:c=a+b; break; case-:c=a-b; break; case*:c=a*b; break; case/:c=a/b; return c; （4） 要求一：中缀表达式求值Step1：首先需要将运算符和运算数分开存放，这就需要分别创建栈：SqStack OP(20);SqStack OD(20);Step2:创建相关字符来存放由键盘输入的字符，并以“=”键结束 char theta; float a,b,d; char c,x; / 存放由键盘接收的字符 char z6; / 存放符点数字符串 int i;OP.Push(=);Step3：当输入为数字元素是，直接存入表达式栈就可以，而当输入是符号元素时，就需要判断优先级并进行存栈出栈操作，如果是非法字符，输出错误，并且不存入；c=*exp+; x=OP.GetTop(); while(c!=|x!=) if(In(c) / 是7种运算符之一 switch(Precede(x,c) case:theta=OP.Pop(); / 退栈并将运算结果入栈 b=OD.Pop(); a=OD.Pop(); OD.Push(Operate(a,theta,b); else if(c=0&c=0&c=9|c=.); zi=0; d=atof(z); / 将字符串数组转为符点型存于d OD.Push(d); else / c是非法字符 coutERROR3endl; exit(0); x=OP.GetTop(); d=OD.GetTop(); return d; （4）中缀表达式转换成后缀表达式：Step1：创建一个操作符栈；char c,x;int i=0;SqStack OP(20);Step2：从左到右扫描读取表达式，执行下列运算，直至表达式结束符。 SqStack OP(20);OP.Push(=); / =是表达式结束标志coutexp:exp=0&c=9)|c=.)postexpi+=c;c=*exp+; 2.2：如果是操作符A2，把操作符栈栈顶的操作符A2与它比较：2.2.1：A1A2，从操作符栈输出所有比A2优先级高的运算符，直至栈顶算符优先级小于A2，A2如操作符栈。if(In(c) / 是7种运算符之一postexpi+= ; x=OP.GetTop();switch(Precede(x,c)case:postexpi+=OP.Pop(); / 运算符出栈输出 break;postexpi=0;（4）中缀表达式转换成前缀表达式：Step1：创建一个操作符栈；char c,x;int i=0;SqStack OP(20);Step2：从右到左扫描读取表达式，执行下列运算，直至表达式结束符；while(*exp != 0) *exp+; OP.Push(=); / =是表达式结束标志c=*exp-;2.1：如果是操作数，输出；if(c=0&c=9)|c=.)preexpi+=c;c=*exp-;2.2：如果是操作符A2，把操作符栈栈顶的操作符A2与它比较：2.2.1：A1A2，从操作符栈输出所有比A2优先级高的运算符，直至栈顶算符优先级小于A2，A2如操作符栈。if(In(c) / 是7种运算符之一preexpi+= ; x=OP.GetTop();switch(Precede(x,c)case:preexpi+=OP.Pop(); / 运算符出栈输出 break;preexpi=0;/while（5）后缀表达式求值：Step1：创建一个栈，作为操作数栈；SqStack OD(20);Step2：执行下列操作，直到表达式结束；2.1：读取表达式：c=*postexp+;2.2：如果是操作数，入操作数栈；if(c=0&c=0&c=9|c=.);zi=0;d=atof(z); / 将字符串数组转为符点型存于dOD.Push(d);2.3如果是操作符A，从操作数栈推出两个操作数a，b，进行运算。并把运算结果入操作数栈；if(In(c)/c为运算符b=OD.Pop ();a=OD.Pop ();OD.Push (Operate(a,c,b);c=*postexp+;c=*postexp+;Step3：栈顶元素即为表达式的值，返回它；v=OD.Pop ();return v;（6）前缀表达式求值；Step1：创建一个栈，作为操作数栈；SqStack OD(20);Step2：执行下列操作，直到表达式结束；2.1：读取表达式：c=*preexp-;2.2：如果是操作数，入操作数栈；if(c=0&c=0&c=9|c=.);zi=0;d=atof(z); / 将字符串数组转为符点型存于dOD.Push(d);2.3如果是操作符A，从操作数栈推出两个操作数a，b，进行运算。并把运算结果入操作数栈；if(In(c)/c为运算符b=OD.Pop ();a=OD.Pop ();OD.Push (Operate(a,c,b);c=*preexp-;c=*preexp-;Step3：栈顶元素即为表达式的值，返回它；v=OD.Pop ();return v;（7）界面设计：界面要求简洁明了，能够方便用户进行功能选择，菜单界面如下：1-创建表达式2-表达式求值3-求后缀表达式4-后缀表达式求值5-求前缀表达式6-前缀表达式求值7-显示表达式8-退出4.运行与测试（1）运行程序，显示菜单，如图所示：（2）创建表达式，由中前后缀表达式计算结果如下图所示： （3）将中缀表达式转化为前后缀表达式： 5.调试记录及收获本次试验为表达式求值实验，首先需要对表达式进行输入存入处理，这就需要利用栈的特性，中缀表达式和中转后都比较容易写出，就是中转前需要将表达式从后往前遍历，这就需要将指针先移到字符串的尾端，我这里运用了while(*exp != 0) *exp+;的代码，将exp移到最后，从右往左对c赋值，然后进行比较。此时得到的前缀表达式就是3 4 7 2 * / 1 + ，此时利用栈的特性，后进先出，将栈顶元素先行压出，这就反转成了前缀表达式 + 1 / * 2 7 4 3 ，此时就大功告成了。本次试验中，实现了表达式的求值和中缀表达式转换成前后缀表达式，更重要的是，我理解了栈的使用方法以及指针的运用方式。附录：程序清单：头文件：/顺序栈类定义template 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 SqStack:SqStack(int m)base=new Tm;if(base=NULL) cout栈创建失败，退出!endl;exit(1);stacksize=m;top=-1;template void 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;template int SqStack:StackEmpty()if(top=-1) return 1;elsereturn 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; 主函数：#include/cout,cin#includeprocess.h/exit()#includestdio.h/EOF,NULL#include#include / atoi()#includeSqStack.hchar pause;char Precede(char t1,char t2) /算符的优先级比较 char f; switch(t2) case +: case -:if(t1=(|t1=) f=; break; case *: case /:if(t1=*|t1=/|t1=) f=; else f=; break; case (:if(t1=) coutERROR1endl; exit(0); else f=; break; case ):switch(t1) case (:f=; break; case =:coutERROR2; break; case =:switch(t1) case =:f=; break; case (:coutERROR2; return f; int In(char c) / 判断c是否为运算符 switch(c) case+: case-: case*: case/: case(: case): case=:return 1; default:return 0; float Operate(float a,char theta,float b) /实施一次运算 float c; switch(theta) case+:c=a+b; break; case-:c=a-b; break; case*:c=a*b; break; case/:c=a/b; return c; float Val_Exp(char *exp) /中缀表达式求值。设OPTR和OPND分别为运算符栈和运算数栈 SqStack OP(20); SqStack OD(20); char theta; float 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(); / 退栈并将运算结果入栈 b=OD.Pop(); a=OD.Pop(); OD.Push(Operate(a,theta,b); else if(c=0&c=0&c=9|c=.); zi=0; d=atof(z); / 将字符串数组转为符点型存于d OD.Push(d); else / c是非法字符 coutERROR3endl; exit(0); x=OP.GetTop(); d=OD.GetTop(); return d; void CreatePostExp(char * exp,char * &postexp)/由中缀式求后缀式char c,x;int i=0;SqStack OP(20);OP.Push(=); / =是表达式结束标志coutexp:exp=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;/whilecout后缀表达式为:postexpendl;void CreatePre(char * exp,char * &preexp)/由中缀式求前缀式char c,x;int i=0;SqStack OP(20);coutexp:exp=0&c=9)|c=.)preexpi+=c;c=*exp-;if(In(c) / 是7种运算符之一preexpi+= ; x=OP.GetTop();switch(Precede(x,c)case:preexpi+=OP.Pop(); / 运算符出栈输出 break;preexpi=0;/whilecout前缀表达式为:preexpi-endl;float Val_PostExp(char *postexp)/后缀表达式求值int i;char z6;float v=0,d=0,a,b;char c;SqStack OD(20);c=*postexp+;while(c!=0)if(c=0&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;float Val_PreExp(char *preexp)/前缀表达式求值int i;char z6