《数据结构课程设计-算术表达式求值》由会员分享，可在线阅读，更多相关《数据结构课程设计-算术表达式求值（7页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 报 告课程名称数据结构课程设计题目算术表达式求值指导教师设计起始日期4.184.25 学院计算机学院系别计算机科学与工程学生姓名班级/学号成绩名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -一、需求分析设计一个算术表达式四则运算的程序，要求完成包括加、减、乘、除运算，包含括号的基本整数表达式的运算。在这里运算数可以1 位长度，也可以多位长度。在运算之后输出的正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。（1）输入：3*（7-2）（2）输出：数据栈栈顶元素：3,7,2,7,5,3,15结果：15（3）自选数据二、概要
2、设计1、使用栈的数据结构表示数据的存储。2、设计算法将中缀表达式转换成后缀表达式，用栈的数据结构实现表达式的运算。3、把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。三、详细设计数据结构：字符类型栈/*定义字符类型栈*/typedefstruct char stackname20;char *base;char *top;Stack;算法：将中缀表达式转换为后缀表达式void Change(char*s1,char*s2)/将字符串 s1中的中缀表达式转换为存于字符串s2中的后缀表达式 Stack R;/定义用于暂存运算符的
3、栈InitStack(R);/初始化栈Push(R,#);/给栈底放入#字 符，它具有最低优先级0 int i,j;i=0;/用于指示扫描s1串中字符的位置，初值为0 j=0;/用于指示 s2串中待存字符的位置，初值为0 char ch=s1i;/ch保存 s1串中扫描到的字符，初值为第一个字符while(ch!=#)/顺序处理中缀表达式中的每个字符if(ch=)/对于空格字符不做任何处理，顺序读取下一个字符ch=s1+i;else if(ch=()/对于左括号，直接进栈Push(R,ch);ch=s1+i;else if(ch=)/对于右括号，使括号内的仍停留在栈中的运算符依次名师资料总结-
4、精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -/出栈并写入到s2中while(Peek(R)!=()s2j+=Pop(R);Pop(R);/删除栈顶的左括号ch=s1+i;else if(ch=+|ch=-|ch=*|ch=/)/对于四则运算符，使暂存在栈中的不低于ch优先级/的运算符依次出栈并写入到s2中char w=Peek(R);while(Precedence(w)=Precedence(ch)/Precedence(w)函数返回运算符形参的优先级s2j+=w;Pop(R);w=Peek(R);四、调试分析调试：在设计过程中出现程序不能运行，发现不能找到结束标识符，因此在设
5、计的时候需要人为动态添加结束标识符#，顺利运行算法时间和空间分析：算法的运行时间主要花在while 循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n 个数据组成，则 此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S 的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个数与运算符（假定把#也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。五、使用说明和测试结果1、使用说明：用户按照屏幕所显示的提示来输入表达式2、测试结果：名师资料总结-精品资料欢迎下载-名师精心整
6、理-第 3 页，共 7 页 -名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -六、心得体会本次实验熟悉了栈数据结构的表示与实现方法，以及表达式中中缀与后缀的转换。七、附录1、初始化int InitStack(Stack*s,char *name)s-base=(char *)malloc(STACKSIZE*sizeof(char);if(!s-base)exit(ERROR);strcpy(s-stackname,name);s-top=s-base;return 1;int In(char ch)return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=
7、)|ch=#);void OutputStatus(void)char *s;/*step*/printf(n%-8d,+step);/*OPTR*/for(s=OPTR.base;s OPTR.top;s+)printf(%c,*s);printf(t);/*OPND*/for(s=OPND.base;s stackname;OutputStatus();if(strcmp(name,OPND)=0)printf(tPUSH(%s,%d),name,ch);else printf(tPUSH(%s,%c),name,ch);#endif*s-top=ch;s-top+;名师资料总结-精品资料
8、欢迎下载-名师精心整理-第 5 页，共 7 页 -return 0;char Pop(Stack*s)char p;#ifdef DEBUG OutputStatus();printf(tPOP(%s),s-stackname);#endif s-top-;p=*s-top;return (p);char GetTop(Stack s)char p=*(s.top-1);return (p);2、操作函数算法int Operate(int a,char op,int b)#ifdef DEBUG OutputStatus();printf(tOPERATE(%d,%c,%d),a,op,b);
9、#endifswitch(op)case+:return (a+b);case-:return (a-b);case*:return (a*b);case/:return (a/b);return 0;int EvalExpr(void)char c,theta,x,m,ch;int a,b;c=*ptr+;while(c!=#|GetTop(OPTR)!=#)if(!In(c)m=atoi(&c);Push(&OPND,m);c=*ptr+;elseswitch(Precede(GetTop(OPTR),c)case :theta=Pop(&OPTR);b=Pop(&OPND);a=Pop(
10、&OPND);Push(&OPND,Operate(a,theta,b);break;return GetTop(OPND);3、测试int main(void)char *pc;printf(输入表达式(以#结束):);gets(expr);pc=expr;if(expr0=0)printf(请输入正确的表达式n);printf(再次输入表达式(以#结束):);gets(expr);else while(*pc!=0)pc+;pc-;if(*pc!=#)printf(请保证表达式以#结束 n);printf(再次输入表达式(以#结束):);gets(expr);InitStack(&OPTR,OPTR);/*初始化运算符栈*/Push(&OPTR,#);/*将#压入运算符栈*/InitStack(&OPND,OPND);/*初始化操作数栈*/printf(nnresult:%dn,EvalExpr();system(pause);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -
