@这篇文档是由C++代码实现的栈，并对以栈为基础的括号匹配、进制转换等问题进行了解决

栈是一种后进先出的数据结构。其中生活中以摞盘子为例最为实际。本文是以Visual Studio中新建的C++win32的控制台应用程序实现的，其中建立了头文件和源文件以及实现main()的demo文件，分别是MyStack.h和MyStack.cpp和demo.cpp,以及Coordinate.h和Coordinate.cpp文件。

其中MyStack.h和MyStack.cpp文件是建立一个栈的模板类，方便以后调用其中的函数。Coordinate.h和Coordinate.cpp文件主要是建立一个坐标属性的类，方便将该数据类型赋值给栈的模板类，以存放具有坐标属性的栈。demo中主要利用模板栈类实现了坐标类存入栈中、以及进制转换和浮点型类型数据等存放入栈中。

MyStack.h文件

#ifndef MYSTACK_H #define MYSTACK_H template <typename T> class MyStack { public: MyStack(int length); virtual ~MyStack(); int MyStackLen(); bool MyStackEmpty(); bool MyStackFull(); void ClearMyStack(); bool InsertElement(T element); bool DeleteElement(T &element); bool TraversalMyStack(); private: T* m_tMyStack; int m_iMyStackLength; int m_iMyStackCapacity; int m_iTos; }; #endif

MyStack.cpp

#include "MyStack.h" #include <iostream> using namespace std; template <typename T> MyStack<T>::MyStack(int length) { m_iMyStackCapacity = length; m_tMyStack = new T[m_iMyStackCapacity]; ClearMyStack(); } template <typename T> MyStack<T>::~MyStack() { delete []m_tMyStack; m_tMyStack = NULL; } template <typename T> int MyStack<T>::MyStackLen() { //cout << "此时的队列长度为：" << m_iMyStackLength << endl; return m_iMyStackLength; } template <typename T> bool MyStack<T>::MyStackEmpty() { return m_iTos == 0?true:false; } template <typename T> bool MyStack<T>::MyStackFull() { return m_iTos== m_iMyStackCapacity?true:false; } template <typename T> void MyStack<T>::ClearMyStack() { m_iMyStackLength = 0; m_iTos = 0; //cout << "已经成功清除栈内的所有元素！" << m_iMyStackLength << endl; } template <typename T> bool MyStack<T>::InsertElement(T element) { if(MyStackFull()) { cout << "该栈已满，不能再插入新的元素！" << endl; return false; } else { m_tMyStack[m_iTos] = element; m_iTos++; m_iMyStackLength++; return true; } } template <typename T> bool MyStack<T>::DeleteElement(T &element) { if(MyStackEmpty()) { //cout << "该栈为空，不能再删除元素！" << endl; return false; } else { m_iTos--; element = m_tMyStack[m_iTos]; m_iMyStackLength--; //cout << "已成功删除元素：" << element << endl; return true; } } template <typename T> bool MyStack<T>::TraversalMyStack() { if(MyStackEmpty()) { //cout << "该栈为空，不能遍历出任何元素！" << endl; return false; } else { //cout << "现将栈内的元素一一打印如下：" << endl; for(int i=(m_iTos-1);i>=0; i--) { cout << m_tMyStack[i]; } return true; } }

demo.cpp文件

#include <iostream> #include "MyStack.h" #include "MyStack.cpp" #include "Coordinate.h" using namespace std; /*定义几个会用到的常量*/ //#define BINARY 2 //#define OCTONARY 8 //#define HEXADECIMAL 16 /*进制转换函数的声明，定义在主函数后面*/ //void CalBinary(int n); //十进制转换为二进制的函数 //void CalOcronary(int n); //十进制转换为八进制的函数 //void CalHexadecimal(int n); //十进制转换为十六进制的函数 int main(void) { /*实现括号匹配问题的判断*/ MyStack<char> *pHaveStack = new MyStack<char>(100); //实例化一个栈类，将所有括号的左半部分存入 MyStack<char> *pNeedStack = new MyStack<char>(50); //实例化一个栈类，将需要匹配的右半部分括号一次存入 char strbrackets[] = "[][][][][]}"; //一个字符类型的数组，存放括号的排列 //cin >> strbrackets; char currentNeed = 0; //需要匹配的括号的右半部分 for (int i=0; i<strlen(strbrackets);i++) //遍历字符类型的数组，通过判断将需要的括号右半部分一次存入栈中，通过一一对比两个栈，将栈清空 { //自己的想法，未能实现原理功能 //pHaveStack->InsertElement(strbrackets[i]); //switch(strbrackets[i]) //{ //case "{": // currentNeed = "}"; // break; //case "[": // currentNeed = "]"; // break; //case "(": // currentNeed = ")"; // break; //case "}": // if (strbrackets[i-1] != "{") // { // cout << "该括号对不完美匹配！"; // } // else // { // char e =0; // pHaveStack->DeleteElement(e); // } // break; //case "]": // if (strbrackets[i-1] != "[") // { // cout << "该括号对不完美匹配！"; // } // else // { // char e =0; // pHaveStack->DeleteElement(e); // } // break; //case ")": // if (strbrackets[i-1] != "(") // { // cout << "该括号对不完美匹配！"; // } // else // { // char e =0; // pHaveStack->DeleteElement(e); // } // break; //default: // cout << "该括号对不完美匹配！"; //} //cout << strbrackets[i] <<endl; if (strbrackets[i] != currentNeed) //判断字符数组的元素是否等于所需的括号的右半部分 { switch(strbrackets[i]) { case '{': pHaveStack->InsertElement(strbrackets[i]); //将该字符数组的元素依次放入栈中 if (currentNeed !=0) { pNeedStack->InsertElement(currentNeed); //将需要的右半部分括号存入另外一个栈中 } currentNeed = '}'; //将需要的右半部分括号赋值给需要匹配的括号的右半部分 break; case '[': pHaveStack->InsertElement(strbrackets[i]); //将该字符数组的元素依次放入栈中 if (currentNeed !=0) { pNeedStack->InsertElement(currentNeed); } currentNeed = ']'; break; case '(': pHaveStack->InsertElement(strbrackets[i]); //将该字符数组的元素依次放入栈中 if (currentNeed !=0) { pNeedStack->InsertElement(currentNeed); } currentNeed = ')'; break; default: //如果不是括号的左半部分，那么这个字符跟任何左半部分括号都不匹配 cout << "字符串匹配不成功！" << endl; //break; system("pause"); return 0; } } else { char e; pHaveStack->DeleteElement(e); //将存放左半部分括号的栈顶出栈一个元素 if (!pNeedStack->DeleteElement(currentNeed)) //同时将存放需要的右半部分括号的栈出栈一个元素，判断是否真的出栈成功 { currentNeed = 0; //如果不成功，将需要的字符置空 } } } if (pNeedStack->MyStackEmpty()) { cout << "字符串匹配成功！" << endl; } else { cout << "字符串匹配不成功！" << endl; } delete []pHaveStack; pHaveStack = NULL; delete []pNeedStack; pNeedStack = NULL; /*实现把一个十进制的整数转换成二进制、八进制、十六进制*/ //cout << "请输入一个整数以及将要转换成的进制数（中间用空格隔开）：" << endl; //int N ,M; //cin >> N >> M; 判断需要把输入的十进制整数转换成为哪种进制 //if (BINARY == M) //{ // CalBinary(N); //转换成二进制 //} //else if (OCTONARY == M) //{ // CalOcronary(N); //转换成十进制 //} //else if (HEXADECIMAL == M) //{ // CalHexadecimal(N); //转换成十六进制 //} //else //{ // cout << "您输入的进制数不存在！"<<endl; //} /*实现利用栈存放坐标*/ //MyStack<Coordinate> stack(5); //实例化一个存放坐标类的大小是5的栈 //stack.InsertElement(Coordinate(1,2)); //往栈中插入新的元素 //stack.InsertElement(Coordinate(3,4)); //stack.InsertElement(Coordinate(5,6)); //stack.InsertElement(Coordinate(7,8)); //stack.TraversalMyStack(); //遍历整个栈的数据元素 //cout << endl; //Coordinate e(0,1); //stack.DeleteElement(e); //从栈中取出一个数据，并返回该数据的值 //cout << e << endl; //打印出从栈中取出的数据元素 //stack.TraversalMyStack(); //再次遍历栈中的数据元素，发现少了一个，而且是栈顶的元素 //cout << endl; //stack.MyStackLen(); //取出栈的长度 //cout << endl; //stack.ClearMyStack(); //清空栈中的所有元素 //stack.TraversalMyStack(); //再次遍历栈，发现栈为空 //cout << endl; //stack.InsertElement(0.1); //再次往栈中插入元素 //stack.InsertElement(1.2); //stack.TraversalMyStack(); //再次遍历栈，栈中的两个数据元素都打印了出来 /*实现利用栈存放浮点型数据*/ //MyStack<double> stack(5); //实例化一个存放浮点型数据的大小是5的栈 //stack.InsertElement(11.2); //往栈中插入新的元素 //stack.InsertElement(12.3); //stack.InsertElement(13.4); //stack.InsertElement(14.5); //stack.InsertElement(15.6); //stack.TraversalMyStack(); //遍历整个栈的数据元素 //cout << endl; //double e =0.1; //stack.DeleteElement(e); //从栈中取出一个数据，并返回该数据的值 //cout << e << endl; //打印出从栈中取出的数据元素 //stack.TraversalMyStack(); //再次遍历栈中的数据元素，发现少了一个，而且是栈顶的元素 //cout << endl; //stack.MyStackLen(); //取出栈的长度 //cout << endl; //stack.ClearMyStack(); //清空栈中的所有元素 //stack.TraversalMyStack(); //再次遍历栈，发现栈为空 //cout << endl; //stack.InsertElement(0.1); //再次往栈中插入元素 //stack.InsertElement(1.2); //stack.TraversalMyStack(); //再次遍历栈，栈中的两个数据元素都打印了出来 system("pause"); return 0; } /*十进制整数转换成二进制数的函数*/ //void CalBinary(int n) //{ // MyStack<int> stack(20); // while(n != 0) //循环进行求余操作，将余数存入栈中 // { // int mod = n % BINARY; //对十进制整数n进行求余操作 // stack.InsertElement(mod); //将余数存入栈中 // n = n / BINARY; //获得短除的商的值，循环进行求余操作 // } // cout << "该整数的二进制数为：" << endl; // stack.TraversalMyStack(); //从栈顶遍历栈中的数据元素，连续打印出来便是该十进制整数的二进制数 // cout << endl; //} /*十进制转换成八进制数的函数*/ //void CalOcronary(int n) //{ // MyStack<int> stack(20); // while(n != 0) //循环进行求余操作，将余数存入栈中 // { // int mod = n % OCTONARY; //对十进制整数n进行求余操作 // stack.InsertElement(mod); //将余数存入栈中 // n = n / OCTONARY; //获得短除的商的值，循环进行求余操作 // } // cout << "该整数的八进制数为：" << endl; // stack.TraversalMyStack(); //从栈顶遍历栈中的数据元素，连续打印出来便是该十进制整数的八进制数 // cout << endl; //} /*十进制转换成十六进制数的函数*/ //void CalHexadecimal(int n) //{ // MyStack<int> stack(20); // char num[] = "0123456789ABCDEF"; //声明一个字符类数组，其中存放了十六进制数的所有要用的字符 // while(n != 0) // { // int mod = n % HEXADECIMAL; //对十进制整数n进行求余操作 // stack.InsertElement(mod); //将余数存入栈中 // n = n / HEXADECIMAL; //获得短除的商的值，循环进行求余操作 // } // cout << "该整数的十六进制数为：" << endl; // int j = stack.MyStackLen(); //取到当前余数在栈中存放的个数，即栈的长度 // for(int i=0;i < j ;i++) // { // int element=0; // stack.DeleteElement(element); //从栈顶一个一个取出数据元素 // cout << num[element]; //将取出的数据元素的值作为字符类数组的下标一一打印出来，记得中间不要有空格或者换行 // } // cout << endl; //}

Coordinate.h文件：主要实现了坐标类和<<操作符重载，而且是友元函数实现的操作符重载。

#ifndef COORDINATE_H #define COORDINATE_H #include <iostream> using namespace std; class Coordinate { public: Coordinate(int x=0, int y=0); //Coordinate(int x, int y); void printCoordinate(); friend ostream &operator<<(ostream &output,Coordinate &coor); private: int m_iX; int m_iY; }; #endif

Coordinate.cpp文件

#include "Coordinate.h" #include <iostream> using namespace std; Coordinate::Coordinate(int x, int y) { m_iX = x; m_iY = y; } void Coordinate::printCoordinate() { cout << "(" << m_iX << "," << m_iY << ")" <<endl; } ostream &operator<<(ostream &output,Coordinate &coor) { output << "(" << coor.m_iX << "," << coor.m_iY << ")"; return output; }