棧的一些小小應用

昨天剛實現了棧的一些基本操作，今天就來實現一點棧的應用把！

首先，寫一點比較簡單的：

1.逆波蘭表達式的計算。

    在通常的表達式中，二元運算符總是置于與之相關的兩個運算對象之間，這種表示法也稱為中綴表示。逆波蘭表達式也稱為后綴表達式。比如：

    兩種表達式如果在程序中運行時，后綴表達式不需要考慮符號優先級的問題。

現在通過一個程序去計算一個簡單的后綴表達式：

#pragma once

#include <iostream>
#include <assert.h>
#include <stack>
using namespace std;

enum Type
{
	OP_NUM,//數字
	OP_SYMBOL,//運算符
};

enum SYMBOL
{
	ADD,
	SUB,
	MUL,
	DIV,
};

struct Cell
{
	Type _type;//類型（1.數字 2.運算符）
	int _value;
};

int CountSymbol(Cell a[], size_t size)
{
	assert(a);
	stack<int> s;

	for (size_t i = 0; i < size; i++)//依次讀取每個數據
	{
		if (a[i]._type == OP_NUM)
		{
			s.push(a[i]._value);
		}
		else
		{
			//取出運算符前面的兩個數字進行計算
			int right = s.top();
			s.pop();//棧的特性，只能pop一個后去下一個數
			int left = s.top();
			s.pop();

			switch (a[i]._value)
			{
				//把計算結果壓入棧中
			case ADD:
				s.push(left + right);
				break;
			case SUB:
				s.push(left - right);
				break;
			case MUL:
				s.push(left * right);
				break;
			case DIV:
				s.push(left / right);
				break;
			}
		}
	}
	return s.top();
}

void TestSymbol()
{
	//12*(3+4)-6+8/2 = 82
	//12 3 4 + * 6 - 8 2 / +   逆波蘭表達式
	Cell a[] =
	{
		{OP_NUM,12},
		{OP_NUM, 3},
		{OP_NUM,4},
		{OP_SYMBOL,ADD},
		{OP_SYMBOL,MUL},
		{OP_NUM,6},
		{OP_SYMBOL,SUB},
		{OP_NUM,8},
		{OP_NUM,2},
		{OP_SYMBOL,DIV},
		{OP_SYMBOL,ADD},
	};
	int ret = CountSymbol(a, sizeof(a) / sizeof(a[0]));
	cout << "ret=" << ret << endl;
}

在這個程序中可以看到應用了棧的一個重要特性，“后進先出”。

2.迷宮是一個很長久的話題，今天我就用代碼來實現它。

迷宮問題有一個很重要的點，就是“回溯”，顧名思義，就是沿著走過的路依次往回走。

為了簡單起見，直接寫一個迷宮，定義為“Maze.txt”文件

                              （0表示通路，1表示墻）

把走過的路的坐標保存在一個棧中，當無路可走的時候，從棧中依次pop出的坐標回溯，直到找到正確的路或者沒有通路為止！

代碼實現如下：

#pragma once

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#define N 10

#include <iostream>
#include <stack>
#include <assert.h>

using namespace std;

struct Pos//記錄坐標
{
	int _row;//行
	int _col;//列
};

void GetMaze(int * a, int n)//讀取迷宮
{
	FILE * fout = fopen("Maze.txt", "r");
	assert(fout);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; )
		{
			char ch = fgetc(fout);
			if (ch == '0' || ch == '1')
			{
				a[i*n + j] = ch - '0';
				j++;//有數據時，才往二維數組中存，所以j++放在這里
			}
			else
			{
				continue;
			}
		}
	}
	fclose(fout);
}

void printMaze(int * a, int n)//輸出迷宮
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << a[i*n + j] << " ";
		}
		cout << endl;
	}
}

bool CheckIsAccess(int * a, int n, Pos next)//檢查是否通行
{
	assert(a);
	if (next._row >= 0 && next._row < n&&
		next._col >= 0 && next._col < n&&
		a[next._row*n + next._col] == 0)// 0 表示可以通行
	{
		return true;
	}
	else
	{
		return false;
	}
}


bool MazePath(int *a, int n, const Pos & entry, stack<Pos>& path)
{
	Pos cur = entry;
	path.push(cur);

	while (!path.empty())//棧空的時候返回起點
	{
		a[cur._row*n + cur._col] = 2;//走過的路標記為2

		if (cur._row == n - 1)//判斷是否到出口
		{
			return true;
		}
		//向上
		Pos next = cur;
		next._row--;
		if (CheckIsAccess(a, n, next))//判斷
		{
			cur = next;
			path.push(cur);//走過的坐標push進棧
			continue;
		}
		//向下
		next = cur;//每次判斷的時候重新賦值給next
		next._row++;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		//向左
		next = cur;
		next._col--;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		//向右
		next = cur;
		next._col++;
		if (CheckIsAccess(a, n, next))
		{
			cur = next;
			path.push(cur);
			continue;
		}
		//無路可走
		a[cur._row*n + cur._col] = 3;
		path.pop();
		if (!path.empty())
		{
			cur = path.top();
		}
	}

	return false;
}

void TestMaze()
{
	int a[N][N] = {};
	GetMaze((int *)a, N);
	printMaze((int *)a, N);

	stack<Pos> path;
	Pos entry = { 2,0 };

	MazePath((int *)a, N, entry, path);
	cout << "結果" << endl;
	printMaze((int *)a, N);

}

輸出的結果是：

數字“2”表示通路。

歡迎各位大神吐槽。