算术表达式求值演示.doc

实习报告题目：算术表达式求值演示。一、 需求分析1.以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。2.利用教科书表3.1给出的算符优先关系，实现对算数四则混合运算表达式的求值。3.仿照教科书的例子在求值中运用符栈、运算数栈、输入字符和主要操作的变化过程。4.程序执行的命令包括：(1)构造空栈；(2) 判断符号优先级;(3) 判断是否为七种运算符之一;(4)运算求解算术表达式。5.测试数据(1)3*(7-2);(2)8;(3)1+2+3+4;(4)88-1*5;(5)1024*4/8;(6)(20+2)*(6/2);(7)3-3-3;(8)8/(9-9);(9)2*(6+2*(3+6*(6+6);(10)(6+6)*6+3)*2+6)*2;二、概要设计1.设定栈的抽象数据类型定义：ADT Stack数据对象：D=ai|aiCharSet,i=1,2,，n,n0数据关系：R1=| ai -1, ai D,i=2,，n基本操作：InitStack（&S）操作结果：构造一个空栈S。GetTop (S，&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S, e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S, &e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，用e返回其值。 ADT Stack2.设定运算表达式的抽象数据类型为：ADT EvaluateExpression数据对象：D=ai| ai为数字及运算符，i=1,2,，n,n0数据关系：R1= 基本操作：Precede(a1 , a2)初始条件：字符a1，a2存在。操作结果：判定运算符的优先级In( d )初始条件：字符d存在。操作结果：判断c是否为七种运算符之一Operate(a, theta, b )初始条件：字符a, theta, b存在。操作结果：运算表达式结果。 ADT EvaluateExpression3.本程序包含3个模块：（1）主程序模块：int main() 初始化；do接受命令：处理命令：return 0;(2)栈模块实现栈抽象数据类型(3)求解算术表达式模块实现算术表达式数据类型各模块之间的调用关系如下：主程序模块 栈模块 求解算术表达式模块三、详细设计1.数据类型、字符类型。typedef double SElemType;/ 数据类型char Precede(char a1 ,char a2) char r; /字符类型2.栈类型typedef struct SqStack SElemType *base; SElemType *top; int stacksize;SqStack;栈的基本操作设置如下：void InitStack (SqStack &S)/构造一个空栈bool GetTop (SqStack S,SElemType &e) /若栈不空，则用e返回S的栈顶元素，并返回true；否则返回falsebool Push(SqStack &S,SElemType e) /插入元素为e的新的栈顶元素bool Pop(SqStack &S,SElemType &e)/若栈不空，则删除S的栈顶元素，用e返回其值其中部分操作的算法：bool Push(SqStack &S,SElemType e) /插入元素为e的新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(-1); /存储空间分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;/top自增 return true;bool Pop(SqStack &S,SElemType &e)/若栈不空，则删除S的栈顶元素，用e返回其值 if(S.top=S.base) return false; e=*-S.top; /删除一个元素,top减一 return true ;3. 求解算术表达式的伪算法SElemType EvaluateExpression( ) SqStack OPTR,OPND;/OPTR和OPND分别为运算符栈和运算数栈 char c; char Data20;/定义此数组为了存放整数或小数 SElemType a,b,d,e; InitStack(OPTR);/构造一个运算符栈 InitStack(OPND);/构造一个运算数栈 Push(OPTR,n);/将换行符压入栈底 c=getchar(); GetTop(OPTR,e); while(c!=n|e!=n)/栈顶不是换行符且输入不是换行符 if(In(c)/是符号则进栈 switch(Precede(e,c) case: /退栈并将运算结果入栈 Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b); break; else if(c=0&c=9|c=.) Push(OPND,c-48); c=getchar(); else couterror!输入错误!endl; exit(-1); GetTop(OPTR,e); GetTop(OPND,e); return e;4.主函数和其他函数的伪算法int main()/主程序 SElemType result;/初始定义 cout请输入表达式endl;/输出输入要求 result=EvaluateExpression();/执行函数操作命令 cout结果为:resultendl;/输出结果 return 0;char Precede(char a1 ,char a2)/判定运算符的优先级函数。 char r; switch(a2) case+: case-:/加减运算优先级相同 if(a1=(|a1=n) r=; break; case*: case/: /乘除运算优先级相同 if(a1=*|a1=/|a1=) r=; else r=; break; case(: if(a1=) cout括号匹配错误!endl; exit(-1); else r=; break; case): if(a1=() r=; else if(a1=n) couterror!没有左括号; break; casen: switch(a1) casen: r=; break; case(: couterror!没有右括号; break; return r;bool In(char d)/判断c是否为七种运算符之一的函数 switch(d) case+: case-: case*: case/: case(: case): casen: return true; default: return false; 5.函数的调用关系图反映了演示程序的结构层次： 主程序Initialization ReadCommand Interpret Init EvaluateExpression PrintEvaluateExpression InitStack Push Pop GetTop四、调试分析1.这次作业思路比较简单，核心问题就是表达式的运算，要区分运算符的优先顺序。通过运用栈后进先出的特点实现算法功能，调用push和pop等函数，实现一系列操作。2.调试过程中，起初想打换行符时打成了，忘了打字母n,结果程序调试总是有错误，改成n后便成功运行了，可见，细节之处也很重要。3.运用了很多的栈的基本操作，让我对栈的内容熟悉了不少，收获很大。4本题中时间复杂度为O（n）五、用户手册本程序的运行环境为DOS操作系统，执行文件为：EvaluateExpression.exe。六、测试结果(1) 请输入表达式：3*(7-2);结果为：15(2) 请输入表达式：8;结果为：8(3) 请输入表达式：1+2+3+4;结果为：10(4) 请输入表达式：88-1*5;结果为：82(5) 请输入表达式：1024*4/8;结果为：512(6) 请输入表达式： (20+2)*(6/2);结果为：6(7) 请输入表达式：3-3-3;结果为：-3(8) 请输入表达式：8/(9-9);结果为：error!除数不能为零(9) 请输入表达式：2*(6+2*(3+6*(6+6);结果为：312(10) 请输入表达式： (6+6)*6+3)*2+6)*2;结果为：312七、附录源代码见“源程序文档”