数据结构课设报告-算术表达式求值.docx

课程设计报告数据结构课程名称： 算术表达式求值题目名称： 学生姓名： 学号： 课程成绩： 二零一六 年 六 月1. 需求分析本演示程序用C+6.0编写，完成栈的生成。（1） 输入的形式和输入值的范围：输入合法表达式，以“#”结尾；输入的操作数是正整数，运算符只含加减乘除四种运算符。（2）输出的形式：显示输入是否正确、输入序列和栈的变化过程、计算结果。（3）程序所能达到的功能：完成算术表达式的计算。（4）测试数据：输入3*（2+4）#；输入5*2#。2. 概要设计（1） 为了实现上述程序功能，需要定义栈的抽象数据类型：ADT SqStack数据对象：D=ai| ai ElemSet,i=1,2,3，n,n0数据关系：R1=| ai-1,ai D,i=1,2,3,，n基本操作：InitStack(SqStack &S)操作结果：声明栈建立函数Push(SqStack &S,char e)初始条件：栈已经存在操作结果：声明入栈函数Pop(SqStack &S)初始条件：栈已经存在操作结果：声明出栈函数DispStack(SqStack &S)初始条件：栈已经存在操作结果：从栈底到栈顶依次输出各元素（2） 本程序包括5个函数：主函数main（）确定如何入栈函数evaluate( )声明取栈顶元素函数GetTop( )声明比较函数Compare( )声明运算函数Operate( )各函数间关系如下： InitStackmainpush evaluateDispStack Compare Pop GetTop Operate3. 详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。（1）栈和指针类型typedef struct /运算符栈SElemType *base;SElemType *top;int stacksize;SqStack1;typedef struct /运算数栈SElemType2 *base;SElemType2 *top;int stacksize;SqStack2;（2）栈的基本操作void InitStack1(SqStack1 &S1)/构造一个空栈S1S1.base=new SElemTypeSTACK_INIT_SIZE;if(!S1.base)cout存储分配失败！;/存储分配失败S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;void InitStack2(SqStack2 &S2)/构造一个空栈S2S2.base=new SElemType2STACK_INIT_SIZE;if(!S2.base)cout=S1.stacksize)/如果栈满，追加存储空间S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char);if(!S1.base)cout=S2.stacksize)/栈满，追加存储空间S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout存储分配失败！;elseS2.top=S2.base+S2.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;*S2.top=e;S2.top=S2.top+1;/将元素e入栈，指针上移char Pop1(SqStack1 &S1)/出栈char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;e=*(-S1.top);return e;float Pop2(SqStack2 &S2)/出栈float e;if(S2.top=S2.base)coutntt运算数栈已空!;e=*(-S2.top);return e;void DispStack1(SqStack1 &S1)/从栈底到栈顶依次输出各元素char e,*p;if(S1.top=S1.base)cout ;elsep=S1.base;while(pS1.top)e=*p;p+;coute;void DispStack2(SqStack2 &S2)/从栈底到栈顶依次输出各元素float e,*p;if(S2.top=S2.base)cout ;elsep=S2.base;while(pS2.top)e=*p;p+;coute;（3）其他模块伪码算法void main()SqStack1 S1;/定义运算符栈SqStack2 S2;/定义运算数栈InitStack1(S1);/调用栈建立函数InitStack2(S2);/调用栈建立函数evaluate(S1,S2);/调用确定如何入栈函数cout按任意键结束!endl;char GetTop1(SqStack1 &S1)/取栈顶元素char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;else e=*(S1.top-1);return e;float GetTop2(SqStack2 &S2)/取栈顶元素float e;if(S2.top=S2.base) coutntt运算数栈已空!;else e=*(S2.top-1);return e;char Compare(char m,char n)/运算符的优先级比较if(n=+|n=-)/输入符号为+、- if(m=(|m=#)return ;/栈顶元素为(、#,此时栈顶符号优先级低，返回;/否则，栈顶符号优先级高,返回else if(n=*|n=/)/输入的符号为*、/if(m=)|m=*|m=/)return ;/栈顶元素为)、*、/,此时栈顶符号优先级高，返回else return ;/否则，栈顶符号优先级低,返回else if(n=()return;/输入的符号为(,则直接返回;/否则，栈顶符号优先级高,返回else /输入符号为其他if(m=#)return=;/栈顶元素为#,此时优先级同，返回=else return ;/否则，栈顶符号优先级高,返回float Operate(float a,char theta,float b)/运算函数float tmp=0;if (theta=+)tmp=a+b;/从运算符栈取出的符号为+，则运算数栈的两元素相加，并返回else if(theta=-)tmp=a-b;/从运算符栈取出的符号为-，则运算数栈的两元素相减，并返回else if(theta=*)tmp=a*b;/从运算符栈取出的符号为*，则运算数栈的两元素相乘，并返回else if(theta=/) /从运算符栈取出的符号为/，则运算数栈的两元素相除，并返回if(b=0) coutn表达式出错!除数不能为0!n;else tmp=a/b;return tmp;4. 测试分析（1） 调试过程回顾分析：1、 语法错误： 错误主要有指针的错误指向，等号与赋值号的混淆，大括号的不正确匹配，变量不定义便使用或局部变量全局使用。2、逻辑错误： 程序初步完成以后，进行测试发现出现死循环，观察显示结果发现，栈中的数据和运算符一直都没有出栈。仔细检查出栈函数操作，发现将return语句写到了top语句的前面，而return语句有跳出的作用，当它一旦执行，其后的语句都会被忽略而得不到执行。因此将它们调换顺序。再次调试程序，输入一个测试表达式（如1+2*5#），发现结果是10，而且通过将栈中的数据进行显示发现1并未出栈，而操作符栈的“+”未进行运算便出了栈。通过检查发现错误出在优先级判断的条件语句里面，在取出栈顶元素与刚读入的运算符进行比较时，当刚读入的运算符优先级高于栈顶的运算符时，直接将刚读入的运算符入栈，因此应将刚取出的先入栈，然后将刚读入的运算符入栈。（2） 时空分析：时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。空间上，由于是用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。在不知表达式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。（3） 经验和体会在课程设计中，算法应简明易懂；如果程序反复多次使用，则应该尽可能选用快速的算法；如果待解决的问题数据量极大，机器的存储空间较小，则在编写算法时应该考虑如何节省空间。以后在编写程序时就应该注意到所编写程序的时间复杂度，以及是否运用了良好的算法，而不能只是像以前编写程序时单纯使用C语言的知识，要充分考虑程序的性能，争取编写出更优良的程序来。通过实际操作，我也发现我的很多不足之处：(1)对一些看似简单的东西掌握不够熟练，比如由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。(2)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。5. 使用说明程序名为Demo1.exe，运行环境为DOS。程序执行后显示请输入不含变量的表达式（以#结束!）：在表达式后输入操作数为正整数的算术表达式。每执行一次功能会显示执行过程及结果。6. 测试结果（1）输入3*（2+4）#，输出：对表达式求值的操作过程如下：_步骤 运算符栈S1 运算数栈S2 输入字符 主要操作_1 # 3*(2+4)# Push2(S2,3)_2 # 3 *(2+4)# Push1(S1,*)_3 #* 3 (2+4)# Push1(S1,()_4 #*( 3 2+4)# Push2(S2,2)_5 #*( 32 +4)# Push1(S1,+)_6 #*(+ 32 4)# Push2(S2,4)_7 #*(+ 324 )# Operate(2,+,4)_8 #*( 36 )# Pop1(S1)_9 #* 36 # Operate(3,*,6)_10 # 18 # RETURN(GETTOP(S2)_表达式的结果为：18（2） 输入5*2#，输出：对表达式求值的操作过程如下：_步骤 运算符栈S1 运算数栈S2 输入字符 主要操作_1 # 5*2# Push2(S2,5)_2 # 5 *2# Push1(S1,*)_3 #* 5 2# Push2(S2,-141)_4 #* 5-141 ?# Push2(S2,-15408)_5 #* 5-141-15408 # Operate(-141,*,-15408)_6 # 2.17253e+006 # RETURN(GETTOP(S2)_表达式出错!7.附录（源代码）#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef float SElemType2;typedef struct /运算符栈SElemType *base;SElemType *top;int stacksize;SqStack1;typedef struct /运算数栈SElemType2 *base;SElemType2 *top;int stacksize;SqStack2;/*运算符栈函数*/void InitStack1(SqStack1 &S1)/构造一个空栈S1S1.base=new SElemTypeSTACK_INIT_SIZE;if(!S1.base)cout=S1.stacksize)/如果栈满，追加存储空间S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char);if(!S1.base)cout存储分配失败！;elseS1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;*S1.top=e;S1.top=S1.top+1;/将元素压入栈中，指针上移char GetTop1(SqStack1 &S1)/取栈顶元素char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;else e=*(S1.top-1);return e;void DispStack1(SqStack1 &S1)/从栈底到栈顶依次输出各元素char e,*p;if(S1.top=S1.base)cout ;elsep=S1.base;while(pS1.top)e=*p;p+;coute;char Pop1(SqStack1 &S1)/出栈char e;if(S1.top=S1.base)coutnttt运算符栈已空!n;e=*(-S1.top);return e;/*运算数栈函数*/void InitStack2(SqStack2 &S2)/构造一个空栈S2S2.base=new SElemType2STACK_INIT_SIZE;if(!S2.base)cout=S2.stacksize)/栈满，追加存储空间S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float);if(!S2.base)cout存储分配失败！;elseS2.top=S2.base+S2.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;*S2.top=e;S2.top=S2.top+1;/将元素e入栈，指针上移void DispStack2(SqStack2 &S2)/从栈底到栈顶依次输出各元素float e,*p;if(S2.top=S2.base)cout ;elsep=S2.base;while(pS2.top)e=*p;p+;coute;float GetTop2(SqStack2 &S2)/取栈顶元素float e;if(S2.top=S2.base) coutntt运算数栈已空!;else e=*(S2.top-1);return e;float Pop2(SqStack2 &S2)/出栈float e;if(S2.top=S2.base)coutntt运算数栈已空!;e=*(-S2.top);return e;char Compare(char m,char n)/运算符的优先级比较if(n=+|n=-)/输入符号为+、- if(m=(|m=#)return ;/栈顶元素为(、#,此时栈顶符号优先级低，返回;/否则，栈顶符号优先级高,返回else if(n=*|n=/)/输入的符号为*、/if(m=)|m=*|m=/)return ;/栈顶元素为)、*、/,此时栈顶符号优先级高，返回else return ;/否则，栈顶符号优先级低,返回else if(n=()return;/输入的符号为(,则直接返回;/否则，栈顶符号优先级高,返回else /输入符号为其他if(m=#)return=;/栈顶元素为#,此时优先级同，返回=else return ;/否则，栈顶符号优先级高,返回float Operate(float a,char theta,float b)/运算函数float tmp=0;if (theta=+)tmp=a+b;/从运算符栈取出的符号为+，则运算数栈的两元素相加，并返回else if(theta=-)tmp=a-b;/从运算符栈取出的符号为-，则运算数栈的两元素相减，并返回else if(theta=*)tmp=a*b;/从运算符栈取出的符号为*，则运算数栈的两元素相乘，并返回else if(theta=/) /从运算符栈取出的符号为/，则运算数栈的两元素相除，并返回if(b=0) coutn表达式出错!除数不能为0!n;else tmp=a/b;return tmp;/*确定如何入栈函数*/void evaluate(SqStack1 &S1,SqStack2 &S2)char c;float t,e;int n=0,i=1,j=0,k=0,l=0;char chSTACK_INIT_SIZE;int s=1;int flag=0,flag2=0;float p1,p2;char ch1;Push1(S1,#);/将#入栈，作为低级运算符coutch;c=ch0;coutn对表达式求值的操作过程如下：n_n步骤t运算符栈S1t运算数栈S2t输入字符tt主要操作;while(c!=#|GetTop1(S1)!=#) coutn_n; couti+t;DispStack1(S1);couttt;DispStack2(S2);couttt;if(flag=1)k-;flag=0;if(flag2)k+=flag2;flag2=0;for(l=0;lk;l+)cout ;for(j=k;chj!=0;j+)cout