实验三栈和队列.doc

实验3：栈和队列一、实验目的深入了解栈和队列的特性，学会在实际问题下灵活运用它们。二、问题描述表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。三、实验要求1、算法优先级别如下：+, -, *, /, (, ), #+ , , , , , ,- , , , , , ,* , , , , , ,/ , , , , , ,( , , , , , , , , , , ,# , , , , , , =2、以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境五、实验步骤1、程序代码编写：4#include #include using namespace std; int Operate(int x,char op,int y) switch(op) case+: return x+y; case-: return x-y; case*: return x*y; case/: return x/y; char Precede(char op1,char op2) /判断符号的优先级 if(op1=+|op1=-)&(op2=+|op2=-|op2=)|op2=#)|(op1=*|op1=/)&(op2=+|op2=-|op2=*|op2=/|op2=)|op2=#) return ; if(op1=(&op2=)|(op1=#&op2=#) return =; else return ; void Tonumber(char &c,stack &OPND) /转化为数字 int number=0; if(c-0)=0&(c-0)=0&(c-0)c; OPND.push(number); int main() stack OPTR; stack OPND;/设OPTR和OPND分别为运算符栈和运算数栈 OPTR.push(#); char c,op1,op2,op; int x,y,temp=1; coutc; while(c!=#|OPTR.top()!=#) Tonumber(c,OPND); if(c!=+&c!=-&c!=*&c!=/&c!=(&c!=)&c!=#) OPND.push(c); cinc; else op1=OPTR.top(); op2=c; switch(Precede(op1,op2) case c; break; case =: OPTR.pop(); cinc; break; case : op=OPTR.top(); /退栈并将运算结果入栈 OPTR.pop(); x=OPND.top(); OPND.pop(); y=OPND.top(); OPND.pop(); OPND.push(Operate(y,op,x); int a=OPND.top(); break; cout计算结果是:OPND.top()endl; return 0;2、调试程序，输入测试数据，输出结果：六、测试数据1. 输入数据：1+（20+4）/（4-1） 正确结果：92. 输入数据：2*9-6-（20+4）/（4-1） 正确结果：4七、实验报告要求实验报告应包括以下几个部分：1、问题描述；2、算法的设计描述；3、测试结果的分析与讨论。4、设计与实现过程中的体会，进一步的改进设想。实现算法的程序清单，应有足够的注释。八、思考题1、 试着扩充运算符集，如增加乘方、单目加等。2、 如何增强计数器的功能和仿真界面。3、 如何实现前缀算术表达式、后缀表达式的求解？答：前缀就是把运算符放在