数据结构实验报告总结
设计题目:模拟计算器程序 学生姓名:谢先斌 系 别:计算机与通信工程学院 专 业:计算机科学与技术 班 级:1班 学 号:541007010144 指导教师:卢冰 李晔 XX 年 6 月 21 日 郑州轻工业学院 课 程 设 计 任 务 书 题目 模拟计算器程序 专业、班级 计算机科学与技术10-01班 学号 541007010144 姓名 谢先斌 主要内容: 设计一个模拟计算器的程序,要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。 基本要求: 要检查有关运算的条件,并对错误的条件产生报警。 主要参考资料: 严蔚敏 吴伟民 编著《数据结构(C语言版)》 清华大学出版社 第44页 栈、第52页表达式求值 完 成 期 限: XX年6月21日 指导教师签名: 课程负责人签名: XX年 6月 21 日 一、 设计题目 模拟计算器的程序 设计一个模拟计算器的程序,要求能对包含加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。 设计要求:要检查有关运算的条件,并对错误的条件产生报警。 二、 算法设计的思想 本程序设计主要是应用了栈,利用栈的“先进后出”原理,建立了两个栈,分别为运算符栈pOStack和运算数栈pDStack。算法的基本思想(参考课本p53页)是: (1) 首先置操作数栈为pDStack空栈,表达式起始符为“=”,位运算符栈的栈底元素; (2) 依次读入表达式中的每个字符,若是操作数则进入pDStack栈,若是运算符则和pOStack栈的栈定运算符比较优先权后作相应操作,直到整个表达式求值完毕(即pOStack栈的栈定元素和当前读入的字符均为“=” )。 三、 算法的流程图 本程序的流程如下附图1所示: 附图1 程序流程图 四、 算法设计分析 首先创建了两个栈: typedef struct OPStack //定义运算符栈 { char opStack; int top; }OPStack, *pOPStack; typedef struct DATAStack //定义运算数栈 { double stack; int top; }DATAStack, *pDATAStack; 来分别存放运算符和运算数。在两个结构体中均有一个top数据域,当top=-1时,表示该站为空栈。 定义一个Evaluateexpression_r()函数来完成函数运算的主要功能:读入表达式,并计算结果。以下是对该函数的分析: 当一次运算开始时,分别调用InitpOPStack(pOPStack &pOStack)函数和InitpDATAStack(pDATAStack &pDStack)函数分别对运算符栈和运算数栈进行初始化。调用PushOPStack(pOStack, '=')函数来完成运算符栈栈低元素的设置。 通过PushOPStack(pOPStack &pOStack, char ch)函数、 PopOPStack(pOPStack &pOStack, char &ch)函数、 PushDATAStack(pDATAStack &pDStack, double d)函数和PopDATAStack(pDATAStack &pDStack, double &d)函数来分别完成运算符和运输数的进出栈操作。getToppOPStack(pOPStack &pOStack)函数和getToppDATAStack(pDATAStack &pDStack) 函数主要是进行得到栈定元素的作用,特别是在对运算符栈优先级的比较中十分重要,其中还会调用IsOP(char &ch) 函数来区分读入的是运算符还是运算数。 ChangeChar(char &c)函数当每次读入一个字符是都会调用一次,主要的作用就是完成不用区分A、S的大小的功能。 Precede(char op1, char op2)函数主要是通过一个二维字符串数组来存放9种运算符的优先级比较的结果,每当读到一个运算符后就进行与运算符栈顶元素比较,通过返回的“、=”结果来进行下一步的操作:''表示运算符和运算数各退栈一次并调用Operate(double a, char theta, double b)函数(主要是对出栈的运算符和运算数进行计算),最后将运算结果压入运算数栈pDStack。 当操作结束时运算数栈的栈顶元素就是计算结果,分别调用ClearpOPStack(pOStack)函数清空运算符栈、ClearpDATAStack(pDStack)函数清空运算数栈以待下一次继续进行相关操作。 print_user()函数和exit_E()函数开始和结束时个调用一次,分别完成欢迎界面和退出界面的布置。main()是本程序的主函数,主要通过while语句和switch语句来完成本程序的运行,当输入Y(y)时调用Evaluateexpression_r()函数完成计算,当输入N(n)时,调用exit_E()函数退出本程序的运行。 本程序还考虑到各种异常的处理,如运算时除数为0、被开方数为0等情况的出现,最终的处理是直接退出程序的运行。 五、 运行结果分析 1. 程序开始界面,如附图2: 附图2 开始界面 2.如下附图3,附图4分别是选择进入和退出程序界面: 附图3(在以下界面输入计算式即可运行出计算结果如附图5) 附图4 退出界面 附图5 运行界面 2. 对异常的处理 a) 对异常1除数为0,如输入“1+2/0=”程序将直接退出,如附图6: 附图6 异常1除数为0 b) 对异常2被开方数为负数,如输入“3+S(-9)=”程序将直接退出,如附图7: 附图7 异常2被开方数为负数 3.以下是对各种简单运算的运行结果,如附图8: 附图8 简单运算 3. 综合运算:如式子“1/2+A(7-8)-S(9*8)=”运行结果如附图9 附图9 综合运算 六、 收获及体会 本程序以C语言的栈的相关知识为基础,通过控制两个栈(运算数栈和运算符栈)的进出的栈操作,来实现对包含加、减、乘、除、括号运算符及SQRT和ABS函数的任意整型表达式的求解运算。 从程序的编写来看,感觉这次自己真的学到了好多,特别是对程序的开发流程。从最初的选定程序,到最终的程序运行成功,让我感到如果是仅仅掌握课本上的知识是远远不能够很好的应用到实际的编程中去的。在这个过程中还需要我们更多的去考虑到实际条件的种种限制和约束。 我在写本程序的过程中也遇到了很多的问题,当然本程序的核心问题就是对两个栈的压出栈操作,需要做优先级判断,并要考虑什么时候进栈,什么时候出栈等操作。我采用了课本上第52-54页讲的通过一个二维字符串数组来控制比较“+-*、()AS=”共9个运算符的优先级控制。对异常,如除数为0、被开方数小于0等异常也进行了精心的处理。对操作过程中要用到的Y、N、A、S等字符也进行了改进,最终本程序可以不区分大小写就完成相关操作。 总之,经过本次专业课程设计,让我掌握了开发应用软件的基本流程,运用所学编程技能的基本技巧,也让我初步了解了软件设计的基本方法,提高进行工程设计的基本技能及分析、解决实际问题的能力,为以后毕业设计和工程实践等打下良好的基础。相信通过这次的课程设计,我对所学的《数据结构(C语言版)》和各种编程语言都有了一个全新的认识。我也会积极吸取本次课程设计的经验,继续研究数据结构和所学的各种编程语言。 七、 源代码 # include # include # include # include # define MAX_OPERATOR_NUM 100 //运算符栈数组长度 # define MAX_DATA_NUM 100 //运算数栈数组长度 typedef struct OPStack //定义运算符栈 { char opStack; int top; }OPStack, *pOPStack; typedef struct DATAStack //定义运算数栈 { double stack; int top; }DATAStack, *pDATAStack; void InitpOPStack(pOPStack &pOStack) //初始化运算符栈 { if( !(pOStack = (pOPStack)malloc(sizeof(OPStack)))) //为运算符栈分配空间 { printf("分配内存空间失败! "); exit(-1); } pOStack->top = -1; } void InitpDATAStack(pDATAStack &pDStack) //初始化运算数栈 { if( !(pDStack = (pDATAStack)malloc(sizeof(DATAStack)))) //为运算数栈分配空间 { printf("分配内存空间失败! "); exit(-1); } pDStack->top = -1; } void PushOPStack(pOPStack &pOStack, char ch) //运算符进栈 { pOStack->opStack = ch; } void PopOPStack(pOPStack &pOStack, char &ch) //运算符出栈 { ch = pOStack->opStack; pOStack->top--; } void PushDATAStack(pDATAStack &pDStack, double d) //运算数进栈 { ++(pDStack->top); pDStack->stack = d; } void PopDATAStack(pDATAStack &pDStack, double &d) //运算数出栈 { d = pDStack->stack; pDStack->top--; } void ClearpOPStack(pOPStack &pOStack) //清空运算符栈 { pOStack->top = -1; } void ClearpDATAStack(pDATAStack &pDStack) //清空运算数栈 { pDStack->top = -1; } char GetToppOPStack(pOPStack &pOStack) //获取运算符栈顶元素 { return pOStack->opStack; } double GetToppDATAStack(pDATAStack &pDStack) //获取运算数栈顶元素 { return pDStack->stack; } bool IsOP(char &ch) //区分 运算符 和 运算数 的函数,是运算符时返回true,否则返回false { //判断是否为符号 if ( (ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '=') || (ch == 'A') || (ch == 'S') || (ch == 'a') || (ch == 's') || (ch == '(') || (ch == ')') ) return true; else return false; } char Precede(char op1, char op2) //参考《数据结构》(C语言版)第53页 表达式求值 表 { char tab; //定义字符串的二维数组来存放运算符优先级的关系 strcpy( tab, ">>" ); strcpy( tab, ">>" ); strcpy( tab, ">>>>" ); strcpy( tab, ">>>>" ); strcpy( tab, " strcpy( tab, ">>>>E>>>>" ); strcpy( tab, ">>>>>>>" ); strcpy( tab, ">>>>>>>" ); strcpy( tab, " printf(" | ***欢迎您的下次使用!谢谢!!!*** | "); //退出使用 printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| "); } double Operate(double a, char theta, double b) //对出栈的运算符和运算数进行计算 { double s; switch(theta) { case '+': s = a + b; break; case '-': s = a - b; break; case '*': s = a * b; break; case '/': if ( b != 0 ) //判断除数是否为0,若为0,退出程序 { s = a/b; break; } else { printf(" #### 除数为0,非法运算。程序终止! #### "); exit_E(); //打印结束菜单 exit(-1); } case 'A': s = fabs(b); //调用FABS()函数 break; case 'S': if( b >= 0) //判断被开方数是否为0,若为0,退出程序 { s = sqrt(b); //调用SQRT()函数 break; } else { printf(" #### 求负数的平方根是非法运算。程序终止! #### "); exit_E(); //打印结束菜单 exit(-1); } } return s; } char ChangeChar(char &c) //通过ChangeChar函数来把a、s的小写字母改为大写的 { if( c == 'a' ) c = 'A'; else if( c == 's' ) c = 'S'; return c; } //参考《数据结构》(C语言版)第53页 表达式求值算法 Evaluateexpression_r()函数 void Evaluateexpression_r() //计算函数:读入表达式,并计算结果 { pOPStack pOStack; //声明运算符栈 pDATAStack pDStack; //声明运算数栈 double result; //存运算的结果 char x, theta, c; //c存放读取的字符,x、theta存放运算符栈的栈顶元素 int flag, data; //标识符,用来读入连续的数字 double s; double getd; //存放GetTop***的结果 double a, b, cc; //a,b存放数据栈出栈的栈顶元素, c存放运算结果 flag = 0; //初始化标识符,用来判断字符串中的连续数字 data = 0; // InitpOPStack(pOStack); //初始化运算符栈 InitpDATAStack(pDStack); //初始化运算数栈 PushOPStack(pOStack, '='); //在运算符栈底放入'=' printf(" &请输入表达式以'='结束:"); c = get); //读入字符 ChangeChar(c); //通过调用函数来实现把小写的a、s改为大写的A、S while( c != '=' || GetToppOPStack(pOStack) != '=') { if( !IsOP(c) ) //不是运算符进栈 { s = c - '0'; //把字符转化为数字 if ( flag == 1 ) { PopDATAStack(pDStack, getd); s = getd*10 + s; } PushDATAStack(pDStack, s); flag = 1; c = get); ChangeChar(c); } else { flag = 0; switch( Precede(GetToppOPStack(pOStack), c) ) //输入元素和运算符栈顶元素比较 { case ' PushOPStack(pOStack, c); c = get); ChangeChar(c); break; case '=': //托括号并接受下一个字符 PopOPStack(pOStack, x); c = get); ChangeChar(c); break; case '>': //退栈并将运算结果进栈 PopOPStack(pOStack, theta); PopDATAStack(pDStack, b); PopDATAStack(pDStack, a); cc = Operate(a, theta, b); PushDATAStack(pDStack, cc); break; }//switch }//else }//while result = GetToppDATAStack(pDStack); //运算结束时,运算数栈的栈底元素就是计算结果 ClearpOPStack(pOStack); //清空运算符栈 ClearpDATAStack(pDStack); //清空运算数栈 printf(" ->计算结果为:%.2f ", result); //输出运算结果 return ; } void print_user() //欢迎界面 { printf(" 欢迎使用C语言版模拟计算器 "); printf("************************************************************************ "); printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| "); printf(" | 模拟计算器使用说明 | "); printf(" | 作者:谢先斌 | "); printf(" | 本程序包括对'+'、'-'、'*'、'/'、'()'的运算 | "); printf(" | 本程序中ABS()算用A()替代、SQRT()运算用S()代替 | "); printf(" | 本程序中的一切字母均不区分大小写 | "); printf(" 正确的表达式如:1+A(7-8)+S(9*8)= "); printf(" | 输入'='表示表达式输入结束!! | "); printf(" | 欢迎使用!!!-->--> | "); printf(" |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| "); printf("************************************************************************ "); } int main() //主函数 { char in; bool b; //标识符,用来标识是否结束程序 b = true; //初始化,不结束 print_user(); //打印欢迎界面 printf(" *请确认使用计算器Y/N:"); while(1) { scanf("%c", &in); //确认是否继续操作 get); //吃掉会车,避免干扰 switch(in) { case 'Y': case 'y': { Evaluateexpression_r(); //进入计算函数:读入表达式,并计算结果 break; } case 'N': case 'n': { exit_E(); b = false; break; } //default: // printf(" **输入错误,请重新输入Y/N:"); // break; } if(b==false) //如果 b==false ,退出整个程序 break; printf(" *您确定要继续使用计算机Y/N:"); get); //用getchar吃掉回车,避免对后续输入中in的干扰 } return 0; }