算数表达式求解课程设计说明书.doc

《算数表达式求解课程设计说明书.doc》由会员分享，可在线阅读，更多相关《算数表达式求解课程设计说明书.doc（37页珍藏版）》请在三一办公上搜索。

1、 中北大学中北大学 数数 据据 结结 构构 课课 程程 设设 计计 说说 明明 书书 学学 院院:电子与计算机科学技术学院电子与计算机科学技术学院 班班 级级:1121010F021121010F02 题题 目目:算术表达式的求解算术表达式的求解 指 导 教指 导 教 师师 陈够喜陈够喜 学 生 学学 生 学 号号 11210107051121010705 11210107141121010714 11210110171121011017 11210110161121011016 学 生 姓学 生 姓 名名 段冰倩段冰倩 宋超峰宋超峰 王东鹏王东鹏 杨建波杨建波 成成绩绩 2013 年 1 月

2、 17 日 1.设计目的设计目的 数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2.设计内容和要求设计内容和要求 2.1 设计内容：（1）本案例要求

3、从键盘中输入一串四则运算表达式，由计算机求出表达式的运算结果。（2）要求能够判断公式的正确性，如括号是否匹配，有没有算术表达式之外的字符（3）对于有错的表达式，要提示出错信息（4）对于正确的表达式，能够正确求出值 2.2 设计要求：(1)符合课题要求，实现相应功能；(2)要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性；3.3.需求分析需求分析 3.1 系统概述 表达式求值运算式实现程序设计语言基本问题之一，也是栈的应用的典型例子。深入了解栈和队列的特性，学会在实际应用中灵活运用。3.2 需求概述 3.2.1 目标 a.软件开发意图、目标及范围:本案例要求从键盘中输入一串四则运算

4、表达式，由计算机求出表达式的运算结果;要求能够判断公式的正确性，如括号是否匹配，有没有算术表达式之外的字符;对于有错的表达式，要提示出错信息。b.主要功能、处理流程、数据流程:3.2.2 运行环境 PC 微机 DOS 操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C+程序集成环境 3.2.3 约束条件 以字符序列的形式从终端输入语法正确、不含变量的算术表达式 算法优先级别：3.3 需求规格 3.3.1 系统总功能 1)系统功能模块图 （图一：系统功能模块图）算术运算式的求解 栈模块 主函数模块main 运算模块 初始化栈 定义栈结构 出栈 入栈 判栈空 判

5、断输入字符类型 判断符号优先级 基础运算函数 运算函数 2）系统流程图 N Y N Y （图二：系统流程图）3)数据流图 算数表达式求解系统 输入表达式 表达式是否正确 求解运算 输出计算结果 输出“表达式错误”是否退出 结束表达式计算系统 （图三：数据流图）3.4 功能需求：接受正确表达是后进行计算并输出结果。3.5 可靠性和可用性需求：接收错误表达式后反馈提示信息；退出程序时进行询问选择。3.6 约束:仅能输入规定字符。如：数字、运算符号、小数点、括号、Q、C、E。3.7 尚未解决的问题：无法记录计算过的数据。4.测试用例 (2+16)/9，13*3，-5+3，-5*21，-2/8，2-3

6、，1.0000000*5，0.975000/0.01 4.4.本设计所采用的数据结构本设计所采用的数据结构 /*操作数堆栈*/typedef struct double dataN;int numTop;Stack1;Stack1*numStack;/*界符堆栈*/typedef struct char dataN;int opTop;Stack2;Stack2*opStack;5.5.功能模块详细设计功能模块详细设计 5.1 5.1 栈结构功能功能栈结构功能功能模块设计（段冰倩完成）模块设计（段冰倩完成）5.1.25.1.2 流程图流程图 （图四：栈的初始化）N Y （图五：栈的判空）初始化

7、栈结构 开辟内存空间 栈顶赋初值 结束 栈的判空函数 栈顶是否为 0 结束 返回 1 返回 0 N Y （图六：入栈操作）N Y （图七：出栈操作）入栈函数 栈满判断 结束 栈顶上移一位 赋值 返回 1 返回 0 出栈操作 判空 返回栈顶下一位 结束 5.1.35.1.3 源代码源代码 /操作数栈与界符栈初始化 Stack1*Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack-numTop=0;return numStack;Stack2*Init_opStack()opStack=(Stack2*)malloc(si

8、zeof(Stack2);opStack-opTop=0;return opStack;/操作数栈判空 int Empty_numStack(Stack1*numStack)if(numStack-numTop=0)return 1;else return 0;/界符栈判空 int Empty_opStack(Stack2*opStack)if(opStack-opTop=0)return 1;else return 0;/入栈（操作数）int Push_numStack(Stack1*numStack,char x)if(numStack-numTop=N-1)return 0;else n

9、umStack-numTop+;numStack-datanumStack-numTop=x;return 1;/出栈（操作数）double Pop_numStack(Stack1*numStack,char*x)if(Empty_numStack(numStack)return 0;else return(numStack-datanumStack-numTop);/入栈（界符）int Push_opStack(Stack2*opStack,char x)if(opStack-opTop=N-1)return 0;else opStack-opTop+;opStack-dataopStack

10、-opTop=x;return 1;/出栈（界符）int Pop_opStack(Stack2*opStack,char*x)if(Empty_opStack(opStack)return 0;else return(opStack-dataopStack-opTop);5.2 5.2 算术表达式计算模块设计（王东鹏完成）算术表达式计算模块设计（王东鹏完成）5.2.1 函数功能说明:Computer 函数在本程序的功能是实现数与运算符号输入时的判定 Result 函数在本程序中的功能是通过在 computer 函数中对该函数的调用实现存储在 num 中的数值运算 函数设计思路（1）通过建立一个

11、字符串数组存放输入的数字字符和运算字符 （2）通过强制转换把字符串类型数据转换成双精度浮点型数据 （3）把数据和运算界符分别压栈在两个栈中，然后通过判断进行比较和出栈 运算 5.2.25.2.2 流程图流程图(另附另附)5.2.35.2.3 源代码源代码 double result(double num1,char op,double num2)/*执行运算*/if(op=+)return num1+num2;if(op=-)return num1-num2;if(op=*)return num1*num2;if(op=/)return num1/num2;return 0;int compu

12、te(char str)/*利用栈结构对算术表达式进行求解,分析表达式*/Init_numStack();Init_opStack();double num=0;int i=0,j=1,k=1;/*j 代表小数点后位数，k 代表数字符号（正负）*/int Flag=0;/*Flag=0 表示不是小数位，1 表示是小数位*/while(stri!=0|opStack-opTop0)/*如果算术表达式不为空*/if(stri=0&stri0&!op(stri-1)&stri!=(&stri-1!=)/*i0且前一字符不是+,-,*,/,(,)这些字符,且当前字符不是(*/numStack-data

13、numStack-numTop+=num*k;/*压num*k入操作数堆栈*/num=0;j=1;Flag=0;k=1;if(opStack-opTop=0|stri=()opStack-dataopStack-opTop+=stri;/*如界符堆栈为空或当前字符为(,将当前字符压入界符堆栈*/else if(stri=)/*若当前字符为)*/while(opStack-opTop0&opStack-data-opStack-opTop!=()numStack-data numStack-numTop-2=result(numStack-datanumStack-numTop-2,opStac

14、k-dataopStack-opTop,numStack-datanumStack-numTop-1);numStack-numTop-;/*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送入操作数堆栈*/*直到遇到界符(,这是正常情况,或者界符堆栈为空,这表明表达式是有错误的*/if(opStack-dataopStack-opTop!=()return 0;else /*界符堆栈非空,当前字符不是(,也不是)*/if(stri=0&numStack-numTop=0)return 0;/*如果表达式结束,或操作数堆栈已空,返回调用处*/while(opStack-opTop0&op(

15、stri)dataopStack-opTop-1)numStack-datanumStack-numTop-2=result(numStack-datanumStack-numTop-2,opStack-data-opStack-opTop,numStack-datanumStack-numTop-1);numStack-numTop-;/*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送操作数堆栈*/*直到当前运算符的优先级低于栈元素的优先级,把当前字符压栈*/if(stri!=0)opStackopTop+=stri;if(stri!=0)i+;if(numStack-numTop!

16、=1|!Empty_opStack(opStack)return 0;return 1;5.3 5.3 输出模块、优先级选择模块（宋超峰完成）输出模块、优先级选择模块（宋超峰完成）5.3.15.3.1 流程图流程图 （图九（图九 ：主函数流程图）：主函数流程图）5.3.25.3.2 源代码源代码 int op(char ch)/*将运算符映射为数字,表示优先级*/if(ch=+|ch=-)return 2;if(ch=*|ch=/)return 3;if(ch=()return-1;return 0;/*程序主界面*/void view()system(cls);printf(n);print

17、f(n);printf(算数表达式求解 n);printf(n);printf(清除(C)等于(E)退出(Q)n);printf(n);printf(n);printf(制作：段冰倩 宋超峰 杨建波 王东鹏 n);printf(n);void main()char ch;system(color 03);view();printf(n 请输入一个长度小于%d 的算术表达式,按E得到结果 n,N);ch=getch();select(ch);5.4 5.4 选择功能模块（杨建波完成）选择功能模块（杨建波完成）5.4.15.4.1 流程图流程图 （图十：选择模块）（图十：选择模块）5.4.25.4

18、.2 源代码源代码 void select(char ch)int compute(char str);int i=0,j=0;char strN=0;char numN=0;double temp;while(1)if(ch=.|ch=)|op(ch)|ch=0&ch=0&chdata0);j=0;temp=numStack-data0;else view();printf(n 请输入一个长度小于%d 的 算 术 表 达 式,按 E 得 到 结 果 n,N);printf(%s,str);printf(n 输入的算术表达式有误!);i=0;j=0;str0=0;if(ch=Q|ch=q)/*

19、退出程序*/printf(n 退出?（是 Y/否 N）n);ch=getch();if(ch=Y|ch=y)break;else /*否定退出，程序继续运行*/view();printf(n 请输入一个长度小于%d 的 算 术 表 达 式,按 E 得 到 结 果 n,N);printf(%s,str);ch=getch();6.6.源代码源代码#include#include#include#include#include#define N 100 /double numStackN=0;/int numTop;/*操作数堆栈栈顶相对栈底的偏移量,可以用来判断堆栈是否为空*/char opSt

20、ackN;/int opTop;/*界符堆栈栈顶相对栈底的偏移量,可以用来判断堆栈是否为空*/*操作数堆栈*/typedef struct double dataN;int numTop;Stack1;Stack1*numStack;/*界符堆栈*/typedef struct char dataN;int opTop;Stack2;Stack2*opStack;/操作数栈与界符栈初始化 Stack1*Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack-numTop=0;return numStack;Stack2*I

21、nit_opStack()opStack=(Stack2*)malloc(sizeof(Stack2);opStack-opTop=0;return opStack;/操作数栈判空 int Empty_numStack(Stack1*numStack)if(numStack-numTop=0)return 1;else return 0;/界符栈判空 int Empty_opStack(Stack2*opStack)if(opStack-opTop=0)return 1;else return 0;/入栈（操作数）int Push_numStack(Stack1*numStack,char x

22、)if(numStack-numTop=N-1)return 0;else numStack-numTop+;numStack-datanumStack-numTop=x;return 1;/出栈（操作数）double Pop_numStack(Stack1*numStack,char*x)if(Empty_numStack(numStack)return 0;else return(numStack-datanumStack-numTop);/入栈（界符）int Push_opStack(Stack2*opStack,char x)if(opStack-opTop=N-1)return 0;

23、else opStack-opTop+;opStack-dataopStack-opTop=x;return 1;/出栈（界符）int Pop_opStack(Stack2*opStack,char*x)if(Empty_opStack(opStack)return 0;else return(opStack-dataopStack-opTop);int op(char ch)/*将运算符映射为数字,表示优先级*/if(ch=+|ch=-)return 2;if(ch=*|ch=/)return 3;if(ch=()return-1;return 0;double result(double

24、num1,char op,double num2)/*执行运算*/if(op=+)return num1+num2;if(op=-)return num1-num2;if(op=*)return num1*num2;if(op=/)return num1/num2;return 0;int compute(char str)/*利用栈结构对算术表达式进行求解,分析表达式*/Init_numStack();Init_opStack();double num=0;int i=0,j=1,k=1;/*j 代表小数点后位数，k 代表数字符号（正负）*/int Flag=0;/*Flag=0 表示不是小

25、数位，1 表示是小数位*/while(stri!=0|opStack-opTop0)/*如果算术表达式不为空*/if(stri=0&stri0&!op(stri-1)&stri!=(&stri-1!=)/*i0且前一字符不是+,-,*,/,(,)这些字符,且当前字符不是(*/numStack-datanumStack-numTop+=num*k;/*压num*k入操作数堆栈*/num=0;j=1;Flag=0;k=1;if(opStack-opTop=0|stri=()opStack-dataopStack-opTop+=stri;/*如界符堆栈为空或当前字符为(,将当前字符压入界符堆栈*/e

26、lse if(stri=)/*若当前字符为)*/while(opStack-opTop0&opStack-data-opStack-opTop!=()numStack-data numStack-numTop-2=result(numStack-datanumStack-numTop-2,opStack-dataopStack-opTop,numStack-datanumStack-numTop-1);numStack-numTop-;/*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送入操作数堆栈*/*直到遇到界符(,这是正常情况,或者界符堆栈为空,这表明表达式是有错误的*/if(op

27、Stack-dataopStack-opTop!=()return 0;else /*界符堆栈非空,当前字符不是(,也不是)*/if(stri=0&numStack-numTop=0)return 0;/*如果表达式结束,或操作数堆栈已空,返回调用处*/while(opStack-opTop0&op(stri)dataopStack-opTop-1)numStack-datanumStack-numTop-2=result(numStack-datanumStack-numTop-2,opStack-data-opStack-opTop,numStack-datanumStack-numTop

28、-1);numStack-numTop-;/*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送操作数堆栈*/*直到当前运算符的优先级低于栈元素的优先级,把当前字符压栈*/if(stri!=0)opStackopTop+=stri;if(stri!=0)i+;if(numStack-numTop!=1|!Empty_opStack(opStack)return 0;return 1;/*程序主界面*/void view()system(cls);printf(n);printf(n);printf(算数表达式求解 n);printf(n);printf(清除(C)等于(E)退出(Q)n);

29、printf(n);printf(n);printf(制作：段冰倩 宋超峰 杨建波 王东鹏 n);printf(n);void select(char ch)int compute(char str);int i=0,j=0;char strN=0;char numN=0;double temp;while(1)if(ch=.|ch=)|op(ch)|ch=0&ch=0&chdata0);j=0;temp=numStack-data0;else view();printf(n 请输入一个长度小于%d 的算术表达式,按E得到结果 n,N);printf(%s,str);printf(n 输入的算

30、术表达式有误!);i=0;j=0;str0=0;if(ch=Q|ch=q)/*退出程序*/printf(n 退出?（是 Y/否 N）n);ch=getch();if(ch=Y|ch=y)break;else /*否定退出，程序继续运行*/view();printf(n 请输入一个长度小于%d 的算术表达式,按E得到结果 n,N);printf(%s,str);ch=getch();void main()char ch;system(color 03);view();printf(n 请输入一个长度小于%d 的算术表达式,按E得到结果 n,N);ch=getch();select(ch);7.截图截图 （此页附在说明书后，请在验收前填好）班级：11210F02 题目：算术表达式求解 学号 姓名 设计模块 成绩 1121010705 段冰倩 栈结构功能功能模块 1121010714 宋超峰 输出模块、优先级选择模块 11210110 王东鹏 算术表达式计算模块 11210110 杨建波 选择功能模块