一、实验目的
二．软件需求：数据对象：D={ ai |ai∈ElemSet,i=1,2,3,……，n，n≥0}
数据关系：R={<ai-1,ai,)>| ai-1,ai ∈D, i=2,3,……，n}约定a1为栈底，an 为栈顶。基本操作：Push(&s,e)
初始条件：栈s已经存在。
操作结果：插入元素e为新的栈顶元素
Pop(&s,&e)
初始条件：栈s已经存在且非空。
操作结果：删除s的栈顶元素，并用e返回其值
3 系统设计：
流程图：
二、实验内容及要求
当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实数范围内。对于异常表达式给出错误提示。
三、实验设备及软件。
PC机、VC++6.0
四、设计方案。
一 题目（老师给定或学生自定）：迷宫求解问题
二 设计的主要思路：
l 表达式用单链表储存，你可以看到这个链表中既有操作数又有操作符，如果你看过我的《如何在一个链表中链入不同类型的对象》，这里的方法也是对那篇文章的补充。
l 输入表达式时，会将原来的内容清空，并且必须按照中缀表示输入。如果你细看一下中缀表达式，你就会发现，除了括号，表达式的结构是“操作数”、“操作符”、“操作数”、……“操作符（＝）”，为了统一这个规律，同时也为了使输入函数简单一点，规定括号必须这样输入“0（”、“）0”；这样一来，“0”就不能作为操作数出现在表达式中了。因为我没有在输入函数中增加容错的语句，所以一旦输错了，那程序就“死”了。
l 表达式求值的过程是，先变成后缀表示，然后用后缀表示求值。因为原书讲解的是这两个算法，并且用这两个算法就能完成中缀表达式的求值，所以我就没写中缀表达式的直接求值算法。具体算法说明参见原书，我就不废话了。
l Calculate()注释掉的两行，“％”是因为只对整型表达式合法，“^”的Power()函数没有完成。
l isp()，icp()的返回值，原书说的不细，我来多说两句。‘＝’（表达式开始和结束标志）的栈内栈外优先级都是最低。‘（’栈外最高，栈内次最低。‘）’栈外次最低，不进栈。‘^’栈内次最高，栈外比栈内低。‘×÷％’栈内比‘^’栈外低，栈外比栈内低。‘＋－’栈内比‘×’栈外低，栈外比栈内低。这样，综合起来，就有9个优先级，于是就得出了书上的那个表。(CSDN)
三 主要功能：
《1》生成迷宫地图
《2》寻找出口路径
《3》随机生成迷宫地图
《4》取得当前通道块当前方向上的下一个通道块
《5》显示迷宫地图
说明：此五个函数模块主要为最后生成一个动态的迷宫作准备。
五、主要代码及分析
//-------------------栈数据结构的声明----------------------------
#include<iostream.h>
#include<fstream.h>
#include <string.h>
#include<iomanip.h>
#include<assert.h>
#include <ctype.h>
#include <conio.h>
#include <stdlib.h>
#include <strstrea.h>
const int SM = 100;
template <class Type> //顺序栈的类定义
class Stack
{
public:
Stack(int=100);//构造函数，初始化栈
~Stack()//析构函数，删除栈中的动态空间
{
delete [] elements;
}
void Push(const Type &item);//向栈中插入元素
Type GetTop();//读取栈顶元素
Type Pop();//从栈中删除元素
void MakeEmpty()//清空栈
{ top=-1;}
int IsEmpty()const//判断栈是否为空
{
return top==-1;
}
int IsFull()const//判断是否已满
{
return top==MaxSize-1;
}
private:
Type *elements;//存放栈中元素的栈数组
int top;//栈顶指针
int MaxSize;//栈的最大可容纳元素个数
};
//---------------栈成员函数的实现---------------
template<class Type>Stack<Type>::Stack(int s):top(-1),MaxSize(s)
{//建立一个最大尺寸为s的空栈，若分配不成功则错误处理。
elements=new Type[MaxSize]; //创建栈空间
assert(elements!=0); //断言：动态存储成功分配与否
}
template<class Type>void Stack<Type>::Push(const Type &item)
{//若栈不满，则将元素item插入到该栈的的栈顶，否则出错处理
assert(!IsFull());
elements[++top] = item;
}
template<class Type>Type Stack<Type>::Pop()
{//如果栈不空则函数返回该栈顶元素的值然后栈顶指针退1
assert(!IsEmpty()); // 断言：判断栈空否，若断言成立则继续执行
return elements[top--]; //返回栈顶元素的值
}
template<class Type>Type Stack<Type>::GetTop()
{//若栈不空则返回该栈顶元素的值
assert(!IsEmpty()); //断言：判断栈空否，若断言成立则继续执行
return elements[top]; //返回栈顶元素的值
}
//----------------------------工具函数的定义------------------------------
//求运算符优先级
int Youxianji(char op)
{
switch (op)
{
case '+':
case '-':
return 1;//定义加减运算的优先级为1
case '*':
case '/':
return 2;//定义乘除运算的优先级为2
case '(':
case '[':
case '{':
case '=':
default:
return 0;//定义在栈中的左括号和栈底字符的优先级为0
}
}
//将中缀表达式转换成后缀表达式
void Change(char *s1,char *s2)
{
Stack<char> R(SM);//定义用于暂存运算符的栈
R.Push('=');//给栈底放入‘='字符，它具有最低优先级0
int i,j;
i = 0;//用于指示扫描s1串中字符的位置，初值为0
j = 0;//用于指示s2串中待存字符的位置，初值为0
char ch = s1[i];
while (ch != '=')
{
if (ch == ' ')
{
ch = s1[++i];//对于空格字符不做任何处理
}
//-------------------------------------------------------------
else if (ch == '(')
{//对于左括号，直接进栈
R.Push(ch);
ch = s1[++i];
}
else if (ch == ')')
{//对于右括号，使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while (R.GetTop() != '(')
{
s2[j++] = R.Pop();
}
R.Pop();//删除栈顶的左括号
ch = s1[++i];
}
//-------------------------------------------------
else if (ch == '[')
{//对于左括号，直接进栈
R.Push(ch);
ch = s1[++i];
}
else if (ch == ']')
{//对于右括号，使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while (R.GetTop() != '[')
{
s2[j++] = R.Pop();
}
R.Pop();//删除栈顶的左括号
ch = s1[++i];
}
//---------------------------------------------
else if (ch == '{')
{//对于左括号，直接进栈
R.Push(ch);
ch = s1[++i];
}
else if (ch == '}')
{//对于右括号，使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while (R.GetTop() != '{')
{
s2[j++] = R.Pop();
}
R.Pop();//删除栈顶的左括号
ch = s1[++i];
}
//---------------------------------------------------
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{//对于四则运算符，使暂存在栈中的不低于ch优先级
//的运算符依次出栈并写入到s2中
char w = R.GetTop();
while (Youxianji(w) >= Youxianji(ch))
{//Youxianji()函数返回运算符形参的优先级
s2[j++] = w;
R.Pop();
w = R.GetTop();
}
R.Push(ch);
ch = s1[++i];
}
else
{//此处为数字或小数点字符的处理
while (isdigit(ch) || ch == '.')
{
s2[j++] = ch;
ch = s1[++i];
}
s2[j++] = ' ';//被转换后的每个数值后放一个空格
}
}
//---------------------------------------------------------
ch = R.Pop();
while (ch != '=')
{
if (ch == '('||ch == '{'||ch == '[')
{
cout<<"表达式错误!"<<endl;
exit(1);
}
else
{
s2[j++] = ch;
ch = R.Pop();
}
}
s2[j++] = '=';//加入字符串结束符
s2[j++] = '\0';
}
//计算后缀表达式值
float Compute(char *s2)
{
Stack<float> S(SM);//用S栈存储操作数和中间计算结果
istrstream ins(s2);//把s2定义为输入字符串流对象ins
char ch;//用于输入字符
float x;//用于输入浮点数
ins>>ch;
while (ch != '=')
{
switch (ch)
{
case '+':
x = S.Pop() + S.Pop();
break;
case '-':
x = S.Pop();
x = S.Pop() - x;
break;
case '*':
x = S.Pop() * S.Pop();
break;
case '/':
x = S.Pop();
if (x != 0.0)//判断除数是否为零
{
x = S.Pop() / x;
}
else
{
cout<<"除数不能为零!"<<endl;
exit(1);
}
break;
default:
ins.putback(ch);
ins>>x;
}
S.Push(x);
ins>>ch;
}
if (!S.IsEmpty())
{
x = S.Pop();
if (S.IsEmpty())//如果栈中只有一个值那一定是结果
{
return x;
}
else
{
cout<<"表达式错误!"<<endl;
exit(1);
}
}
else
{
cout<<"表达式错误!"<<endl;
exit(1);
}
}
//判断是否为运算符
int IsYf(char ch)
{
switch (ch)
{
case '+':
case '-':
case '*':
case '/':
return 1;
break;
default:
return 0;
break;
}
}
//提示信息显示
void Tishi(int n)
{
switch (n)
{
case 0:
cout<<"..."<<endl;
break;
case 1:
cout<<"\n表达式首字符不能是运算符...请重新输入"<<endl;
break;
case 2:
cout<<"\n表达式中的运算符输入有误...请重新输入"<<endl;
break;
case 3:
cout<<"\n表达式中有非法字符...请重新输入"<<endl;
break;
case 4:
cout<<"\n没有以'='字符结束...请重新输入"<<endl;
break;
case 5:
cout<<"\n表达式括号不配对...请重新输入"<<endl;
break;
default:
break;
}
}
//检查表达式是否有错
int Test(char *s1)
{
char ch;
int i=0;
int left1 = 0;//统计左括号
int right1 = 0;//统计右括号
int left2 = 0;//统计左括号
int right2 = 0;//统计右括号
int left3 = 0;//统计左括号
int right3 = 0;//统计右括号
ch = s1[i++];
if (ch =='\0')//没有输入了表达式
{
Tishi(0);
return 0;
}
if (IsYf(ch))//第一个是运算符
{
Tishi(1);
return 0;
}
while (ch != '\0')
{
if (IsYf(ch) && IsYf(s1[i]))//运算符错误
{
Tishi(2);
return 0;
}
if ((ch < '0') || (ch > '9'))//有否非法字符
{
switch (ch)
{
case '('://合法字符
left1++;
break;
case ')':
right1++;
break;
case '['://合法字符
left2++;
break;
case ']':
right2++;
break;
case '{'://合法字符
left3++;
break;
case '}':
right3++;
break;
case ' ':
case '+':
case '-':
case '*':
case '/':
case '=':
case '.':
break;
default://非法字符
Tishi(3);
return 0;
break;
}
}
ch = s1[i++];
}
if (s1[i-2] != '=')//结束符错误
{
Tishi(4);
return 0;
}
if (left1!=right1||left2!=right2||left3!=right3)//括号问题
{
Tishi(5);
return 0;
}
return 1;//表达式正确
}
//-----------------------------END--------------------------
//-----------------------------主函数------------------
void main()//主程序
{
char str1[50],str2[50]; //暂时存储表达式
int i;
cout<<" =================欢迎使用！=================="<<endl;
cout<<endl;
while(i!=0)
{
cout<<" 请输入一个以'='字符结束的中缀算术表达式："<<endl;
cin.getline(str1,sizeof(str1));
while(!Test(str1)) //检查表达式是否正确
{
cin.getline(str1,sizeof(str1));
}
Change(str1,str2); //处理结果
cout<<"\n求值结果为： "<<str1<<Compute(str2)<<endl;
cout<<endl;
cout<<"如果继续请输入 ：1"<<endl;
cin>>i;
}
}
//-----------------------------END-----------------------------
六．测试结果及说明
=================欢迎使用！==================
请输入一个以'='字符结束的中缀算术表达式：
{(0-3+4+9)*(0-3)*7/[(0-5)*2]-7}*2=
求值结果为： {(0-3+4+9)*(0-3)*7/[(0-5)*2]-7}*2=
如果继续请输入 ：1
3.5+12.3*15+8-(3/2+1)+2*2+3.2*3-5/6-3=
请输入一个以'='字符结束的中缀算术表达式：
求值结果为： .5+12.3*15+8-(3/2+1)+2*2+3.2*3-5/6
如果继续请输入 ：1
1
请输入一个以'='字符结束的中缀算术表达式：
...
2-2+5/7-[3+(1+2+3-9)*(4+5+6+7)]/9+8=
求值结果为： 2-2+5/7-[3+(1+2+3-9)*(4+5+6+7)]/9+
如果继续请输入 ：1
1
请输入一个以'='字符结束的中缀算术表达式：
...
(23-12.33)/{1.2+[(23-12.3)*(13-5)-6]/2}=
求值结果为： (23-12.33)/{1.2+[(23-12.3)*(13-5)-
如果继续请输入 ：1
1
请输入一个以'='字符结束的中缀算术表达式：
...
1/2/3/4/5/6/7/8/9=
求值结果为： 1/2/3/4/5/6/7/8/9=2.75573e-006
如果继续请输入 ：1
3,3*5+[12-(22-3*5)]+11*3.4=
请输入一个以'='字符结束的中缀算术表达式：
表达式中有非法字符...请重新输入
3.3*5+[12-(22-3*5)]+11*3.4=
求值结果为： 3.3*5+[12-(22-3*5)]+11*3.4=58.9
如果继续请输入 ：1
七、实验总结与心得体会
实验总结：
该程序虽然能运行出预计的结果但是还存在一些问题
1．由于对栈的算法的推敲不足，使程序调试时有些费时
2．本程序有些代码不够完善，有待进一步改进。
心得体会：
6 总结：
表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例子。这里用静态栈实现表达式求值，包含了加，减，乘，除等符号的运算，很有意义。
对自己又有了进一步的提高，并对数据结构这门课有更深刻的认识。