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

1、中北大学数 据 结 构课 程 设 计 说 明 书   学 院:电子与计算机科学技术学院班 级:1121010F02题 目:算术表达式的求解指导教师陈够喜学生学号1121010705112101071411210110171121011016学生姓名段冰倩宋超峰王东鹏杨建波成绩  2013 年 1月 17 日1 .设计目的数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：n 了解并掌握数据结构

2、与算法的设计方法，具备初步的独立分析和设计能力；n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；n 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2. 设计内容和要求2.1设计内容：（1）本案例要求从键盘中输入一串四则运算表达式，由计算机求出表达式的运算结果。（2）要求能够判断公式的正确性，如括号是否匹配，有没有算术表达式之外的字符（3）对于有错的表达式，要提示出错信息（4）对于正确的表达式，能够正确求出值2.2设计要求：(1)符合课题要求，实现相应功能；

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

4、序集成环境或 Visual C+ 程序集成环境 3.2.3 约束条件 以字符序列的形式从终端输入语法正确、不含变量的算术表达式 算法优先级别： 3.3需求规格3.3.1系统总功能1)系统功能模块图算术运算式的求解栈模块主函数模块main运算模块初始化栈定义栈结构出栈入栈判栈空判断输入字符类型判断符号优先级基础运算函数运算函数 （ 图一：系统功能模块图 ）2） 系统流程图算数表达式求解系统 输入表达式输出“表达式错误”表达式是否正确 N Y求解运算输出计算结果是否退出 N Y结束表达式计算系统 （图二：系统流程图）3)数据流图 （图三：数据流图）3.4功能需求：接受正确表达是后进行计算并输出结果

5、。3.5可靠性和可用性需求：接收错误表达式后反馈提示信息；退出程序时进行询问选择。3.6约束:仅能输入规定字符。如：数字、运算符号、小数点、括号、Q、C、E。3.7尚未解决的问题：无法记录计算过的数据。4. 测试用例 (2+16)/9，13*3，-5+3，-5*21，-2/8，2-3，1.0000000*5，0.975000/0.01 4.本设计所采用的数据结构/*操作数堆栈*/typedef struct double dataN; int numTop;Stack1;Stack1 *numStack;/*界符堆栈*/typedef struct char dataN; int opTop;

6、Stack2;Stack2 *opStack;5.功能模块详细设计5.1 栈结构功能功能模块设计（段冰倩完成）5.1.2流程图初始化栈结构 开辟内存空间栈顶赋初值结束 （图四：栈的初始化）栈的判空函数栈顶是否为0 N Y返回0返回1结束 （图五：栈的判空）入栈函数 栈满判断 N栈顶上移一位 Y返回0赋值返回1结束 （图六：入栈操作） 出栈操作判空 N Y返回栈顶下一位结束 （图七：出栈操作）5.1.3源代码/操作数栈与界符栈初始化Stack1 *Init_numStack() numStack=(Stack1*)malloc(sizeof(Stack1); numStack->numTo

7、p=0; return numStack;Stack2 *Init_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

8、 0;/入栈（操作数）int Push_numStack(Stack1 *numStack,char x) 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-&g

9、t;numTop);/入栈（界符）int Push_opStack(Stack2 *opStack,char x) if(opStack->opTop=N-1) return 0; 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);5.2

10、 算术表达式计算模块设计（王东鹏完成）5.2.1函数功能说明:Computer函数在本程序的功能是实现数与运算符号输入时的判定Result函数在本程序中的功能是通过在computer函数中对该函数的调用实现存储在num 中的数值运算函数设计思路（1）通过建立一个字符串数组存放输入的数字字符和运算字符 （2）通过强制转换把字符串类型数据转换成双精度浮点型数据 （3）把数据和运算界符分别压栈在两个栈中，然后通过判断进行比较和出栈 运算5.2.2 流程图(另附) 5.2.3源代码double result(double num1,char op,double num2) /*执行运算*/ if(op

11、='+') 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=

12、0; /*Flag=0表示不是小数位，1表示是小数位*/ while(stri!='0'|opStack->opTop>0) /*如果算术表达式不为空*/ if(stri>='0'&&stri<='9') /*如果当前字符是阿拉伯数字字符*/ if(Flag=0) num=num*10+stri-'0' /*多位数计算*/ else num+=(stri-'0')/(j*10.0); /*小数计算*/ j*=10; else /*如果当前字符不是阿拉伯数字字符*/ if(st

13、ri='.') /*那么它是否小数点*/ Flag=1; /*设置标志,表明下一个应该是小数位,如果下一个不是小数位,应该归零*/ else /*如果当前字符不是阿拉伯数字字符,也不是小数点*/ if( k=1&&stri='-'&&(i=0|op(stri-1) ) /*如果当前字符是'-',符号标志为1,当前是第一个字符或前一个字符为'+','-','*','/','('这些字符*/ k=-1; else if(i>0&

14、;&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是'+','-','*','/','(',')'这些字符,且当前字符不是'('*/ numStack->datanumStack->numTop+=num*k; /*压num*k入操作数堆栈*/ num=0; j=1; Flag=0; k=1; if( opStack->opTop=0|st

15、ri='(') opStack->dataopStack->opTop+=stri;/*如界符堆栈为空或当前字符为'(',将当前字符压入界符堆栈*/ else if(stri=')') /*若当前字符为')'*/ while(opStack->opTop>0&&opStack->data-opStack->opTop!='(') numStack->data numStack->numTop-2=result(numStack->datanumS

16、tack->numTop-2,opStack->dataopStack->opTop,numStack->datanumStack->numTop-1); numStack->numTop-; /*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送入操作数堆栈*/ /*直到遇到界符'(',这是正常情况,或者界符堆栈为空,这表明表达式是有错误的*/ if(opStack->dataopStack->opTop!='(') return 0; else /*界符堆栈非空,当前字符不是'(',也不是&

17、#39;)'*/ if(stri='0'&&numStack->numTop=0) return 0; /*如果表达式结束,或操作数堆栈已空,返回调用处*/while(opStack->opTop>0&&op(stri)<=op(opStack->dataopStack->opTop-1) numStack->datanumStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->data-opStac

18、k->opTop,numStack->datanumStack->numTop-1); numStack->numTop-; /*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送操作数堆栈*/ /*直到当前运算符的优先级低于栈元素的优先级,把当前字符压栈*/ if(stri!='0') opStackopTop+=stri; if(stri!='0') i+; if( numStack->numTop!=1|!Empty_opStack(opStack) return 0; return 1; 5.3 输出模块、优先级选择模块

19、（宋超峰完成）5.3.1流程图 （图九 ：主函数流程图）5.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"); printf(" n"); printf

20、(" 算数表达式求解 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的算术表达

21、式,按'E'得到结果 n",N); ch=getch(); select(ch);5.4 选择功能模块（杨建波完成）5.4.1流程图 （图十：选择模块）5.4.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<=

22、'9') stri+=ch; stri='0' view(); printf("n请输入一个长度小于%d的算术表达式,按'E'得到结果 n",N); printf("%s",str); if( ch='-'&&(i=1|op(stri-2)|ch>='0'&&ch<='9' ) numj+=ch; numj='0' else j=0; if(ch='C'|ch='c')

23、 /*清除数据*/ if(strlen(str) str-i='0' view(); printf("n请输入一个长度小于%d的算术表达式,按'E'得到结果 n",N); printf("%s",str); if(ch='E'|ch='e') /*求算术表达式的值*/ if(compute(str) printf("n=%gn",numStack->data0); j=0; temp=numStack->data0; else view(); printf(&

24、quot;n请输入一个长度小于%d的算术表达式,按'E'得到结果 n",N); printf("%s",str); printf("n输入的算术表达式有误!"); 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();

25、 printf("n请输入一个长度小于%d的算术表达式,按'E'得到结果 n",N); printf("%s",str); ch=getch(); 6.源代码#include <stdio.h> #include <conio.h>#include <stdlib.h> #include <process.h> #include <string.h> #define N 100 /double numStackN=0; /int numTop; /*操作数堆栈栈顶相对栈底的偏移量

26、,可以用来判断堆栈是否为空*/char opStackN; /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-&

27、gt;numTop=0; return numStack;Stack2 *Init_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; els

28、e return 0;/入栈（操作数）int Push_numStack(Stack1 *numStack,char x) 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->datanum

29、Stack->numTop);/入栈（界符）int Push_opStack(Stack2 *opStack,char x) if(opStack->opTop=N-1) return 0; 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->opT

30、op);int op(char ch) /*将运算符映射为数字,表示优先级*/ if(ch='+'|ch='-') return 2; if(ch='*'|ch='/') return 3; if(ch='(') return -1; return 0; double result(double num1,char op,double num2) /*执行运算*/ if(op='+') return num1+num2; if(op='-') return num1-num2; if

31、(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表示不是小数位，1表示是小数位*/ while(stri!='0'|opStack->opTop&

32、gt;0) /*如果算术表达式不为空*/ if(stri>='0'&&stri<='9') /*如果当前字符是阿拉伯数字字符*/ if(Flag=0) num=num*10+stri-'0' /*多位数计算*/ else num+=(stri-'0')/(j*10.0); /*小数计算*/ j*=10; else /*如果当前字符不是阿拉伯数字字符*/ if(stri='.') /*那么它是否小数点*/ Flag=1; /*设置标志,表明下一个应该是小数位,如果下一个不是小数位,应该归零

33、*/ else /*如果当前字符不是阿拉伯数字字符,也不是小数点*/ if( k=1&&stri='-'&&(i=0|op(stri-1) ) /*如果当前字符是'-',符号标志为1,当前是第一个字符或前一个字符为'+','-','*','/','('这些字符*/ k=-1; else if(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')

34、9;) /*i>0且前一字符不是'+','-','*','/','(',')'这些字符,且当前字符不是'('*/ numStack->datanumStack->numTop+=num*k; /*压num*k入操作数堆栈*/ num=0; j=1; Flag=0; k=1; if( opStack->opTop=0|stri='(') opStack->dataopStack->opTop+=stri;/*如界符堆栈为空或当前字符为

35、'(',将当前字符压入界符堆栈*/ else if(stri=')') /*若当前字符为')'*/ while(opStack->opTop>0&&opStack->data-opStack->opTop!='(') numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->dataopStack->opTop,numStack->datanu

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

37、 0; /*如果表达式结束,或操作数堆栈已空,返回调用处*/while(opStack->opTop>0&&op(stri)<=op(opStack->dataopStack->opTop-1) numStack->datanumStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->data-opStack->opTop,numStack->datanumStack->numTop-1); numStack->numTo

38、p-; /*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送操作数堆栈*/ /*直到当前运算符的优先级低于栈元素的优先级,把当前字符压栈*/ 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&q

39、uot;); printf(" 算数表达式求解 n"); printf(" n"); printf(" 清除 (C) 等于 (E) 退出 (Q) n"); 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>=