算术表达式求值课程设计.doc

学号： 学年论文（设计）（本科）学 院 专 业 年 级 姓 名 论文（设计）题目 算术表达式求值 指导教师 职称 成 绩 2012 年 月 日目录一、 概述3二、 设计目的.3三、设计功能分析3四、概要设计说明4五、详细信息说明5六、流程图10七、程序代码10八、调试及运行结论17九、总结19十、参考文献19一、概述数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其它理工专业热门选修课。而且它与计算机其他课程都有密切联系，具有独特的承上启下的重要位置。拥有数据结构这门课程的知识准备，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程的都是有益的。二、设计目的 1、了解算术表达式的不同表现形式及相应算法实现的不同。2、深入了解栈的特性，并在实际问题背景下灵活运用。3、掌握字符串解释为表达式的意义和数字转化。三、设计功能分析 算术表达式求值程序实现以下功能：(1) 构造一个空栈S,初始条件：栈S已存在(2) 用P返回S的栈顶元素(3) 插入元素ch为新的栈顶元素(4) 删除S的栈顶元素(5) 判断字符是否是运算符，运算符即返回1(6) 判断运算符优先权，返回优先权高的(7) 输入表达式(8) 返回表达式的最终结果。四：概要设计说明 在计算机中算术表达式由常量、变量、运算符和括号组成。由于不同的运算符优先级不同，而且还要考虑括号；因此算术表达式不可能完全严格的从左到右执行。因此在设计程序时，要借助栈的功能。算法输入：一个算术表达式，由常量、变量、运算符、括号组成（以字符串的形式输入）。操作符为+、-、*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算术符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在. 操作结果：用P返回S的栈顶元素。 Push(*S,ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。 Precede(c1, c2) 初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。ADT Stack五、详细设计说明1、数据存储结构设计 因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还要定义一个int类型的栈用来寄存操作数。/* 定义字符类型栈 */typedef structint stacksize;char *base;char *top;Stack1/*定义整形栈*/typedef structint stacksize;int *base;int *top;Stack22、主要算法、Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。 算符间的优先关系如下：+- *、（）#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一维数组存储49种情况switch(c1) /* i为下面array的横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j为下面array的纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符array7*i+j为对应的c1,c2优先关系*/ 、利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#3*（72）#Push(OPND,3)2#3*（72）#Push(OPTR,*)3# *3（72）#Push(OPNR,()4# *（372）#Push(OPND,7)5# *（3 72）#Push(OPNR,-)6# *（3 72）#Push(OPND,2)7# *（3 7 2）#Operate(7,-,2)8# *（3 5）#Pop(OPTR)9# *3 5#Operate(3,*,5)10#15#Return GetTop2(OPND) 表二算法伪代码如下：int EvalExpr()/主要操作函数 c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) /不是运算符即进栈 if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case :/退栈并将运算结果入栈 theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; 六、流程图如下：c!=#|GetTop(OPTR)!=#!In（c）case :操作数栈头两个数进行运算进操作符栈c=*ptr+;Return GetTop2(OPND)char c=表达式首字符七、程序代码#include #include #include #define STACK_INIT_SIZE 100 #define status int#define SElemType float#define ERROR 0#define OK 1typedef structSElemType *base;SElemType *top;int stacksize;SqStack;void InitStack(SqStack &S)/初始化顺序栈 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(1); S.top=S.base; S.stacksize=STACK_INIT_SIZE;status GetTop(SqStack S, SElemType &e)/取栈顶元素的值 if(S.base=S.top) return ERROR; else e=*(S.top-1); return OK;status Push(SqStack &S, SElemType e)/入栈操作 if(S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+10)*sizeof(SElemType); if(!S.base) return ERROR; S.top=S.base+S.stacksize; else *S.top+=e; return OK;status Pop(SqStack &S, SElemType &e)/出栈操作 if(S.base=S.top) return ERROR; else e=*(-S.top); return OK;status Empty(SqStack S)/判断栈是否为空的操作 if(S.base=S.top) return true; else return false;/此前全部为顺序栈的基本操作char Precede(char c1 ,char c2)/判定运算符的优先级 char r; switch(c2) case+: case-: if(c1=(|c1=#) r=; break; case*: case/: if(c1=*|c1=/|c1=) r=; else r=; break; case(: if(c1=) printf(括号匹配错误!n); exit(-1); else r=; break; case#: switch(c1) case#: r=; break; case(: printf(error!没有右括号!n); exit(-1); default: r=; /switch break; /switch return r;/Precedebool In(char d)/判断c是否为七种运算符之一 switch(d) case+: case-: case*: case/: case(: case): case#: return true; default: return false; /switchSElemType Operate( SElemType a, SElemType theta, SElemType b )/Operate为进行二元运算的a theta b的函数 char n=char(theta);/此处把double型强制转换成int型，虽然会造成精度缺失，但本身theta是一个符号，也算是整型 switch(n) /转换后相当于和符号匹配ACSII码 case+: return a+b; case-: return a-b; case*: return a*b; default: if(b!=0) return a/b; else printf(error!除数不能为零n); exit(-1); /switchSElemType EvaluateExpression() /算符表达式的优先算法。设OPTR和OPND分别为运算符栈和运算数栈 SqStack OPTR,OPND; char c; char Data11;/定义此数组为了存放整数或小数 SElemType a,b,d,e; InitStack(OPTR);/构造一个运算符栈 InitStack(OPND);/构造一个运算数栈 Push(OPTR,#);/将#压入栈底 c=getchar(); GetTop(OPTR,e); while(c!=#|e!=#)/栈顶不是#号且输入不是#号 if(In(c)/是符号则进栈 switch(Precede(e,c) case: /退栈并将运算结果入栈 Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b); break; /switch else if(c=0&c=0&c=9|c=.) Datai=c; i+; c=getchar(); Datai=0;/数字没有存满,输入字符串结束符 d=atof(Data);/此处是把数组里的数字，实际上是按字符串；转换为double类型，然后把浮点型数字入栈 Push(OPND,d);/atof函数的形参是指针类型，故用数组名 else printf(error!输入错误!n); exit(-1); GetTop(OPTR,e); /while GetTop(OPND,e); return e;/EvaluateExpressionvoid main() SElemType result; printf(请输入表达式，以#号结束n); result=EvaluateExpression(); printf(结果为:%f:n,result);八、调试及运行结果 1、程序调试 1）使用Microsoft visual c+ 编辑软件进行源程序的编写。 2）使用Microsoft visual c+软件进行编译，步骤：按F7。 3）使用Microsoft visual c+运行程序并调试，步骤：（1） 按F7；（2）按Ctrl+F5。 2、运行及程序界面 1）编辑程序界面图一 2）执行程序及运行后界面图二 -Configuration:0-Win32Debug-Linking.0. exe - 0 error(s), 0 warning(s)图三3）运行过程 1、输入正确的表达式后2、更改表达式九：总结通过此次的课程设计，更加清楚了算术表达式求值的过程，同时也更加深刻的理解了栈的相关知识。更加深刻的知道程序设