数据结构实验报告（逆波兰表达式求值）.doc

实验三逆波兰表达式求值一. 问题描述:读入一个后缀表达式,利用堆栈来计算该表达式的值,同时要效验后缀表达式是否正确。二. 需求分析:。,界面自动输出后缀表达式的值,否则输出表达式错误的信息,将结果置为0。。*1-#,所以首先选择一个字符数组存储该串字符,直接使用编译器自带的字符数组。由于计算后缀表达式时,具有先进后出的规律,故而考虑使用堆栈其ADTStack{操作对象:字符,整数,浮点数基本操作:Stack(intsize);//构造大小为size的堆栈~Stack();//撤销堆栈BoolIsEmpty();//是否为空,是返回true,否则返回falseBoolIsFull();//是否为满,是返回true,否则返回falseVoidPush(TX);//将x压入堆栈VoidPop(T&x);//弹出栈顶元素,并用x保存对于计算后缀表达式的值的算法:首先假设此表达式正确从字符串第一个开始扫描,遇到运算数就先转化成为数值然后压入堆栈中,如遇到运算符则弹出堆栈上面的两个元素,并进行对应的运算,将得到的值压入栈中,直到最后一个字符为止。对于表达式错误:返回0小数缺少整数部分:,而是直接检测到小数点运算符过多:23*-弹出一个数后堆栈便空运算数过多:37*:/*Name:逆波兰表达式求值Copyright:WCH466-Experiment-3Author:wch466Date:02/04/1222:59Description:读入一个后缀表达式,利用堆栈来计算该表达式的值,同时要效验后缀表达式是否正确。*///Copyright:WCH466-Experiment-3#include<iostream>#include<string>#include<cmath>usingnamespacestd;classAstack{private:intsize;inttop;float*list;boolg;public:Astack(intse=4){size=se;top=0;list=newfloat[size];g=1;}~Astack(){delete[]list;}voidpush(constfloat&it)//入{if(top==size)return;list[top++]=it;}floatpop(){if(top==0){g=0;return0;}//g=0代表表达式错误(运算符多了)returnlist[--top];}booljudge(){returng;}intlength()const{/*cout<<"lengthoflistis"<<top<<endl;*/returntop;}};//Copyright:WCH466-Experiment-3voidPretreatstr(constchar*a)//预处理字符{inti=0,g=1,s=1,size=strlen(a),k=0;floatnum=0,in=0,x,y,de=0;//standforinteger,decimalAstackt(size);fo