算术表达式的求解数据结构课程设计说明书.doc
中北大学数 据 结 构课 程 设 计 说 明 书 学生姓名: 张蓓学 号：1021011602 学 院:软件学院专 业:软件工程 题 目:算术表达式的求解指导教师何志英 2011年12月20日1. 设计任务概述（包括系统总体框图及功能描述） 利用栈结构,求解用户正确输入的算术表达式,并实现保存、读取、清除功能，且对用户输入的错误信息进行提示,重新输入.按下”Q”键表达式错误表达式正确按下”S”键按下”R”键按下”E”键 求解算术表达式系统输入算术表达式 判断表达式 是否正确求解运算，得到结果提示错误，重新输入按下“N”键按下“Y”键退出？（Y/N）退出运算系统读取刚才保存的得数保存得数按下“Q”键2. 本设计所采用的数据结构（如：链表、栈、树、图等）本设计采用了栈结构，创建了两个栈，一个压入数字，另一个压入符号。3. 功能模块详细设计3.1 详细设计思想求解表达式的主要思想是创建两个栈，一个是符号栈，另一个是数字栈。符号栈关键是运算优先顺序，数字栈关键是多位数与小数的计算。本程序设计了四个模块，第一个模块double result(double num1,char op,double num2)，主要目的是进行加减乘除运算的操作方法，num1与num2的关系；第二个模块int compute(char str)，主要目的是对用户输入的算术表达式进行求解，其中对多位数与小数进行了定义与数值计算，以及带括号的表达式运算的优先顺序；第三个模块void face()，主要目的是设计用户主界面；第四个模块是主函数，主要目的是将上述模块集中运用，进行求解。至此完成利用栈结构求解表达式运算。3.2 核心代码调用的库函数:#include <stdio.h> #include <conio.h>#include <stdlib.h> #include <process.h> #include <string.h>自己定义的函数:1) double result(double num1,char op,double num2) 进行加减乘除运算2) int compute(char str) 对用户输入的算术表达式进行求解3) void face() 用户主界面4) main() 主函数核心定义函数设计：int compute(char str) double num=0; int i=0,j=1,k=1; int Flag=0; numTop=opTop=0; while(stri!='0'|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(stri='.') Flag=1; else if( k=1&&stri='-'&&(i=0|op(stri-1) ) k=-1; else if(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')') numStacknumTop+=num*k; num=0; j=1; Flag=0; k=1; if(opTop=0|stri='(') opStackopTop+=stri; else if(stri=')') while(opTop>0&&opStack-opTop!='(') numStacknumTop-2=result(numStacknumTop-2,opStackopTop,numStacknumTop-1); numTop-; if(opStackopTop!='(') return 0; else if(stri='0'&&numTop=0) return 0; while(opTop>0&&op(stri)<=op(opStackopTop-1) numStacknumTop-2=result(numStacknumTop-2,opStack-opTop,numStacknumTop-1); numTop-; if(stri!='0') opStackopTop+=stri; if(stri!='0') i+; if(numTop!=1|opTop!=0) return 0; return 1; 3.3 程序运行结果（拷屏）1 运行程序，打开程序界面 2 用户正确输入算术表达式的值 3 如果在输入过程中出现错误,例如,出现两个乘号,按c键清除 4 清除后5 正确输入算术表达式后按e得到正确结果6 按s键保存所得到的结果7 按r读出被保存的数据8 按q退出程序9 按Y退出4. 课程设计心得、存在问题及解决方法通过本次课程设计,我巩固了栈的建立,入栈,出栈的操作,提高了发现问题进而解决问题的能力，深化了数据结构的基本知识，并进行了拓展实践。最终，加强了程序设计的能力,并且能够有条理的安排各个函数的功能和位置。曾经存在的问题：1) 利用栈判断小数存在，并求解小数运算。2) 考虑各个运算符的优先顺序。解决方法：1) 利用小数点存在的判断，以及位数与数值的关系，除以十的倍数进行数值运算。2) 优先顺序自己先罗列一遍，以免遗漏。将+-*/数字化，以此代表优先顺序。（）单独处理。附：程序源代码：#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; /*界符堆栈栈顶相对栈底的偏移量,可以用来判断堆栈是否为空*/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(op='*') return num1*num2; if(op='/') return num1/num2; return 0; int compute(char str) /*利用栈结构对算术表达式进行求解,分析表达式*/ double num=0; int i=0,j=1,k=1; /*j代表小数点后位数，k代表数字符号（正负）*/ int Flag=0; /*Flag=0表示不是小数位，1表示是小数位*/ numTop=opTop=0; while(stri!='0'|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(stri='.') /*那么它是否小数点*/ Flag=1; /*设置标志,表明下一个应该是小数位,如果下一个不是小数位,应该归零*/ else /*如果当前字符不是阿拉伯数字字符,也不是小数点*/ if( k=1&&stri='-'&&(i=0|op(stri-1) ) /*如果当前字符是'-',符号标志为1,当前是第一个字符或前一个字符为'+','-','*','/','('这些字符*/ k=-1; else if(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是'+','-','*','/','(',')'这些字符,且当前字符不是'('*/ numStacknumTop+=num*k; /*压num*k入操作数堆栈*/ num=0; j=1; Flag=0; k=1; if(opTop=0|stri='(') opStackopTop+=stri; /*如界符堆栈为空或当前字符为'(',将当前字符压入界符堆栈*/ else if(stri=')') /*若当前字符为')'*/ while(opTop>0&&opStack-opTop!='(') numStacknumTop-2=result(numStacknumTop-2,opStackopTop,numStacknumTop-1); numTop-; /*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送入操作数堆栈*/ /*直到遇到界符'(',这是正常情况,或者界符堆栈为空,这表明表达式是有错误的*/ if(opStackopTop!='(') return 0; else /*界符堆栈非空,当前字符不是'(',也不是')'*/ if(stri='0'&&numTop=0) return 0; /*如果表达式结束,或操作数堆栈已空,返回调用处*/while(opTop>0&&op(stri)<=op(opStackopTop-1) numStacknumTop-2=result(numStacknumTop-2,opStack-opTop,numStacknumTop-1); numTop-; /*分别从操作数堆栈,界符堆栈出栈响应元素执行计算,结果送操作数堆栈*/ /*直到当前运算符的优先级低于栈元素的优先级,把当前字符压栈*/ if(stri!='0') opStackopTop+=stri; if(stri!='0') i+; if(numTop!=1|opTop!=0) return 0; return 1; /*程序主界面*/void face() system("cls"); printf(" _n"); printf(" 保存数据 (S) | 读数 (R) | 清除 (C) | 等于 (E) | 退出 (Q) n"); printf(" -n"); /*主函数*/main() int i=0,j=0,k; char strN="0" char numN="0" char saveN="0" char ch; double temp; unsigned long temp2; face(); /*调用face函数*/ printf("n请输入一个算术表达式,按'E'得到结果 n"); ch=getch(); while( 1 ) if(ch='.'|ch=')'|op(ch)|ch>='0'&&ch<='9') stri+=ch; stri='0' face(); /*调用face函数*/ printf("请输入一个算术表达式,按'E'得到结果n"); printf("%s",str); if( ch='-'&&(i=1|op(stri-2)|ch>='0'&&ch<='9' ) numj+=ch; numj='0' else j=0; if(ch='S'|ch='s') /*保存数据*/ if(strlen(num) face(); /*调用face函数*/ printf("%s 已经被保存n",strcpy(save,num); /*将num中的算术表达式保存到save中*/ printf("请输入一个算术表达式,按'E'得到结果n"); printf("%s",str); else face(); /*调用face函数*/ printf("没有数据被保存!n"); /*没有输入算术表达式*/ printf("请输入一个算术表达式,按'E'得到结果n"); printf("%s",str); if(ch='R'|ch='r') /*读取数据*/ if(strlen(save) /*将保存的数据读出*/ face(); /*调用face函数*/ printf("请输入一个算术表达式,按'E'得到结果n"); printf("%s",strcat(str,save); /*输出保存的数据*/ i+=strlen(save); if(ch='C'|ch='c') /*清除数据*/ if(strlen(str) str-i='0' face(); /*调用face函数*/ printf("请输入一个算术表达式,按'E'得到结果n"); printf("%s",str); if(ch='E'|ch='e') /*求算术表达式的值*/ if(compute(str) printf("n=%gn",numStack0); j=0; temp=numStack0; else face(); /*调用face函数*/ printf("请输入一个算术表达式,按'E'得到结果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 /*否定退出，程序继续运行*/ face(); /*调用face函数*/ printf("请输入一个表达式,按'E'得到结果n"); printf("%s",str); ch=getch();
