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

数据结构课程实验指导书逆波兰表达式求值一、需求分析1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。2、用堆栈来实现3、测试数据输入：2 3 * 1 #输出：2 3 * 1 - =5二、概要设计抽象数据类型需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。ADT Stack数据成员：int size; int top; /分别用于存储栈大小、栈顶位置float *listArray;/存储浮点型数字的数组成员函数：bool push(float it);bool pop(float& it);bool isEmpty(); /判断栈为空bool isOne();/判断栈是否只有一个元素算法的基本思想1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+stri-48将数据由字符类型转换为浮点型数据；2. 如果字符是.，则将.转化为小数点，并将.后的数据转化为小数部分；3. 遇到空格前是数据的，将x押入栈；4. 如果该字符是+，-，*或/，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；程序的流程输入字符串，程序对字符串依次扫描。扫描一位，处理一位。扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。三、详细设计物理数据类型用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈：class Stackprivate:int size;int top;float *listArray;public:Stack(int sz=20);Stack();bool push(float it);/入栈bool pop(float& it);/出栈bool isEmpty();/判断栈是否为空bool isOne(); /判断栈里是否只有且仅有一个元素;成员函数的函数体 5 Stack:Stack(int sz) /栈构造函数size=sz;top=0;listArray=new floatsize;bool Stack:push(float it)if(top=size)return false;listArraytop+=it;return true;bool Stack:pop(float& it)if(top=0)return false;it=listArray-top;return true;bool Stack:isEmpty() /判断站是否为空if(top=0)return true;return false;bool Stack:isOne()if(top=1)return true;return false;Stack:Stack()delete listArray;算法的具体步骤用switch语句实现1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+stri-48将数据由字符类型转换为浮点型数据；2. 如果字符是.，则将.转化为小数点，并将.后的数据转化为小数部分；3. 遇到空格前是数据的，将x押入栈；4. 如果该字符是+，-，*或/，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；算法的时空分析因为入栈、出栈的时间复杂度均为(1)，所以时间的复杂度主要取决于字符串的长度，空间也同样取决于字符串长度。时间复杂度为(n)。输入和输出的格式输入：2 3 * 1 #输出：2 3 * 1 - =5五、测试结果六、用户使用说明（可选）1. 运行程序后，直接输入后缀表达式；2. 用户输入的表达式必须符合后缀表达式的要求，并以#号结束。七、附录（可选）#include #include using namespace std;class Stackprivate:int size;int top;float *listArray;public:Stack(int sz=20);Stack();bool push(float it);/入栈bool pop(float& it);/出栈bool isEmpty();/判断栈是否为空bool isOne();/判断栈里是否一个元素;Stack:Stack(int sz) /栈构造函数size=sz;top=0;listArray=new floatsize;bool Stack:push(float it)if(top=size)return false;listArraytop+=it;return true;bool Stack:pop(float& it)if(top=0)return false;it=listArray-top;return true;bool Stack:isEmpty() /判断站是否为空if(top=0)return true;return false;bool Stack:isOne()if(top=1)return true;return false;Stack:Stack()delete listArray;/此函数传进输入的字符串，并对字符串进/行扫描并进行相应处理，得到结果(函数声/明)void compute(char* str); int main()char str20;cin.getline(str,20,#);compute(str);return 0;/此函数传进输入的字符串，并对字符串进/行扫描并进行相应处理，得到结果(函数体)void compute(char* str)Stack aStack;float x=0,y=0,s1,s2,temp;int i;i=0;while(stri)switch(stri)case +: /加法运算if(aStack.isOne()|aStack.isEmpty() cout 表达式不符合要求;return;aStack.pop(s1);aStack.pop(s2);x=s2+s1;aStack.push(x);x=0;i+;break;case -: /减法运算if(aStack.isOne()|aStack.isEmpty()cout 表达式不符合要求;return;aStack.pop(s1); aStack.pop(s2);x=s2-s1; aStack.push(x);x=0; i+;break;case *: /乘法运算if(aStack.isOne()|aStack.isEmpty()cout 表达式不符合要求;return;aStack.pop(s1); aStack.pop(s2);x=s2*s1;aStack.push(x);x=0;i+;break;case /: /除法运算if(aStack.isOne()|aStack.isEmpty()cout 表达式不符合要求;return;aStack.pop(s1);a