四川大学《数据结构与算法分析》课程设计报告 带括号的算术表达式.doc
文本预览下载声明
《数据结构与算法分析》课程设计报告
课题名称： 带括号的算数表达式求值
课题设计人（学号）：
指导教师： 朱宏
评阅成绩：
评阅意见：
提交报告时间：2014 年 12月 9日
带括号的算数表达式求值
计算机类 专业
学生 指导老师 朱宏
[摘要] 在平时的生活中，我们可以解决一些简单的算术表达式，如果当我们遇到一些式子较为冗长，运算比较复杂的算术表达式时，我们都会选择计算器。那么，计算器又是通过怎样的原理来进行运算的呢。
本程序利用堆栈先进后出的特点，采用操作数和操作符两个堆栈，实现由中缀表达式到后缀表达式的转换并求值的过程。带括号的算术表达式的求值是堆栈的一个典型的应用实例。
关键词：计算器 堆栈 C++
一、实验名称:带括号的算术表达式求值?
二、实验的目的和要求:?
1.采用算符优先数算法,能正确求值表达式;?
2.熟练掌握栈的应用;?
3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C++程序;?
4.上机调试程序,掌握查错、排错使程序能正确运行。
三、实验的环境：
硬件环境：
处理器：Inter(R) Core(TM) i7-4500U
内存：8.00GB
软件环境：
操作系统：Windows8.1
编译软件：Microsoft Visual Studio 2012
四、算法描述:
我设计的带有括号的算术表达式求值的程序中，运算符的优先级是这样子的：
先乘除，后加减
同级运算从左到右依次运算。
先括号内的运算，再括号外的运算。
我的设计思路是，先输入一个最后不带等于号的中缀表达式，先对表达式检查是否有错误，如果有将会输出“表达式有错误”，否则通过堆栈方法将这个中缀表达式转化为后缀表达式，然后将后缀表达式求值。
函数清单：
transform()——用于将中缀表达式转换为后缀表达式
calculate()——将后缀表达式进行求值
examine()——检查输入的表达式是否有错误
main()——主程序。
五：源程序清单：
#include iostream
#include cmath
#include stack
#include string
using namespace std;
string transform(string str)//转换为后缀表达式
{
stackchar ope;
int i;
string exp=;
for(i=0;iint(str.size());i++)
{
if(str[i]==.||isdigit(str[i]))
{
exp+=str[i];
}
else if(str[i]==+||str[i]==-)
{
int j=i-1;
if(isdigit(str[j]))
{
exp+= ;//每个数字的后面都加一个空格加以区分
if(ope.empty()||ope.top()==()
{
ope.push(str[i]);
}
else
{
while(!ope.empty()ope.top()!=()
{
exp+=ope.top();
ope.pop();
}
ope.push(str[i]);
}
}
else
{
if(ope.empty()||ope.top()==()
{
ope.push(str[i]);
}
else
{
while(!ope.empty()ope.top()!=()
{
exp+=ope.top();
ope.pop();
}
ope.push(str[i]);
}
}
}
else if(str[i]==*||str[i]==/||str[i]==%)
{
int j=i-1;
if(isdigit(str[j]))
{
exp+= ;
if(ope.empty()||ope.top()==(||ope.top()==+||ope.top()==-)
{
ope.push(str[i]);
}
else
{
while(!ope.empty
显示全部