《数据结构实验报告（逆波兰表达式求值）》由会员分享，可在线阅读，更多相关《数据结构实验报告（逆波兰表达式求值）（6页珍藏版）》请在金锄头文库上搜索。
1、实验三 逆波兰表达式求值一问题描述：读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。二需求分析： 1. 本程序需要基于堆栈的基本操作来实现逆波兰表达式的求值。2.若表达式正确，界面自动输出后缀表达式的值，否则输出表达式错误的信息,将结果置为0。3.操作数和操作符均由键盘键入。4.输入输入一个后缀表达式2 3 * 1 - #输出结果 5三概要设计由于操作的事一串字符，所以首先选择一个字符数组存储该串字符，直接使用编译器自带的字符数组。由于计算后缀表达式时，具有先进后出的规律，故而考虑使用堆栈其ADT Stack 操作对象：字符，整数，浮点数 基本操作： Stack(
2、int size);/构造大小为size的堆栈 Stack()；/撤销堆栈 Bool IsEmpty();/是否为空，是返回true，否则返回false Bool IsFull();/是否为满，是返回true，否则返回false Void Push(T X);/将x压入堆栈 Void Pop(T &x);/弹出栈顶元素，并用x保存对于计算后缀表达式的值的算法：首先假设此表达式正确从字符串第一个开始扫描，遇到运算数就先转化成为数值然后压入堆栈中，如遇到运算符则弹出堆栈上面的两个元素，并进行对应的运算，将得到的值压入栈中，直到最后一个字符为止。对于表达式错误：返回01、 小数缺少整数部分：如 .9
3、99未检测到数，而是直接检测到小数点2、 运算符过多：2 3*-弹出一个数后堆栈便空3、 运算数过多：3 7*0最后堆栈不空四源程序：/* Name: 逆波兰表达式求值 Copyright: WCH466-Experiment-3 Author: wch466 Date: 02/04/12 22:59 Description: 读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。*/ Copyright: WCH466-Experiment-3 #include#include#includeusing namespace std;class Astackprivat
4、e: int size; int top; float *list; bool g; public: Astack(int se=4) size=se;top=0;list=new float size;g=1; Astack() delete list; void push(const float& it) /入 if(top=size) return; listtop+=it; float pop() if(top=0) g=0;return 0; /g=0代表表达式错误（运算符多了） return list-top; bool judge()return g; int length()
5、const /*coutlength of list is topendl; */return top; ;/ Copyright: WCH466-Experiment-3 void Pretreatstr(const char *a) /预处理字符 int i=0,g=1,s=1,size=strlen(a),k=0; float num=0,in=0,x,y,de=0; /stand for integer,decimal Astack t(size); for(i=0;i47) s=1; /有数 if(g) in=in*10+ai-48; /提取整数部分 else /小数处理 de=(a
6、i-48)*pow(0.1,k+)+de; if(ai=46) if(g=0) cout小数点多余！;return ; g=0;k=1; /有小数 if(ai=42|ai=43|ai=45|ai=47|ai= ) if(s) / s=0 代表没数 t.push(in+de);in=0;de=0;g=1;s=0;/*cout插入：in+deendl;*/ if(ai!= ) y=t.pop(); x=t.pop(); if(ai=+) t.push(x+y); if(ai=-) t.push(x-y); if(ai=*) t.push(x*y); if(ai=/) if(y=0) cout分母为
7、零！endl; return; t.push(x/y); if(t.length()=1&t.judge()&ai-148) /最后一个字符不能为num cout表达式的答案是：int(t.pop()*100)/100.0endl; else cout表达式错误endl; ;/ Copyright: WCH466-Experiment-3 int main() char s100; while(gets(s) Pretreatstr(s); system(pause); return 0;五测试结果： 六实验心得：1.通过本次试验，我发现自己分析问题不是很全面，忽略掉一些细节。以后分析问题时要仔细考虑，认真分析，避免在细节上犯错误。2.通过这次实验，我发现自己编程能力相当欠缺，尤其是用链表实现。自己以后要勤加练习。
