数据结构实验-栈和队列.doc

《数据结构实验-栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验3：栈和队列一、实验目的深入了解栈和队列的特性，学会在实际问题下灵活运用它们。二、问题描述表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。三、实验要求1、算法优先级别如下：'+','-','*','/','(',')','#''+''>','>','<','<','<','>','>','-''>','>','<','<','<','>','>','*''>','>','>','>','<','>','>','/''>','>','>','>','<','>','>','

2、(''<','<','<','<','<','=','',')''>','>','>','>','','>','>','#''<','<','<','<','<','','='2、以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。 四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境 五、实验步骤1、根据给出的算符优先级，设置运算符栈和运算数栈；2、在读入表达式的同时，完成运算符和运算数的识别处理，并将运算数的字符序列

3、形式转换成整数形式，并进行相应的运算；3、调试程序，检查输出结果；4、实验小结。 六、测试数据1.输入数据：1+（20+4）/（4-1）正确结果：92.输入数据：2*9-6-（20+4）/（4-1）正确结果：4七、实验报告要求实验报告应包括以下几个部分：1、问题描述；2、算法的设计描述；3、测试结果的分析与讨论。4、设计与实现过程中的体会，进一步的改进设想。实现算法的程序清单，应有足够的注释。实验代码如下：#include#include#includeusingnamespacestd;#de

4、fineMAX1000structsave1{floatn[MAX];inttop;}stack1;structsave2{charn[MAX];inttop;}stack2;//stack1存储数字，stack2存储运算符号.boolstackempty(save1s)//判断是否为空{if(s.top==-1)return1;elsereturn0;}boolstackempty2(save2s)//判断是否为空{if(s.top==-1)return1;elsereturn0;}voidpush(save1&s,floate)//将e入栈{

5、if(s.top==MAX-1){cout<<"栈已满"<

6、s,char&e)//将栈顶元素出栈，存到e中{if(s.top==-1){cout<<"栈为空"<

7、

8、e=='+')return2;if(e=='*'

9、

10、e=='/')return4;if(e=='^')return5;if(e=='(')return0;if(e==')')return7;return-1;}intout(chare)//e在栈外的优先级别{if(e=='-'

11、

12、e=='+')return1;

13、if(e=='*'

14、

15、e=='/')return3;if(e=='^')return6;if(e=='(')return7;if(e==')')return0;return-1;}voidcount(floata,charope,floatb)//进行计算并将计算结果入栈{floatsum;if(ope=='+')sum=a+b;if(ope=='-')sum=a-b;if(ope=='*')sum=a*b;if(ope=='/')sum=a/b;if(ope=='^')sum=pow(a,b);push(stack1,sum);}intmain

16、(){inti=0,len,j,nofpoint,g=0;//len表示输入式子的长度。g表示读入的字符是否是字母变量、数字以及运算符。