HUNAN UNIVERSITY
课程实习
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
题 目 逆波兰表达式求值
学生姓名 朱 佳
学生学号 201308010228
专业班级 计算机科学与技术1302班
指导老师 吴 帆
完成日期 2015年4月26日
一、 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1、 问题背景
表达式求值是程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
语言编译中的一个最基本的问题．因为任何程序设计语言都必须具有表达式求值的功能，同时表达式的计算应用也相当广泛，比如电力调度系统中的计算遥测、车站票务系统中的票价类型计算公式等。
通常，我们所说的表达式是由运算符、操作数、界限符所组成。而算术表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。
1、中缀表达式——将运算符放在两操作数的中间。在运算中存在运算符的优先权与结合性的问题。例如运算：a*b+(c-d/e)*f 时，编译器即自左向右逐一检查，当检查到第一个运算符“*”时还无法知道是否执行；待检查到第二个运算符“ + ”时，因为知道“*”的优先级别高于“ + ”时，才知道执行“a*b”；当继续检查到“ ( ”时，可知道先执行括号以内部分等。
2、前缀表达式——将运算符放在两操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家—Jan Lukasiewicz，这种表示法也称波兰表示法。
3、后缀表达式——将运算符放在两操作数的后面。后缀表达式也称逆波兰表达式，因其使表达式求值变得轻松，所以被普遍使用。
前缀和后缀表示法有三项公共特征：
（1） 操作数的顺序与等价的中缀表达式中操作数的顺序一致
（2） 不需要括号
（3） 操作符的优先级不相关
2、 问题描述
读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。
3、 基本要求
（1）从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。
（2）用堆栈来实现
4、 输入输出格式
输入：在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开，以“#”表示结束。
输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字，如果不正确，请在字符界面上输出表达式错误提示。
5、 测试数据
输入 2 3 * 1 –#
输出 5
6、 实现提示
无
7、 选作内容
（1） 在输入和输出方式上发生改变：
输入：将后缀表达式存于文本文件中，其中后缀表达式中两相邻操作数之间利用空格隔开，程序从该文本文件中读出表达式。
输出：如果该后缀表达式正确，则计算结果，计算结果保留小数点后面两位有效数字，同时将结果输出到该文件中原表达式的后面，结果与表达式之间用“=”后相连；如果不正确，请在输出表达式错误提示到该文件原表达式的后面，它们之间用“---”相连。
（2）表达式中操作数为一实数，该实数精确到小数点后面两位有效数字。
二、 概要设计
（一）基本要求
1. 基本思想
定义一个类，作为要存放各种数据的栈。栈中定义多个成员函数，以完成初始化、出栈、压栈等操作，私有成员定义两个指针，一个指向栈的顶部，一个指向栈的底部，另有一个int型数据保存其大小。程序需要用户输入表达式（从文件读取），保存在一个字符串数组中，一个一个读取并判断其类型，当读取数字或小数点则进行转换，保存在栈里面。当读取到四则运算符号，取出栈里最顶端的两个元素进行运算。运算结果压栈。总操作数目必须等于符号数-1，每次运算前判断是否有两个运算数，否则表达式错误，输出提示信息。
2. 程序的流程
（1） 输入模块：完成表达式的输入，存入字符串数组representation中。
（2） 运算模块：设计一个类，保存压栈的数据。类中除构造函数与析构函数外，设成员函数进行压栈、弹栈、数据转换、计算的功能，当无法进行运算时，输出错误信息。
（3） 输出模块：在控制台或者文件中输出结果或错误提示信息。
三、 详细设计
1. 物理数据类型
题目要求输入一个逆波兰表达式，数据与数据，数据与操作符之间用一个空格隔开，最后以# 结束。
2. 算法的具体步骤
该程序实现约瑟夫环的流程图如下所示
3. 算法的时空分析
算法的运行时间复杂度为O(n)。
4. 输入输出的格式
输入
//输入一个逆波兰表达式（或者从文件读取，无提示信息）
输出
//输出读取到的逆波兰表达式
//输出结果或错误提示
四、 调试分析
程序经调试，输出结果正确，能够实现逆波兰表达式的求解。
五、 测试结果
（一）
基本要求
（二） 选做内容
六、 用户使用说明（可选）
本程序的运行环境为window 8操作系统，输入后缀表达式得到输出结果。
七、 实验心得
本实验编写一个使用栈的数据结构求解逆波兰表达式的程序。虽然栈的数据结构概念基本了解，但着手编写代码的时候在空间的分配问题上遇到了一些问题，经过查阅参考书籍发现需要使用realloc函数以便在空间不足的时候重新分配空间。
八、 附录
附件：逆波兰表达式求值
#include
#include
#include
using namespace std;
class Astack
{
private:
int size;
int top;
float *list;
bool g;
public:
Astack(int size=4)
{
size = size;
top = 0;
list = new float[size];
g = 1;
}
~Astack()
{
delete[]list;
}
void push(const float& it) //入栈
{
if(top==size)
return;
list[top++]=it;
}
float pop()
{
if(top==0)
{
g=0;
return 0;
}
return list[--top];
}
bool judge()
{
return g;
}
int length() const
{
return top;
}
};
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;
Astack t(size);
for(i=0;i47)
{
s=1;
if(g)
in=in*10+a[i]-48; //提取整数部分
else
{
de=(a[i]-48)*pow(0.1,k++)+de;
}
}
if(a[i]==46)
{
if(g==0)
{
cout << "小数点多余！";
return ;
}
g=0;
k=1;
}
if(a[i]==42||a[i]==43||a[i]==45||a[i]==47||a[i]==' ')
{
if(s)
{
t.push(in+de);in=0;de=0;g=1;s=0;
}
if(a[i]!=' ')
{
y=t.pop();
x=t.pop();
}
if(a[i]=='+') t.push(x+y);
if(a[i]=='-') t.push(x-y);
if(a[i]=='*') t.push(x*y);
if(a[i]=='/')
{
if(y==0)
{
cout << "分母为零！" << endl;
return;
}
t.push(x/y);
}
}
}
if(t.length()==1&&t.judge()&&a[i-1]<48) //最后一个字符
{
cout << "输出：" << int(t.pop()*100)/100.0 << endl;
}
else
cout << "表达式错误\n" << endl;
};
int main()
{
cout << "输入：";
char s[100];
while(gets(s))
Pretreatstr(s);
system("pause");
return 0;
}
浙公网安备 33021202002483