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

1、数据结构实验报告实验四 实验题目：排序算法 学号： 日期：2014.12.4班级：物联网工程姓名： Email：实验目的：堆栈的应用任务要求： 一、实验目的 掌握堆栈的使用。 二、实验内容 1、计算数学表达式的值。输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、“)构成，例如 2 + 3 * ( 4 + 5 ) 6 / 4。假定表达式输入格式合法。2、以一个 m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。迷宫根据一个迷宫数据文

2、件建立。迷宫数据文件由一个包含0、1的矩阵组成。迷宫的通路可以使用通路上各点的坐标序列进行展示(使用图形展示最佳)。软件环境：Win7 操作系统开发工具：visual C+ 6.0实验步骤：template<class T>class 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<T

3、>& Add(const T& x);Stack<T>& Delete(T& x); Tpop() ;private:int top; / 栈顶int MaxTop; / 最大的栈顶值T *stack; / 堆栈元素数组;template<class T>Stack<T>:Stack(int MaxStackSize)MaxTop = MaxStackSize - 1;stack = new TMaxStackSize;top = -1;template<class T>T Stack<T>:To

4、p() constreturn stacktop;template<class T>Stack<T>& Stack<T>:Add(const T& x)stack+top = x;return *this;template<class T>Stack<T>& Stack<T>:Delete(T& x)x = stacktop-;return *this;template<class T>T Stack<T>:pop()T it=-1;if (top = 0) retu

5、rn it;it = stack-top;return it;#include <iostream>#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

6、, 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<int> pathStack;/定义栈 public:MazeSolveMethod() :pathStack(100)MazeSolveMethod() void findPath(int startX, int startY)

7、;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 << "进入方法！" << endl;while (true)if (mazex - 1y = 0)pathStack.Add(-x);pathStack.Add(y);mazexy = 2;else if (mazexy - 1 = 0)p

8、athStack.Add(x);pathStack.Add(-y);mazexy = 2;else if (mazexy + 1 = 0)pathStack.Add(x);pathStack.Add(+y);mazexy = 2;else if (mazex + 1y = 0)pathStack.Add(+x);pathStack.Add(y);mazexy = 2;if (mazex - 1y != 0 && mazexy + 1 != 0 && mazex + 1y != 0 && mazexy - 1 != 0)if (x >= 8

9、&& 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; i<10; i+)for (int j = 0;

10、 j<10; j+)if (mazeij = 2)cout << '*' << " "else if (mazeij = 3)cout << 0 << " "elsecout << 1 << " "cout << endl;Stack<char> OPTR;Stack<int> OPND;char c;char Precede(char ch1, char ch2);int Operate(char m,

11、char ch, char n);void Charge(char & c);int main()OPTR.Add('=');cout << "输入表达式,以=结尾" << endl;docin >> c;if (c = '+' | c = '-' | c = '*' | c = '/' | c = '(' | c = '=' | c = ')')Charge(c);elseOPND.Add(c - &#

12、39;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

13、x = 0; x < 10; x+)cin >> 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 < 9; x+)if (mazex0 = 0)mazex0 = 2;if (mazex9 = 0)mazex9 =

14、 2;solve.printPath();system("pause");return 0;/下面这个函数判定两个算符的优先级 char Precede(char ch1, char ch2)if (ch1 = '+' | ch1 = '-' | ch1 = '*' | ch1 = '/' | ch1 = '(' | ch1 = '=') && ch2 = '('| (ch1 = '+' | ch1 = '-' |

15、ch1 = '(' | ch1 = '=') && (ch2 = '/' | ch2 = '*')| (ch1 = '(' | ch1 = '=') && (ch2 = '+' | ch2 = '-')return '>'else if (ch1 = '('&&ch2 = ')')return '='else if (ch1 = '='

16、&&ch2 = '=')return 'q'elsereturn '<'/下面这个函数为进行二元运算m OP n int Operate(char m, char ch, char n)switch (ch)case '+':return m + n;break;case '-':return m - n;break;case '*':return m*n;break;case '/':return m / n;break;return 0;void Charge(char & c)char temp;int temp1, temp2;switch (Precede(O