算术表达式的求解数据结构课程设计报告.pdf

《算术表达式的求解数据结构课程设计报告.pdf》由会员分享，可在线阅读，更多相关《算术表达式的求解数据结构课程设计报告.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.-可修编.课程设计报告 题目：算术表达式求值 一、需求分析 1、设计要求：给定一个算术表达式，通过程序求出最后的结果 1、从键盘输入要求解的算术表达式；2、采用栈结构进行算术表达式的求解过程；3、能够判断算术表达式正确与否；4、对于错误表达式给出提示；5、对于正确的表达式给出最后的结果；2、设计构想：为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作 OPND，用以寄存操作数或运算结果。在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入 OPND，操作符入 OPTR。在输入表达式的最后输入#，设定#的优先级最低，代表表达式输入结束。在表

2、达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。二、概要设计 1、本程序包含的模块：.-可修编.（1）栈模块实现栈抽象数据类型（2）运算模块实现数据表达式的运算（3）主程序模块 三、详细设计（1）栈模块 1、定义栈结构 struct Sqstack 算术运算式的求解 栈模块 主函数模块main 运算模块 初始化栈 定义栈结构 出栈 入栈 取栈顶元素 判断输入字符类型 判断符号

3、优先级 基础运算函数 运算函数 .-可修编.elemtype*top;/栈顶元素 elemtype*base;/栈底元素 int stacksize;/栈的大小 ;2、栈的基本操作 初始化栈 status initstack(struct Sqstack&s)s.base=(elemtype*)malloc(stack_size*sizeof(elemtype);if(!s.base)return OVERFLOW;s.top=s.base;s.stacksize=stack_size;return OK;入栈 status push(struct Sqstack&s,elemtype e).

4、-可修编.if(s.top-s.base=s.stacksize)s.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(elemtype);if(!(s.base)return OVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;*s.top+=e;return OK;出栈 elemtype pop(struct Sqstack&s)elemtype e;if(s.top=s.base)return ERROR;e=*-s.

5、top;.-可修编.return e;取栈顶元素 elemtype gettop(struct Sqstack&s)elemtype e;if(s.top=s.base)return ERROR;e=*(s.top-1);return e;（2）运算模块 1、判断输入字符 c 是否为操作符：若是，则返回1；否则，返回 0 int In(int c)char p10=+-*/()#;int i=0;while(pi!=0).-可修编.if(pi=c)return 1;i+;return 0;2、判断运算符的优先级 char precede(char top,char c)/该函数为判断当前运算符

6、与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回，前一个运算符小于当前运算符的优先级则返;break;case+:case-:if(top=#|top=().-可修编.result=;break;case*:case/:if(top=*|top=/|top=)result=;else result=;else result=;break;.-可修编.case(:result=;break;case:result=;break;default:printf(操作符输入错误！n);return result;3、运算函数 基础运算函数：实现相应的加、减、乘、除、乘方及带小括号

7、的基本数学运算并返回结果，其中 a，b 为两个操作数，theta 为操作符 elemtype operate(elemtype a,char theta,elemtype b)elemtype result;switch(theta)case+:result=a+b;break;case-:result=a-b;break;case*:result=a*b;break;case/:.-可修编.if(b=0)printf(nn 输入错误!分母不能为 0!n);result=0;else result=a/b;break;case%:if(b=0|b=NULL)printf(nn 输入错误!n);

8、return 0;break;else result=a%b;break;case:result=(int)pow(double)a,(double)b);break;default:printf(操作符输入错误！n);return result;.-可修编.运算函数 elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)/该函数为求表达式的值的整个操作过程，通过调用相应的函数实现遇到运算符则与栈顶运算符比较优先级,/若当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,同时两操作数出栈,进

9、行运算,所得结果入数栈,/重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#，运算结束。/若操作数为个位数，则直接将输入的字符减 48 后入栈，若为多位数，则通过 flag 来实现。若输入字符 c 为操作数且 flag=1(即操作数为多位数)，则将操作数栈的栈顶元素出栈后乘以 10，然后加上，（c-48）然后将二者的和入操作数栈。elemtype a,b,c,theta,e;initstack(optr);push(optr,#);initstack(opnd);c=getchar();int flag=0;.-可修编./当输入操作数时 flag=1

10、；当输入操作符时 flag=0；/当前输入为操作数且 flag=1 时，将操作数栈的栈顶元素出栈，然后将其和当前输入转换成相应的 int 类型 while(c!=#|gettop(optr)!=#)if(!In(c)/c 若为操作数则入 opnd 栈 if(flag=1)e=pop(opnd);/取栈顶元素 push(opnd,(e*10+(c-48);/将输入数在转化为 int 型，并将上次输入数*10 并与当前操作数相加，将结果如操作数栈 else push(opnd,c-48);flag=1;c=getchar();.-可修编.else flag=0;/当前字符为操作符，则入操作符栈，并

11、将 flag 置为 0 switch(precede(gettop(optr),c)/判断当前操作数与操作符栈中的栈顶元素的优先级 case:theta=pop(optr);b=pop(opnd);a=pop(opnd);push(opnd,operate(a,theta,b);break;/若当前操作符的优先级低于操作符栈的栈顶元素，则将操作符栈栈顶元素出栈，并将操作数栈的栈顶两个元素出栈，计算两个元素间以操作符栈栈顶元素为运算符的数学运算 /switch /if.-可修编./while return pop(opnd);（3）主程序模块 1、main 函数 void main(int ar

12、gc,char*argv)struct Sqstack opnd;/操作数栈 struct Sqstack optr;/操作符栈 initstack(opdn);initstack(optr);elemtype result;printf(*n);printf(算术运算式的求解);printf(n*n);printf(n 请输入算术运算表达式(以#结尾):n);printf(n);result=evaluate(opnd,optr);printf(n*n);.-可修编.printf(nn 运算的结果是:n n%dn,result);printf(n*n);四、调试分析 1、测试结果 1 测试数

13、据：3+7*2-1#测试结果：2 测试数据：(3+7)*2-1#测试结果：3 测试数据：1/0#测试结果：.-可修编.2、程序时间复杂度为 O（n）；3、设计中出现的问题：在开始的设计中没有注意除数不能为 0，后来加入 if(b=0)printf(分母为 0,the result is errorn);result=0;else result=a/b;break;来判断除数是否为 0 4、算法改进：1输入的操作数和操作码由于是字符串类型的，在原设计中实现的操作都是对个位数实现的，实用性不大，故在后来的设计中，通过一个标志 flag 实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算

14、 2开始只实现了加、减、乘、除及带小括号的数学运算，考虑到实用性，在后来的设计中引入 pow 函数，实现了乘方的运算，调整结果如下：.-可修编.3最初设计的运行界面过于单调，不够友好，改进时加入一些*调整 调整结果如下：五、课程设计总结 本学期是我第一次接触课程设计，发现了很多学习上的问题，也有很多收获。在这两周的时间里，我再一次复习并更深入的了解了数据结构及C 语言之中的相关知识，通过算术运算式的求解这一题目，形象深入的理解了栈结构及.-可修编.原理。同时，通过每一次的编译运行不断改进完善题目，并通过这一个不断改进的过程，完善自己的思想，增强了自己全面分析问题的能力。当然，第一次的课程设计我做的还不够好，还有很多不足，缺少实践，缺乏经验，但我相信，在今后的设计中，我会加倍努力，珍惜机会，将所学知识融会贯通并与实际相结合