前言：今天要來實作數制轉換、括號匹配和河內塔，這三個範例都是非常知名的堆疊應用，甚至會是程式競賽的考題，所以今天就來帶大家看看這些題目。

數制轉換：

一樣新增一個新的專案，這邊注意一點，因為等等的練習同樣需要用到上一篇寫好的Stack，所以可以先把程式碼複製下來(不包含main程式)，並新增一個標頭檔，這樣只要呼叫出來就可以了，不用在重寫一次。


之後就開始實作了。

先解釋std::cin >>s的意思，這個程式的意思是，先建立一個變數，輸入一個數字後換行，之後"cin"就是從鍵盤打數字，這個數字會儲存到變數"s"裡面

此範例用二進位制換算，更改d的值就能轉換成不同進位。

這樣就完成了，是不是很簡單，那我們繼續下一題。

括號匹配：

直接在這個專案新增項目就好，不用創建新的專案，但這邊要注意一個專案不能有兩個main程式，所以必須在之前實作的main程式用#if 0 和 #end if包起來。

程式碼範例

實作結果

這樣就成功了，括號匹配雖然看似簡單但是其實是非常重要的，還是不能輕忽！

河內塔問題：

先來解釋河內塔的遊戲規則。
有三根桿子A，B，C。A桿上有數個穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿；
每次只能移動一個圓盤且大盤不能疊在小盤上面。
提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規則。
試問要如何移？

圖片來源：https://sites.google.com/a/g2.nctu.edu.tw/unimath/_/rsrc/1512212597474/manuscript/hanoi/%E5%9C%96%E7%89%871.png?height=208&width=400

這就是河內塔的遊戲規則，接下來就用實作一一解答。

程式碼基本上就是這樣運行(用寫的太複雜，還是用畫的好了)

結果就如下圖

三個盤子，共要移動七次，也可以加上移動次數讓程式碼更完整。

本日小結：今天一次就講了三個實作，雖然很累但是也感覺非常充實，三道題目的程式碼都不長，不過括號匹配和河內塔的想法比較複雜，不是三五分鐘就可以搞懂的。這些題目所運用到的技術都有可能在未來使用到，不要認為這些程式碼只能用在對應的題目上，能融會貫通才是真正的學會喔(∩_∩)
明天也將要進入新的單元，大家加油！！！

堆疊標頭檔

#pragma once
template<typename T>
class SqlStack {
	T* data, * top_; //建立指針變量T指向元素，及top_指向堆疊的位置
	int capacity;

public:
	SqlStack(int cap = 3) {
		data = new T[cap];
		if (!data) { top_ = 0; capacity = 0; return; } //創建失敗的情況
		top_ = data; capacity = cap; //創建成功的條件
	}
	T& top() { //編寫top()檢查堆疊是否為空的，並返回T類型的引用變量
		if (top_ == data) throw "堆疊為空";
		return *(top_ - 1);
	}
	bool push(T e) { //編寫push()函式，且容量也會隨資料的增加變多
		if (top_ - data == capacity) {
			T* p = new T[2 * capacity];
			if (!p) return false;
			for (int i = 0; i < capacity; i++)
				p[i] = data[i];
			delete[] data; data = p;
			top_ = data + capacity;
			capacity = 2 * capacity;
		}
		*top_ = e; top_++; return true;
	}
	bool pop() { //編寫pop()函示，需先判對堆疊是否為空
		if (top_ == data) return false;
		top_--; return true;
	}
	bool empty() { //檢查堆疊是不是空的，與top()相同概念
		return top_ == data;
	}
	void clear() { //清除堆疊所有元素
		top_ == data;
	}
};

數制轉換

#include "SqlStack.h";
#include <iostream>;
using namespace std;

int main() {
	int n,d; //n為輸入的數字,d為要轉換的進制
	std::cin >> n;
	std::cin >> d;
	SqlStack<int> s;
	while (n) {
		s.push(n % d);
		n = n / d;
	}
	while (!s.empty()) {
		auto e = s.top();
		std::cout << e;
		s.pop();
	}
}

括號匹配

#include <iostream>
#include <string>
#include "SqlStack.h"
using std::string;
bool isLeft(char ch) { //判斷是否為左括弧
	return  ch == '(' || ch == '[' || ch == '{';
}
bool isRight(char ch) { //判斷是否為右括弧
	return  ch == ')' || ch == ']' || ch == '}';
}
bool isMatch(const char c1,const char c2) { //判斷是否匹配，const表示不會修改到
	if (c1 == '(' && c2 == ')' || c1 == '[' && c2 == ']' || c1 == '{' && c2 == '}')
		return true;
	return false;
}
bool is_match(string s) {
	SqlStack<char> stack;
	for (int i = 0; i <= s.size(); i++) {
		if (isLeft(s[i])) { //遇到左括弧則放入堆疊內
			stack.push(s[i]);
		}
		else if (isRight(s[i])) { //遇到右括弧則放到堆疊外
			if (stack.empty()) return false;
			char c = stack.top();
			if (!isMatch(c, s[i])) return false;
			stack.pop();
		}
	}
	if (stack.empty()) { //如果最後堆疊為空，表示括號匹配成功
		return true;
	return false;
	}
}

int main() {
	string s;
	std::cin >> s; //輸入s字串
	if(is_match(s))
		std::cout << s << "匹配成功";
	else 
		std::cout << s << "匹配失敗";
	return 0;
}

漢諾塔

#include<iostream>
void move(int x, char a, char b) {
	std::cout << x << "從" << a << "移到" << b << "\n";
}

void hanoi(int n, char x, char y, char z) { //n個盤字和xyz三根柱子，x為起點，z為終點，y為輔助
	if (n == 1) move(n, x, z); //只有一個盤子，從x移到z即可
	else {
		hanoi(n - 1, x, z, y); 
		move(n, x, z); 
		hanoi(n - 1, y, x, z); 
	}
}

int main() {
	hanoi(3, 'A', 'B', 'C');
}