山东大学数据结构实验四堆栈的应用.doc

数据结构实验报告实验四实验题目：排序算法 学号： 日期：2014.12.4班级：物联网工程姓名： Email：实验目的：堆栈的应用任务要求：一、实验目的 掌握堆栈的使用。 二、实验内容 1、计算数学表达式的值。输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、“)构成，例如 2 + 3 * ( 4 + 5 ) 6 / 4。假定表达式输入格式合法。2、以一个 m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。迷宫根据一个迷宫数据文件建立。迷宫数据文件由一个包含0、1的矩阵组成。迷宫的通路可以使用通路上各点的坐标序列进行展示(使用图形展示最佳)。软件环境：Win7 操作系统开发工具：visual C+ 6.0实验步骤：templateclass Stack / LIFO 对象public:Stack(int MaxStackSize = 10);Stack() delete stack; bool IsEmpty() const return top = -1; bool IsFull() const return top = MaxTop; T Top() const;Stack& Add(const T& x);Stack& Delete(T& x); Tpop() ;private:int top; / 栈顶int MaxTop; / 最大的栈顶值T *stack; / 堆栈元素数组;templateStack:Stack(int MaxStackSize)MaxTop = MaxStackSize - 1;stack = new TMaxStackSize;top = -1;templateT Stack:Top() constreturn stacktop;templateStack& Stack:Add(const T& x)stack+top = x;return *this;templateStack& Stack:Delete(T& x)x = stacktop-;return *this;templateT Stack:pop()T it=-1;if (top = 0) return it;it = stack-top;return it;#include #include stack.h using namespace std;static int maze1010= 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 0, 0, 1, 1, 0, 0, 0, 0, 1 , 1, 0, 0, 0, 1, 0, 1, 0, 0, 1 , 1, 0, 0, 0, 0, 0, 1, 1, 0, 1 , 1, 0, 1, 0, 0, 0, 1, 1, 1, 1 , 1, 0, 1, 1, 1, 0, 1, 1, 1, 1 , 1, 0, 1, 1, 1, 0, 1, 1, 1, 1 , 1, 1, 1, 1, 1, 0, 0, 0, 1, 1 , 1, 1, 1, 1, 1, 1, 1, 0, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ,;/存放迷宫数据 class MazeSolveMethodprivate:Stack pathStack;/定义栈 public:MazeSolveMethod() :pathStack(100)MazeSolveMethod() void findPath(int startX, int startY);void printPath() const;void MazeSolveMethod:findPath(int startX, int startY)int x = startX;int y = startY;pathStack.Add(x);pathStack.Add(y);mazexy = 2;cout 进入方法！ = 8 & y = 8)break;elsemazexy = 3;y = pathStack.pop();x = pathStack.pop();y = pathStack.Top();int temp = pathStack.pop();x = pathStack.Top();pathStack.Add(temp);void MazeSolveMethod:printPath() constcout printPath endl;for (int i = 0; i10; i+)for (int j = 0; j10; j+)if (mazeij = 2)cout * ;else if (mazeij = 3)cout 0 ;elsecout 1 ;cout endl;Stack OPTR;Stack OPND;char c;char Precede(char ch1, char ch2);int Operate(char m, char ch, char n);void Charge(char & c);int main()OPTR.Add(=);cout 输入表达式,以=结尾 c;if (c = + | c = - | c = * | c = / | c = ( | c = = | c = )Charge(c);elseOPND.Add(c - 0); while (c != = | OPTR.Top() != =);cout 结果是: OPND.Top() endl;/*cout 请输入迷宫10*10: endl;for (int z = 0; z 10; z+)cout 第 z+1 行: endl;for (int x = 0; x mazezx;cout endl 输入完毕 endl;*/MazeSolveMethod solve;solve.findPath(1, 1);for (int y = 0; y 10; y+)if (maze0y=0)maze0y = 2;if (maze9y = 0)maze9y = 2;for (int x= 1; x ;else if (ch1 = (&ch2 = )return =;else if (ch1 = =&ch2 = =)return q;elsereturn :OPTR.Add(c);break;case =:OPTR.Delete(temp);br