堆栈的应用 计算数学表达式的值、迷宫.doc

堆栈的应用 计算数学表达式的值、迷宫实验四堆栈的应用一、实验目的掌握堆栈的使用。二、实验内容1、计算数学表达式的值。输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符+、-、*、/、(、)构成，例如2+3*(4+5) 6/4。假定表达式输入格式合法。*2、以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。迷宫根据一个迷宫数据文件建立。迷宫数据文件由一个包含0、1的矩阵组成。迷宫的通路可以使用通路上各点的坐标序列进行展示(使用图形展示最佳)。*计算数学表达式的值*在此没先转成后缀表达式，代码写得不好*#pragma once#includeNoMem.h#includeOutOfBounds.htemplate class Tclass Stackpublic：Stack(int MaxStackSize=10)；Stack()delete stack；bool IsEmpty()constreturn top=-1；bool IsFull()constreturn top=MaxTop；T Top()const；Stack T&Add(const T&x)；Stack T&Delete(T&x)；private：int top；int MaxTop；T*stack；template class TStack T：Stack(int MaxStackSize)MaxTop=MaxStackSize-1；stack=new TMaxStackSize；top=-1；template class TT Stack T：Top()constif(IsEmpty()throw OutOfBounds()；else return stacktop；template class TStack T&Stack T：Add(const T&x)if(IsFull()throw NoMem()；stack+top=x；return*this；template class TStack T&Stack T：Delete(T&x)if(IsEmpty()throw OutOfBounds()；x=stacktop-；return*this；*#pragma once class OutOfBoundspublic：OutOfBounds(void)OutOfBounds(void)；*#pragma once class NoMempublic：NoMem(void)NoMem(void)；*/exp4计算数学表达式的值.cpp：定义控制台应用程序的入口点。/#includestdafx.h#include string#includeStack.h#include iostream using namespace std；const int MaxLength=100；float count(const char*expr)Stack char sign(MaxLength)；Stack float data(MaxLength)；sign.Add(#)；float j,k；char temp；int length=strlen(expr)；for(int i=0；i length；i+)/couttest：exprisign：sign.Top()endl；if(expri！=+&expri！=-&expri！=*&expri！=/&expri！=(&expri！=)/expri为数据if(sign.Top()！=*&sign.Top()！=/)/expri为数据且符号栈的顶部不是*或/data.Add(float)expri-48)；/coutdata：data.Top()；else if(sign.Top()=*)/符号栈的顶部为*data.Delete(j)；j=j*(float)expri-48)；/coutdataj：j endl；data.Add(j)；sign.Delete(temp)；/cout sign.Top()；else/符号栈的顶部为/data.Delete(j)；j=j/(float)expri-48)；data.Add(j)；sign.Delete(temp)；else if(expri=(|expri=*|expri=/)sign.Add(expri)；/coutaaa：sign.Top()；else if(expri=+|expri=-)if(sign.Top()！=+&sign.Top()！=-)sign.Add(expri)；/coutsign+：sign.Top()；else if(sign.Top()=+)data.Delete(j)；data.Delete(k)；k=j+k；data.Add(k)；sign.Delete(temp)；sign.Add(expri)；elsedata.Delete(j)；data.Delete(k)；k=k-j；data.Add(k)；sign.Delete(temp)；sign.Add(expri)；else/expri为)if(sign.Top()=+)data.Delete(j)；data.Delete(k)；k=j+k；data.Add(k)；sign.Delete(temp)；sign.Delete(temp)；if(sign.Top()=*)data.Delete(j)；data.Delete(k)；k=j*k；data.Add(k)；sign.Delete(temp)；else if(sign.Top()=/)data.Delete(j)；data.Delete(k)；k=k/j；data.Add(k)；sign.Delete(temp)；else if(sign.Top()=-)data.Delete(j)；data.Delete(k)；k=k-j；data.Add(k)；sign.Delete(temp)；sign.Delete(temp)；if(sign.Top()=*)data.Delete(j)；data.Delete(k)；k=j*k；data.Add(k)；sign.Delete(temp)；else if(sign.Top()=/)data.Delete(j)；data.Delete(k)；k=k/j；data.Add(k)；sign.Delete(temp)；elsesign.Delete(temp)；if(！(sign.Top()=#)if(sign.Top()=+)data.Delete(j)；data.Delete(k)；k=j+k；data.Add(k)；/coutlast：sign.Top()；sign.Delete(temp)；else if(sign.Top()=-)data.Delete(j)；data.Delete(k)；k=k-j；data.Add(k)；/coutlast-：sign.Top()；sign.Delete(temp)；return data.Top()；int _tmain(int argc,_TCHAR*argv)char exprMaxLength；coutType an expression of length at mostMaxLength endl；cin.getline(expr,MaxLength)；coutThe result is：count(expr)；system(pause)；return 0；*迷宫*#pragma once class Positionpublic：friend bool FindPath()；friend void OutputPath()；Position(void)Position(void)private：int row；int col；*#pragma once#includeNoMem.h#includeOutOfBounds.htemplate class Tclass Stackpublic：Stack(int MaxStackSize=10)；Stack()delete stack；bool IsEmpty()constreturn top=-1；bool IsFull()constreturn top=MaxTop；T Top()const；Stack T&Add(const T&x)；Stack T&Delete(T&x)；private：int top；int MaxTop；T*stack；template class TStack T：Stack(int MaxStackSize)MaxTop=MaxStackSize-1；stack=new TMaxStackSize；top=-1；template class TT Stack T：Top()constif(IsEmpty()throw OutOfBounds()；else return stacktop；template class TStack T&Stack T：Add(const T&x)if(IsFull()throw NoMem()；stack+top=x；return*this；template class TStack T&Stack T：Delete(T&x)if(IsEmpty()throw OutOfBounds()；x=stacktop-；return*this；*#pragma once class NoMempublic：NoMem(void)NoMem(void)；*#pragma once class OutOfBoundspublic：OutOfBounds(void)OutOfBounds(void)；*/maze.cpp：定义控制台应用程序的入口点。/#includestdafx.h#include iostream#includeStack.h#includePosition.husing namespace std；int*maze,m,n；/m行n列的迷宫Stack Position*path；void InputMaze()coutPlease input the number of row and col；cin mn；/maze=new intm+1n+1；maze=new int*m+2；maze0=new intn+2；mazem+1=new intn+2；for(int k=1；k=m；k+)mazek=new intn+2；coutinput thekth row：；/cin.getline(mazek,n)；for(int i=1；i=n；i+)cin mazeki；cout endl；bool FindPath()path=new Stack Position(m*n-1)；Position offset4；offset0.row=0；offset0.col=1；offset1.row=1；offset1.col=0；offset2.row=0；offset2.col=-1；offset3.row=-1；offset3.col=0；/maze0=new int*n+2；/mazem+1=new int*n+2；/initialize wall of obstacles around maze for(int a=0；a=m+1；a+)mazea0=mazean+1=1；/left and right for(int j=0；j=n+1；j+)maze0j=mazem+1j=1；/top and bottom Position here；here.row=1；here.col=1；maze11=1；int option=0；int LastOption=3；/search for apath while(here.row！=m|here.col！=n)int r,c；while(option=LastOption)r=here.row+offsetoption.row；c=here.col+offsetoption.col；if(mazerc=0)break；option+；/was aneighbor found?if(option=LastOption)path-Add(here)；here.row=r；here.col=c；mazerc=1；option=0；elseif(path-IsEmpty()return false；Position next；path-Delete(next)；if(next.row=here.row)option=2+next.col-here.col；else option=3+next.row-here.row；here=next；return true；void OutputPath()in