[Day10]程序菜鸟自学C++资料结构演算法 – 堆 叠应用：数制转换&括号匹配&汉诺塔

前言：今天要来实作数制转换、括号匹配和河内塔，这三个范例都是非常知名的堆叠应用，甚至会是程序竞赛的考题，所以今天就来带大家看看这些题目。

数制转换：

一样新增一个新的专案，这边注意一点，因为等等的练习同样需要用到上一篇写好的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');
}