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

《北京理工大学数据结构及算法设计实验二.doc》由会员分享，可在线阅读，更多相关《北京理工大学数据结构及算法设计实验二.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. .?数据构造与算法设计?实验报告实验二学院：自动化学院班级： 06111001 学号： 1120210001： 宝竞宇 一、 实验目的掌握栈的建立，输入，删除，出栈等根本操作。应用栈解决实际问题。二、实验内容实现简单计算器的功能,请按照四那么运算加、减、乘、除、幂和括号的优先关系和惯例，编写计算器程序。要求支持运算符：+、-、*、/、%、和=： 从键盘输入一个完整的表达式，以回车作为表达式输入完毕的标志； 输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进展计算。例如，输入：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 (long int)

4、 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。栈的进出和链表的区别还是很大的，在这次实验中我学会掌握了，栈的创立，和存入，出栈等操作，掌握了有关知识。同时比拟了，链表与栈之间的区别和联系。五、用户使用说明 运行程序，程序对话框会显示“Expression=然后输入表

6、达式，按回车得出结果，然后按任意键退出程序。六、程序运行结果七、程序清单#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 return (0);defaul

7、t: 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 main( )int j, k,

8、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 /* 如果是符号与栈顶的符号比拟并运算 */ i

9、f ( 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); /* 计算 */ pushd(k); /* 计算结果入栈 */ break;case W: printf(Error No. 4:%sn, p); return 1;printf(%dn,prd.datprd.top-1);/* 输出结果 */system(PAUSE);return 0;. .word.