算术表达式求值演示程序.doc

数 理 学 院课程设计报告书课程名称 数据结构课程设计 设计题目 算术表达式求值演示 专业班级 学 号 姓 名 指导教师 2014 年 12 月1设计时间2014年12月232014年12月29日2 设计目的设计一个程序，演示算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。3设计任务(1)设置运算符栈和运算数栈辅助分析算符优先关系；(2)在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算；(3)在识别出运算数的同时，要将其字符序列形式转换成整数形式；(4)在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。4 设计内容 4.1需求分析4.1.1该程序能实现算术四则运算表达式的求值，显示运算过程。4.1.2输入的形式：表达式，例如5*（3+7）#。包含的运算符只能有+、 -、*、 /、 ( ) ；4.1.3输出的形式：运算结果，50。4.1.4程序所能达到的功能：对表达式求值并输出。4.2总体设计4.2.1.栈的抽象数据类型定义：ADT Stack数据对象：D=ai|aiChar,i=1,2.,n,n0数据关系：R1=ai-1,ai|ai-1,aiD,i=2,3.n约定an端为栈顶，ai端为栈底4.2.2基本操作： 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主程序的流程：EvaluateExpression()函数实现了对表达式求值的功能，main()函数直接调用EvaluateExpression()对输入的表达式求值输出。算法流程图4.2.3函数的调用关系图ReturnOpOrdmainprecede InPopPushEvaluateExpression输出Operate4.3详细设计4.3.1. 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优先关系*/ 利用该算法对算术表达式4*(6-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#4*(6-2)#Push(OPND,4)2#4*(6-2)#Push(OPTR,*)3#*4(6-2)#Push(OPNR,()4#*(46-2)#Push(OPND,6)5#*(4 6-2)#Push(OPNR,-)6#*(-4 62)#Push(OPND,2)7#*(-4 6 2)#Operate(6,-,2)8#*(4 4)#Pop(OPTR)9#*4 4#Operate(4,*,4)10#16#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; 4.3.2主函数和其他函数的伪码int main( ) printf(请输入正确的表达式以#结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,#); /* 将#压入运算符栈 */ InitStack2(&OPND); /* 初始化操作数栈 */ printf(表达式结果为:%dn, EvalExpr();return 0; 4.3.3 函数的调用关系图ReturnOpOrdmainprecede InPopPushEvaluateExpression输出Operate 调用关系图4.4测试与分析4.4.1测试4.4.2实验分析：表达式求值程序是一个多次调用函数的过程，且调用的过程较为复杂，调试花费时间较多。在while循环时指针移动容易出错，因此多次出现内存错误，对于涉及的循环的操作开始和结束条件设置很关键。本次实验熟悉了栈数据结构的表示与实现方法。算法时间和空间分析：算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则 此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个 数与运算符（假定把#也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。4.5 附录源程序：#include #include #include #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;/* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/Stack2 OPND; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE;return OK; int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stacksize=STACK_INIT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) /运算符栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈s的栈顶元素，用p返回其值 char p;s-top-; p=*s-top; return p; int Pop2(Stack2 *s)/删除操作数栈s的栈顶元素，用p返回其值 int p;s-top-; p=*s-top; return p;char GetTop(Stack s)/用p返回运算符栈s的栈顶元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用p返回操作数栈s的栈顶元素 int p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的 */ char Precede(char c1,char c2) int i=0,j=0; static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; 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); /* 返回运算符 */ /*操作函数 */ int Operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); return 0; int num(int n)/返回操作数的长度 char p10;itoa(n,p,10);/把整型转换成字符串型n=strlen(p);return n;int EvalExpr()/主要操作函数 char c,theta,x; int n,m;int a,b; 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; return GetTop2(OPND); int main( ) printf(请输入正确的表达式以#结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,#); /* 将#压入运算符栈 */ InitStack2(&OPND); /* 初始化操作数栈 */ printf(表达式结果为:%dn, EvalExpr();return 0; 5 总结与展望这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有