逆波兰表达式求值(实验报告及c++源码)

《逆波兰表达式求值(实验报告及c++源码)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程实验指导书逆波兰表达式求值一、需求分析1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。2、用堆栈来实现3、测试数据输入：23*1–#输出：23*1--=5二、概要设计抽象数据类型需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。ADTStack数据成员：intsize;inttop;//分别用于存储栈大小、栈顶位置float*listArray;//存储浮点型数字的数组成员函数：boolpush(floatit);boolpop(float&it);boolisEmpty()

2、;//判断栈为空boolisOne();//判断栈是否只有一个元素算法的基本思想1.逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48将数据由字符类型转换为浮点型数据；2.如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分；3.遇到空格前是数据的，将x押入栈；4.如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；程序的流程输入字符串，程序对字符串依次扫描。扫描一位，

3、处理一位。扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。三、详细设计物理数据类型用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈：classStack{private:intsize;inttop;float*listArray;public:Stack(intsz=20);~Stack();－5－数据结构课程实验指导书boolpush(floatit);//入栈boolpop(float&it);//出栈boolisEmpty();//判断栈是否为空boolis

4、One();//判断栈里是否只有且仅有一个元素};成员函数的函数体－5－数据结构课程实验指导书Stack::Stack(intsz)//栈构造函数{size=sz;top=0;listArray=newfloat[size];}boolStack::push(floatit){if(top==size)returnfalse;listArray[top++]=it;returntrue;}boolStack::pop(float&it){if(top==0)returnfalse;it=listArray[--top];retu

5、rntrue;}boolStack::isEmpty()//判断站是否为空{if(top==0)returntrue;returnfalse;}boolStack::isOne(){if(top==1)returntrue;returnfalse;}Stack::~Stack(){deletelistArray;}－5－数据结构课程实验指导书算法的具体步骤用switch语句实现1.逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48将数据由字符类型转换为浮点型数据；2.如果字符是‘.’

6、，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分；3.遇到空格前是数据的，将x押入栈；4.如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；算法的时空分析因为入栈、出栈的时间复杂度均为Θ(1)，所以时间的复杂度主要取决于字符串的长度，空间也同样取决于字符串长度。时间复杂度为Θ(n)。输入和输出的格式输入：23*1–#输出：23*1--=5五、测试结果－5－数据结构课程实验指导书六、用户使用说明（可选）1.运行程序后，直接输入

7、后缀表达式；2.用户输入的表达式必须符合后缀表达式的要求，并以‘#’号结束。七、附录（可选）－5－数据结构课程实验指导书#include#includeusingnamespacestd;classStack{private:intsize;inttop;float*listArray;public:Stack(intsz=20);~Stack();boolpush(floatit);//入栈boolpop(float&it);//出栈boolisEmpty();//判断栈是否为空boolis

8、One();//判断栈里是否一个元素};Stack::Stack(intsz)//栈构造函数{size=sz;top=0;listArray=newfloat[size];}boolStack::push(floatit){if(top==size)return