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

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 

4、9;%': return (long int) fmod(x,y);case '': if (y>=0 ) return (long int) pow(x,y); else return (0);default: printf("Error No. 3n"); return 0; 主程序：在主程序内，以字符串的形式输入表达式，然后分别调用函数存入各相应栈，然后用数组判断，比较运算符的优先顺序。依次输入，当要输入的算符优先级比已经在栈顶的优先级低，则取出运算。while ( *p!='#' | prt.datprt.top-1!=

5、'#' )以#号作为结束的标志。switch ( refusal(prt.datprt.top-1, *p ) )用来比较优先级主函数流程图： 开 始 循环模块输入表达式各项 存入模块存入 判断模块是否计算 输出栈顶值结 束四、程序调试分析 在程序调试过程中，对实验的步骤并不是非常熟悉，导致实验的过程中对基本的计算器栈的应用不好。其原理是依次读入表达式的每一个字符，把数字和运算符分别存在两个不同的栈中，当要读入的运算符比已经在栈中的运算符优先级低时，则取出运算，然后把结果存入数栈。优先级的关系一开始不知道怎么建立，后来想到了二维数组，然后在计算操作函数的编写上，出现了问题，最后

6、想到了应用switch。栈的进出和链表的区别还是很大的，在这次实验中我学会掌握了，栈的创立，和存入，出栈等操作，掌握了有关知识。同时比较了，链表与栈之间的区别和联系。五、用户使用说明 运行程序，程序对话框会显示“Expression=”然后输入表达式，按回车得出结果，然后按任意键退出程序。六、程序运行结果 七、程序清单#include <stdio.h>#include <math.h>#include <string.h>#define W 0x00char chinput200, *p; /* 运算式存储字符串 */* 运算式当前读取位置 */struc

7、t FUHAO/* 建符号栈 */char dat200;int top;prt;struct SHU/* 建数字栈 */long int dat200;int top;prd;char PRI99='>','>','<','<','<','<','<','>','>','>','>','<','<','

8、<','<','<','>','>','>','>','>','>','<','<','<','>','>','>','>','>','>','<','<','

9、<','>','>','>','>','>','>','>','<','<','>','>','>','>','>','>','>','<','<','>','

10、>','<','<','<','<','<','<','<','=', W ,'>','>','>','>','>','>',W, '>','>' ,'<','<','<',

11、'<','<','<','<', W ,'=' ;/*优先级列表*/void pushd(long int a)/* 数字入栈 */prd.datprd.top+=a;void pusht(char a)/* 符号入栈 */prt.datprt.top+=a;long int popd( )/* 数字出栈 */return prd.dat-prd.top;char popt( )/* 符号出栈 */return prt.dat-prt.top;long int numble ( )/* 数字

12、整理 */long int b=0;dob = b*10 + *p -'0'p+;while ( *p>='0' && *p<='9' ) ;return b;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 (

13、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) pow(x,y); else return (0);default: printf("Error No. 3n"); return 0;int signswitch ( char a )/* 符号转换 */char signs= '+', '

14、;-', '*', '/', '%', '', '(', ')', '#', '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);

15、int main( )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!='#' )i

16、f ( *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 '<': pusht ( *p+ ); /* 当前运算符优先级高则运算符入栈 */break; /*处理下一个字符*/case '=': popt( ); /* 脱括号 */ p+; break;case '>': b=popt( ); /* 当前运算符优先级低