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

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

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

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

4、语法正确、不含变量的算术表达式算法优先级别：3.3 需求规格3.3.1 系统总功能1) 系统功能模块图7算术运算式的求解运 算 模 块判 断 输 入 字 符 类 型判断符号优先级基 础 运 算 函（图一：系统功能模块图 ）2）系统流程图结束表达式计算系统（图二：系统流程图）3）数据流图(图三：数据流图)3.4 功能需求：接受正确表达是后进行计算并输出结果。3.5 可靠性和可用性需求：接收错误表达式后反馈提示信息；退出程序时进行询问选择。3.6 约束 : 仅能输入规定字符。如：数字、运算符号、小数点、括号、Q、 C、 E。3.7 尚未解决的问题：无法记录计算过的数据。4. 测试用例(2+16)/

5、9 ， 13*3 ， -5+3， -5*21 ， -2/8 ， 2-3 ， 1.0000000*5 ， 0.975000/0.015. 本设计所采用的数据结构/* 操作数堆栈*/typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆栈*/typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;6. 功能模块详细设计6.1 栈结构功能功能模块设计（段冰倩完成）6.1.1 流程图（图四：栈的初始化）结束（图五:栈的判空）N（图六：入栈操作）出栈操作1，9判空

6、返回栈顶下一位（图七：出栈操作）6.1.2 源代码/操作数栈与界符栈初始化Stackl *Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack->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=

7、0) return 1;else return 0;13/ 界符栈判空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;elsenumStack->numTop+;numStack->datanumStack->numTop=x;return 1;/ 出栈(操作数)double Pop_num

8、Stack(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;elseopStack->opTop+;opStack->dataopStack->opTop=x;return 1;/ 出栈(界符)int Pop_opStack(Stack2 *

9、opStack,char*x)if(Empty_opStack(opStack) return 0;else return(opStack->dataopStack->-opTop);6.2 算术表达式计算模块设计(王东鹏完成)6.2.1 函数功能说明:Computer 函数在本程序的功能是实现数与运算符号输入时的判定numResult 函数在本程序中的功能是通过在computer 函数中对该函数的调用实现存储在中的数值运算函数设计思路(1 )通过建立一个字符串数组存放输入的数字字符和运算字符( 2)通过强制转换把字符串类型数据转换成双精度浮点型数据( 3)把数据和运算界符分别压栈

10、在两个栈中，然后通过判断进行比较和出栈运算6.2.2 流程图 (另附 )6.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 compute(char str) /

11、* Init_numStack();Init_opStack();double num=0;17int i=0,j=1,k=1; /*j代表小数点后位数，k 代表数字符号(正负)*/int Flag=0; /*Flag=0表示不是小数位，1 表示是小数位*/while(stri!='0'|opStack->opTop>0) /*if(stri>='0'&&stri<='9')/*if(Flag=0)num=num*10+stri-'0'/*elsenum+=(stri-'0'

12、)/(j*10.0);/*如果算术表达式不为空*/如果当前字符是阿拉伯数字字符*/多位数计算*/小数计算*/j*=10;else /*如果当前字符不是阿拉伯数字字符*/if(stri='.')/*那么它是否小数点*/Flag=1; /*设置标志, 表明下一个应该是小数位, 如果下一个不是小数位 , 应该归零*/else /*如果当前字符不是阿拉伯数字字符, 也不是小数点*/if(k=1&&stri='-'&&(i=0|op(stri-1) /* 如果当前字符是'-', 符号标志为1, 当前是第一个字符或前一个字符为

13、'+','-','*','/','('这些字符*/k=-1;elseif(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')')/*i>0且前一字符不是'+','-','*','/','(',')'这些字符, 且当前字符不是'('*/*压num*k入操numStack->datan

14、umStack->numTop+=num*k;作数堆栈*/num=0; j=1; Flag=0; k=1;if( opStack->opTop=0|stri='(') opStack->dataopStack->opTop+=stri;/*如界符堆栈为空或当前字符为'(', 将当前字符压入界符堆栈*/elseif(stri=')') /*若当前字符为')'*/while(opStack->opTop>0&&opStack->data-opStack->opTop!=&

15、#39;(')numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->dataopStack->opTop,numStack->datanumStack->numTop-1);numStack->numTop-; /* 分别从操作数堆栈, 界符堆栈出栈响应元素执行计算,结果送入操作数堆栈*/* 直到遇到界符'(', 这是正常情况, 或者界符堆栈为空, 这表明表达式是有错误的*/if(opStack->d

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

17、>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( numSta

18、ck->numTop!=1|!Empty_opStack(opStack)return 0;return 1;6.3 输出模块、优先级选择模块（宋超峰完成）6.3.1 流程图（图九：主函数流程图）6.3.2 源代码int op（char ch） /*将运算符映射为数字, 表示优先级*/if(ch='+'|ch='-') return 2;if(ch='*'|ch=7') return 3;if(ch='(') return -1;return 0;)/*程序主界面*/void view()(system("

19、cls");printf("n");printf("(>n");printf("I算数表达式求解I n");printf("< 、n")；printf("II 清除(C)等于(E) 退出(Q) |IIn");printf("'7IIn");printf("(、n");printf("'1 制作： 段冰倩宋超峰杨建波王东鹏 I)n");printf("'7n");) voi

20、d main() (char ch;system("color 03");view();printf（"n请输入一个长度小于d的算术表达式,按'E'得到结果n",N）;ch=getch();select（ch）;6.4 选择功能模块（杨建波完成）6.4.1 流程图37(图十：选择模块)6.4.2 源代码void select(char ch) int compute(char str);int i=0,j=0;char strN="0"char numN="0"double temp;while(

21、1 )if(ch='.'|ch=')'|op(ch)|ch>='0'&&ch<='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' )n

22、umj+=ch;numj='0'else j=0; if(ch='C'|ch='c')/*清除数据*/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",num

23、Stack->data0);j=0; temp=numStack->data0;elseview();printf("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

24、();if(ch='Y'|ch='y') break;else /*否定退出，程序继续运行*/view();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 <s

25、tring.h>#define N 100/double numStackN=0;/int numTop; /* 操作数堆栈栈顶相对栈底的偏移量, 可以用来判断堆栈是否为空*/char opStackN;/int opTop; /* 界符堆栈栈顶相对栈底的偏移量, 可以用来判断堆栈是否为空*/* 操作数堆栈*/typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆栈*/typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;/ 操作数栈与界符栈初始

26、化Stack1 *Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack->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;/ 界符栈判空in

27、t 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;elsenumStack->numTop+;numStack->datanumStack->numTop=x;return 1;/ 出栈(操作数)double Pop_numStack(Stack1 *numStack,char*x)if(Empt

28、y_numStack(numStack) return 0;else return(numStack->datanumStack->numTop);/ 入栈(界符)int Push_opStack(Stack2 *opStack,char x)if(opStack->opTop=N-1) return 0;elseopStack->opTop+;opStack->dataopStack->opTop=x;return 1;/ 出栈(界符)int Pop_opStack(Stack2 *opStack,char*x)if(Empty_opStack(opSta

29、ck) 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 num1,char op,double num2) /*if(op='+') return num1+

30、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表示不是小数位，1 表示是小数位

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

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

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

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

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

36、;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-opStack->opTop,numStack->datanumStack-&g

37、t;numTop-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"

38、;);printf("(、n");printf("I算数表达式求解I n");printf("( I、n");printf("III 清除(C)等于(E) 退出(Q)|n");printf("''n");printf("(>n");printf("'1 制作： 段冰倩宋超峰杨建波王东鹏 In");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=')'110P(ch)11ch>='0'&