北京理工大学数据结构与算法设计实验二.doc

1、数据结构与算法设计实验报告实验二学院：自动化学院班级： 06111001 学号： 1120100001姓名： 宝竞宇 一、 实验目的 掌握栈的建立，输入，删除，出栈等基本操作。应用栈解决实际问题。二、实验内容 实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（）和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、（）和=： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志； 输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。例如，输入：4+2*5=输出：14 输入：(4+2)*(2-10)=输出：-48三、程序设计 1、

2、概要设计 抽象数据类型定义：两个栈结构，分别用来储存数据和计算符号 宏定义：函数“成功”，“失败的返回值” 在主程序程序中先依次输入各表达式，存入相应各栈，然后 ，调用“判断函数”来判断计算符的优先次序，然后再利用计算函数来计算，表达式值。其中还有，取栈顶元素函数，存入栈函数。 2、详细设计数据类型实现：struct tchar dat200; int top;prt;入栈函数：存入数组，栈顶指针上移void pushd(long int a)prd.datprd.top+=a;出栈：取出对应值，栈顶指针下移 long int popd( )return prd.dat-prd.top;比较优

3、先级：建立数组，比较返回大于小于号。计算函数：以字符型输入，运算符号，用switch来分支计算判断，返回计算数值 long int operation ( long int x, long int y, char a) switch(a)case +: return x+y;case -: return x-y;case *: return x*y;case /: if ( y ) return x/y; else printf(Divide 0.n); return 0; case %: return (long int) fmod(x,y);case : if (y=0 ) return

4、(long int) pow(x,y); else return (0);default: printf(Error No. 3n); return 0; 主程序：在主程序内，以字符串的形式输入表达式，然后分别调用函数存入各相应栈，然后用数组判断，比较运算符的优先顺序。依次输入，当要输入的算符优先级比已经在栈顶的优先级低，则取出运算。while ( *p!=# | prt.datprt.top-1!=# )以#号作为结束的标志。switch ( refusal(prt.datprt.top-1, *p ) )用来比较优先级主函数流程图： 开 始 循环模块输入表达式各项 存入模块存入 判断模块是

5、否计算 输出栈顶值结 束四、程序调试分析 在程序调试过程中，对实验的步骤并不是非常熟悉，导致实验的过程中对基本的计算器栈的应用不好。其原理是依次读入表达式的每一个字符，把数字和运算符分别存在两个不同的栈中，当要读入的运算符比已经在栈中的运算符优先级低时，则取出运算，然后把结果存入数栈。优先级的关系一开始不知道怎么建立，后来想到了二维数组，然后在计算操作函数的编写上，出现了问题，最后想到了应用switch。栈的进出和链表的区别还是很大的，在这次实验中我学会掌握了，栈的创立，和存入，出栈等操作，掌握了有关知识。同时比较了，链表与栈之间的区别和联系。五、用户使用说明 运行程序，程序对话框会显示“Ex

6、pression=”然后输入表达式，按回车得出结果，然后按任意键退出程序。六、程序运行结果 七、程序清单#include #include #include #define W 0x00char chinput200, *p; /* 运算式存储字符串 */* 运算式当前读取位置 */struct FUHAO/* 建符号栈 */char dat200;int top;prt;struct SHU/* 建数字栈 */long int dat200;int top;prd;char PRI99=,W, , ,=0 & *p=0 ) return (long int) pow(x,y); else r

7、eturn (0);default: printf(Error No. 3n); return 0;int signswitch ( char a )/* 符号转换 */char signs= +, -, *, /, %, , (, ), #, 0 ;int k;k = 0;while ( signsk!=0 & signsk != a )k+;if ( signsk = a ) return k;else return -1;char refusal ( char a,char b ) /* 判定优先级 */return PRIsignswitch(a)signswitch(b);int m

8、ain( )int j, k, l, flag=0; /* flag=0前一个符号不是) */char b;prt.dat0=#;prt.top=1;prd.top=0;printf (Enter Expression=);scanf(%s, chinput); /* 接收运算式 */strcat( chinput, # ); /* 在运算式结尾加#号 */p = chinput;while ( *p!=# | prt.datprt.top-1!=# )if ( *p=0 & *p=9) j = numble();/* 如果是数字进行整理并入栈 */pushd(j);else /* 如果是符号与栈顶的符号比较并运算 */ if ( flag=1 & *p=( ) printf(Error No.1:%sn, p); return 0;else if ( *p=) flag=1; else flag=0;switch ( refusal(prt.datprt.top-1, *p ) )case : b=popt( ); /* 当前运算符优先级低则进行栈顶计算 */ k=popd(); /* 第二操作数出栈 */ l=popd(); /* 第一操作数出栈 */ k=operation(l,k,b); /* 计算