《算数表达式求解课程设计说明书.docx》由会员分享，可在线阅读，更多相关《算数表达式求解课程设计说明书.docx（39页珍藏版）》请在三一文库上搜索。
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
4、.3 约束条件 以字符序列的形式从终端输入语法正确、不含变量的算术表达式 算法优先级别：3.3 需求规格3.3.1 系统总功能1）系统功能模块图11算术运算式的求解疋初义始栈化结栈构1片f主 函 数 模 块mai nr判 栈 空运 算 模 块判 断 输 入 字 符 类 型判断符号优先级基 础 运 算 函 数运 算 函 数（图一：系统功能模块图 ）2）系统流程图（图二：系统流程图）3）数据流图(图三：数据流图)3.4 功能需求：接受正确表达是后进行计算并输出结果。3.5 可靠性和可用性需求：接收错误表达式后反馈提示信息；退出程序时进行询问选择。3.6 约束 : 仅能输入规定字符。如：数字、运算符
5、号、小数点、括号、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.014. 本设计所采用的数据结构/* 操作数堆栈 */typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆栈 */typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;5.功能模块详细设计5.1栈结构功能功能模块设计（段冰倩完成）5
6、.1.2流程图初始化栈结构开辟内存空间栈顶赋初值结束（图四：栈的初始化）返回0结束（图五：栈的判空）（图六：入栈操作）出栈操作N（图七：出栈操作）返回栈顶下一位155.1.3源代码/操作数栈与界符栈初始化Stackl *lnit_nu mStack()nu mStack=(Stack1*)malloc(sizeof(Stack1);nu mStack->nu mTop=0;return nu mStack;Stack2 *ln it_opStack()opStack=(Stack2*)malloc(sizeof(Stack2);opStack->opTop=0;return opS
7、tack;/操作数栈判空int Empty_ numStack(Stack1 *n umStack)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;elsenumStack->numTop+;
8、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;elseopStack->opTop+;opStac
9、k->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 算术表达式计算模块设计(王东鹏完成)5.2.1 函数功能说明 :Computer 函数在本程序的功能是实现数与运算符号输入时的判定numResult 函数在本程序中的功能是通过在 computer 函数中对该函数的调用实现存储在 中的数值运算函数设计思路
10、( 1)通过建立一个字符串数组存放输入的数字字符和运算字符 (2)通过强制转换把字符串类型数据转换成双精度浮点型数据 (3)把数据和运算界符分别压栈在两个栈中，然后通过判断进行比较和出栈 运算5.2.2 流程图 (另附 )5.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='/
11、9;) 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>0) /*if(stri>='0'&&am
12、p;stri<='9') /*if(Flag=0)num=num*10+stri-'0' /*elsenum+=(stri-'0')/(j*10.0); /*如果当前字符是阿拉伯数字字符 */多位数计算 */小数计算 */j*=10;else /* 如果当前字符不是阿拉伯数字字符 */ if(stri='.') /* 那么它是否小数点 */Flag=1; /* 设置标志 , 表明下一个应该是小数位 , 如果下一个不是小 数位 ,应该归零 */else /* 如果当前字符不是阿拉伯数字字符 , 也不是小数点 */if( k=1
13、&&stri='-'&&(i=0|op(stri-1) ) /* 如果当前字符是 '-', 符号标志为 1, 当前是第一个字符或前一个字符为 '+','-','*','/','(' 这些字符 */ k=-1;elseif(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是 '+','
14、;-','*','/','(',')' 这些字符 , 且当前字符不是 '('*/numStack->datanumStack->numTop+=num*k;/* 压 num*k 入操作数堆栈 */num=0; j=1; Flag=0; k=1;if( opStack->opTop=0|stri='(')opStack->dataopStack->opTop+=stri;/* 如界符堆栈为空 或当前字符为 '(', 将当前字符压入界符堆栈 */el
15、seif(stri=')') /* 若当前字符为 ')'*/while(opStack->opTop>0&&opStack->data-opStack->opTop!='(')numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,o pStack->dataopStack->opTop,numStack->datanumStack->numTop-1);numStac
16、k->numTop-; /* 分别从操作数堆栈 , 界符堆栈出栈响应元素执行计算,结果送入操作数堆栈 */* 直到遇到界符 '(', 这是正常情况 , 或者界符堆栈为空 , 这表明表达式是有错误的 */ if(opStack->dataopStack->opTop!='(') return 0;else /* 界符堆栈非空 , 当前字符不是 '(', 也不是 ')'*/if(stri='0'&&numStack->numTop=0) return 0; /* 如果表达式结束
17、, 或操作数堆栈已空 , 返回调用处 */ 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->numTop-; /* 分
18、别从操作数堆栈 , 界符堆栈出栈响应元素执行计算 结果送操作数堆栈 */* 直到当前运算符的优先级低于栈元素的优先级, 把当前字符压栈 */if(stri!='0')opStackopTop+=stri; if(stri!='0') i+;if( numStack->numTop!=1|!Empty_opStack(opStack)return 0;return 1;5.3 输出模块、优先级选择模块(宋超峰完成)5.3.1 流程图(图九 ：主函数流程图)5.3.2 源代码int op(char ch) /* 将运算符映射为数字 , 表示优先级 */if(c
19、h='+'|ch='-') return 2;if(ch='*'|ch='/') return 3;if(ch='(') return -1;return 0;/* 程序主界面 */ void view()system("cls");n");n");printf("printf("printf("II算数表达式求解n");printf("n");printf("II清除 (C) 等于 (E) 退出 (Q)I
20、IIIn");printf("IIIIn");printf("IIIIn");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.1 流程图25(图十：选择模块)5
21、.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<='9')stri+=ch;stri='0'view();printf("n请输入一个长度小于d的算术表达式，按'E'得到结果n&q
22、uot;,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') /* 清除数据 */if(strlen(str)str-i='0'view();printf("n 请输入一个长度小于 %d 的 算 术 表 达 式 , 按 'E' 得
23、 到 结 果 n",N);printf("%s",str);if(ch='E'|ch='e') /* 求算术表达式的值 */if(compute(str)printf("n=%gn",numStack->data0);j=0; temp=numStack->data0;elseview();printf("n 请输入一个长度小于 %d 的 算 术 表 达 式 , 按 'E' 得 到 结 果 n",N);printf("%s",str);print
24、f("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();printf("n请输入一个长度小于 %d 的 算 术 表 达 式 , 按 'E' 得 到 结 果n",N);printf("
25、;%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; /* 操作数堆栈栈顶相对栈底的偏移量/char opStackN;/int opTop; /* 界符堆栈栈顶相对栈底的偏移量/*
26、 操作数堆栈 */typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆栈 */typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;/ 操作数栈与界符栈初始化Stack1 *Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack->numTop=0;return numStack;Stack2 *Init_opStack()opStack=(Stack2*)malloc(s
27、izeof(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->num
28、Top=N-1) return 0;elsenumStack->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->opTo
29、p=N-1) return 0;elseopStack->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(
30、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(op='*') return num1*num2;if(op='/') return num1/num2; return 0;int comput
31、e(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>0) /* if(stri>='0'&&stri<='9') /*if(Flag=0)num
32、=num*10+stri-'0' /*elsenum+=(stri-'0')/(j*10.0); /*如果当前字符是阿拉伯数字字符 */多位数计算 */小数计算 */37j*=10;else /* 如果当前字符不是阿拉伯数字字符 */if(stri='.') /*那么它是否小数点 */Flag=1;/*设置标志 , 表明下一个应该是小数位 , 如果下一个不是小数位 ,应该归零 */else /*如果当前字符不是阿拉伯数字字符 , 也不是小数点*/if(k=1&&stri='-'&&(i=0|op(s
33、tri-1) /*如果当前字符是符号标志为 1, 当前是第一个字符或前一个字符为 '+','-','*','/','这些字符 */k=-1;elseif(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是 '+','-','*','/','(',')'这些字符 , 且当前字符不是&
34、#39;('*/numStack->datanumStack->numTop+=num*k;/* 压 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&
35、amp;&opStack->data-opStack->opTop!='(')numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->dataopStack->opTop,numStack->datanumStack->numTop-1);numStack->numTop-; /* 分别从操作数堆栈 , 界符堆栈出栈响应元素执行计算结果送入操作数堆栈 */* 直到遇到界符 '(',
36、 这是正常情况 , 或者界符堆栈为空 , 这表明表达式是有错误的 */if(opStack->dataopStack->opTop!='(') return 0;else /* 界符堆栈非空 , 当前字符不是 '(', 也不是 ')'*/if(stri='0'&&numStack->numTop=0) return 0; /*如果表达式结束 , 或操作数堆栈已空 , 返回调用处 */ while(opStack->opTop>0&&op(stri)<=op(opS
37、tack->dataopStack->opTop-1)numStack->datanumStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->data-opStack->opTop,numStack->datanumStack->numTop-1);numStack->numTop-; /* 分别从操作数堆栈 , 界符堆栈出栈响应元素执行计算 结果送操作数堆栈 */* 直到当前运算符的优先级低于栈元素的优先级 , 把当前字符压栈 */if(stri!=&
38、#39;0')opStackopTop+=stri;if(stri!='0')i+;if( numStack->numTop!=1|!Empty_opStack(opStack)return 0;return 1;/* 程序主界面 */void view()system("cls");n");printf("printf("printf("printf(" n");printf(" n");printf(" n");printf(" n
39、");printf(" n");printf("IIIIIIn");II算数表达式求解n");清除 (C) 等于 (E) 退出 (Q)IIIIIIII制作： 段冰倩 宋超峰 杨建波 王东鹏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&g
40、t;='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' )numj+=ch;numj='0'else j
41、=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",numStack->data0);j=0;
42、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();if(ch='Y'|ch
43、='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截图£3 P'UscrAyy'gjkeFA算贵表达式甜狀算乔恵达式求瞩（憨的学卡泌式我解舷诵常 = |回（此页附在说明书后，请在验收前填好）班级：11210F02题目：算术表达式求解学号姓名设计模块成绩1121010705段冰倩栈结构功能功能模块1121010714宋超峰输出模块、优先级选择模块11210110王东鹏算术表达式计算模块11210110杨建波选择功能模块