数据结构表达式求值完整篇(含实验报告).doc

1、 实验目的和要求（1）深入理解栈的特点及其描述方法。 （2）能够在两种存储结构上实现栈抽象数据类型实现。 （3）掌握栈的几个典型应用算法，能灵活应用栈解决实际问题。2、 概要设计【定义所有抽象数据类型、自定义函数间的调用关系图，自定义函数的功能描述和流程图，以及主程序的流程图。】Y开始输出结果EvaluateExpression ( )While(1)定义运算符和操作数栈并初始化 并fflush(stdin)清除缓存OPTR; OPND; 输入每个字符并执行相应的条件语句入栈出栈/比较OPTR的栈顶元素和ch的优先级char Precede (SElemType_OPTR top, char ch)/运算并将结果出栈Operate 3、 调试分析【(1) 调试过程中遇到的问题是如何解决的以及对设计与实现中关键点的回顾讨论和分析；(2) 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；(3) 经验和体会等。】1.栈的定义、初始化、出栈进栈、取栈顶元素等步骤不难就先把结构打好了2.操作数和运算符分别入不同的栈char-int 进 操作数栈 先考虑了小于10的整数直接进栈,重点是运算符的优先级这块函数的编写3前面的都听简单的，就是小数编写这块想了很久，将单个字符转为整数后还要定一个double p;使依次输入的数成一个小数-p.在小数入栈使要考虑放在那条if语句中，防止在运算结果入栈后p再次入栈，又定义了int flag;通过flag的值判定p是否入栈。并且成功入栈后p,q都要回到初始状态。小数解决4.负数部分讨论一开始就有负数和运算符后面有负数的情况。（比较容易） 右图重点 。定义了low做判定符号的标志。如果在运算符后输入负号则low=-1(将p入栈时入栈的是p*low)，继续输入ch。总结：我觉得写的好的地方在于定义了flag,low分别作为小数入栈和负号与减号区别的条件。第一次写这么长的代码，还有就是将输入的字符再转到小数这段代码可以留着很有用。开始考虑的大整数想麻烦了，直接用double 难度降低了很多4、 测试数据与结果【列出你的测试结果，包括输入和输出。测试数据应该完整和严格，最好多于需求分析中所列。】序号输入输出说明11-2#3.000减负数2-1-2#-3.000两负数3-1-2#1.00043.66+4.34#8.000小数52*2+4-32#-1.000长串+乘方63.66*2+3-4#6.32071+3-4*5/2+3.666#-2.3395、 附录【给出每部分的源代码（必须要有一定量的注释）。】/* common.h */#include stdio.h#include string.h#include ctype.h#include math.h/*其他函数的声明*/double EvaluateExpression ( ); /算数表达式求值的算法优先算法char Precede (SElemType_OPTR top, char ch); /比较OPTR的栈顶元素和ch的优先级double Operate (SElemType_OPND a, SElemType_OPTR theta, SElemType_OPND b); /运算/栈基本操作的函数声明void OPTR_InitStack(Sqstack_OPTR &s); /运算符栈初始化void OPND_InitStack(Sqstack_OPND &s); /操作数栈初始化char OPTR_GetTop(Sqstack_OPTR s); /取运算符的栈顶元素double OPND_GetTop(Sqstack_OPND s); /取操作数的栈顶元素 void OPTR_Push(Sqstack_OPTR &s,SElemType_OPTR e); /入栈void OPND_Push(Sqstack_OPND &s,SElemType_OPND e); /入栈void OPTR_Pop(Sqstack_OPTR &s,SElemType_OPTR &e); /出栈void OPND_Pop(Sqstack_OPND &s,SElemType_OPND &e); /出栈/*基本操作函数的实现*/#include common.h#include Sqstack.h#include other.h/运算符栈初始化void OPTR_InitStack(Sqstack_OPTR &s) s.base=new SElemType_OPTRMAXSIZE;if(!s.base)printf(n运算符栈存储分配失败!n);s.top=s.base;s.stacksize=MAXSIZE;/操作数栈初始化void OPND_InitStack(Sqstack_OPND &s) s.base=new SElemType_OPNDMAXSIZE;if(!s.base)printf(n操作数栈存储分配失败!n);s.top=s.base;s.stacksize=MAXSIZE;/取操作符的栈顶元素char OPTR_GetTop(Sqstack_OPTR s)if(s.top!=s.base)return *(s.top-1);return 0;/取运算数的栈顶元素double OPND_GetTop(Sqstack_OPND s)if( s.top != s.base )return ( *(s.top-1) )-0;return 0;/运算符入栈void OPTR_Push(Sqstack_OPTR &s,SElemType_OPTR e)if(s.top-s.base = s.stacksize)printf(n满栈!n);*s.top+=e; /先赋值后自加/操作数入栈void OPND_Push(Sqstack_OPND &s,SElemType_OPND e)if(s.top-s.base = s.stacksize)printf(n满栈!n);*s.top+=e+0; /先赋值后自加/运算符出栈void OPTR_Pop(Sqstack_OPTR &s,SElemType_OPTR &e)if(s.top = s.base)printf(n空栈!n);e=*-s.top;/操作数出栈void OPND_Pop(Sqstack_OPND &s,SElemType_OPND &e)if(s.top = s.base)printf(n空栈!n);e=(*-s.top)-0;/*其他函数的实现*/#include common.h#include Sqstack.h#include other.h/算数表达式求值的算法优先算法double EvaluateExpression ( )Sqstack_OPTR OPTR;Sqstack_OPND OPND;char ch; char x; /弹出的(char dimo=0; /记录小数点分前后计算double p=0; /将输入的操作数处理后得double p;然后p入栈double q=0.1; /小数点后运算int low=1; /判断负数int flag=1; /用来判定 double p 是否入栈SElemType_OPTR theta; /运算符栈顶元素SElemType_OPND a,b; /弹出的两个要运算的操作数/初始化 OPTR_InitStack(OPTR); /OPTR运算符 OPND_InitStack(OPND); /OPND操作数OPTR_Push(OPTR,#); /将表达式起始符压入运算符栈scanf(%c,&ch);if( ch = -)low=-1;scanf(%c,&ch); /保证接下来的实现从数字开始while(ch != # | OPTR_GetTop(OPTR) != # )if( isdigit(ch) | ch = .)flag=1;if(ch != . )if ( dimo != . )p = p*10 ;p += (ch-0);scanf(%c,&ch);else if ( dimo = .)p = p+(ch-0)*q;q=q*q;scanf(%c,&ch);else if( ch = . )dimo = .;scanf(%c,&ch); elseif( flag = 1 )OPND_Push(OPND,p*low); /操作数进栈OPNDdimo=0;p=0;q=0.1;switch( Precede( OPTR_GetTop(OPTR), ch ) )case :OPTR_Pop(OPTR,theta); /运算符存到theta出栈OPND_Pop(OPND,b); /操作数出栈OPND_Pop(OPND,a); /操作数出栈OPND_Push( OPND,Operate(a,theta,b) );flag =0 ;break; /注意此处没有输入！case =:OPTR_Pop(OPTR,x); /相等的情况: 栈顶元素是(,且ch是) 即消除一对括号scanf(%c,&ch);/low=1;break;return OPND_GetTop( OPND ); /比较OPTR的栈顶元素和ch的优先级char Precede (SElemType_OPTR top, char ch)switch (top)case +:if(ch=+|ch=-|ch=)|ch=#)return ;if(ch=*|ch=/|ch=(|ch=)return ;if(ch=*|ch=/|ch=(|ch=)return ;if(ch=(|ch=)return ;if(ch=(|ch=)return ;break;case (:if(ch=+|ch=-|ch=*|ch=/|ch=()return ;if(ch=)return =;if(ch=)return ;break;case #:if(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)return ;if(ch=()return =;break;return 0;/运算double Operate (SElemType_OPND a, SElemType_OPTR theta, SElemType_OPND b)switch(theta)case +:return a+b;break;case -:return a-b;break;case *:return a*b;break;case /:return a/b;break;case :return pow(a