c++栈的基础应用，括号匹配、逆波兰表达式求值

//#include
//#include
//#include
//#include
//using namespace std;
//
//template
//class Node
//{
//public:
//    Node(){}
//    Node(T data, Node* next)  //构造函数初始化每一节点
//    {
//        this->data = data;  //当前节点的数据域
//        this->next = next;  //当前节点的指针域，存储指向下一节点的指针
//    }
//    ~Node() {}
//    T data;      //当前节点的数据域
//    Node* next;    //指针域，下一节点的指针
//};
//
//template
//class Stack
//{
//private:
//    Node* head;    //头结点
//    int length;    //链表长度(当前元素个数)
//public:
//    Stack();
//    ~Stack();
//    bool IsEmpty();//判断栈是否为空
//    int GetSize(); //获取当前栈中的元素个数
//    void push(T elm); //向栈中压入元素
//    T pop();  //元素出栈，弹出栈顶元素
//    void for_each(); //遍历栈
//    T top();  //h获取出栈顶元素
//};
//
链栈的功能测试
//void TestStack()
//{
//    Stacks;
//    cout << "栈是否为空：" << s.IsEmpty() << " " << "栈中的元素个数为：" << s.GetSize() << endl;
//    for (int i = 1; i <= 10; i++)
//    {
//        string str[10] = { "1","2","3","4" ,"5","6" ,"7","8" ,"9","10" };
//        s.push(str[i - 1]);
//    }
//    cout << "栈是否为空：" << s.IsEmpty() << " " << "栈中的元素个数为：" << s.GetSize() << endl;
//    s.for_each();
//    for (int i = 1; i <= 3; i++)
//    {
//        s.pop();
//    }
//    cout << "栈是否为空：" << s.IsEmpty() << " " << "栈中的元素个数为：" << s.GetSize() << endl;
//    s.for_each();
//    return;
//}
//
案例括号(英文)匹配问题
//bool BracketMatch(string str)
//{
//    //1.创建栈对象
//    Stacks;
//    //2.遍历字符串
//    for (int i = 0; i < str.size(); i++)
//    {
//        //3.判断是左括号还是右括号，并出入栈
//        if (str[i] == '{' || str[i] == '[' || str[i] == '(')//更多类型的匹配加入即可
//        {
//            s.push(str[i]);
//        }
//        else if(str[i] == '}' || str[i] == ')' || str[i] == ']')//更多类型的匹配加入即可
//        {
//            if (s.IsEmpty())return false;
//            else
//            {
//                
//                if (str[i] == '}' && s.top() != '{')return false;
//                else if (str[i] == ']' && s.top() != '[') return false;
//                else if (str[i] == ')' && s.top() != '(') return false;
//                //更多类型的匹配加入即可
//                else
//                {
//                    s.pop();
//                }
//            }
//        }
//        
//    }
//    //4.判断栈中是否还有剩余括号
//    if (s.GetSize() == 0)return true;
//    else return false;
//}
案例逆波兰表达式
//void GetReBoLan()
//{
//    //生成逆波兰表达式
//
//}
//int CaculateBoLan(string notation)
//{
//    //得到逆波兰表达式结果
//    //1.创建栈对象
//    Stackoprands;
//    //2.遍历字符串
//    for (int i = 0; i < notation.size(); i++)//4判断是否到字符串结尾
//    {
//        int o1=0;
//        int o2=0;
//        int result=0;
//        //3.判断是运算符还是操作数，并出入栈
//        switch (notation[i])
//        {
//        case '+': {
//            o1 = oprands.pop();
//            o2 = oprands.pop();
//            result = o2 + o1;
//            oprands.push(result); // 3.1计算结果将结果入栈
//            break;
//        }
//        case '-': {
//            o1 = oprands.pop();
//            o2 = oprands.pop();
//            result = o2 - o1;
//            oprands.push(result);
//            break;
//        }
//        case '*': {
//            o1 = oprands.pop();
//            o2 = oprands.pop();
//            result = o2 * o1;
//            oprands.push(result);
//            break;
//        }
//        case '/': {
//            o1 = oprands.pop();
//            o2 = oprands.pop();
//            result = o2 / o1;
//            oprands.push(result);
//            break;
//        }
//        default:oprands.push((notation[i])-48);
//            break;
//        }
//    }
//    //5弹出最终结果
//    int tmp = oprands.pop();
//    return tmp;
//}
//int main(int agrc, char* agrv[])
//{
//    //TestStack();
//    
//    string notation = "365-8*+";
//    cout << CaculateBoLan(notation) << endl; 
//    return 0;
//}
//
//template
//Stack::Stack()
//{
//    this->head = new Node;
//    this->head->next = NULL;
//    this->length = 0;
//}
//template
//Stack::~Stack()
//{
//    delete this->head; //删除头结点
//    this->head = NULL; //指向空
//}
判断栈是否为空
//template
//bool Stack::IsEmpty()//判断栈是否为空
//{
//    if (this->length == 0)return true;
//    else return false;
//}
获取当前栈中的元素个数
//template
//int Stack::GetSize() //获取当前栈中的元素个数
//{
//    return this->length;
//}
向栈中压入元素,头插
//template
//void Stack::push(T elm) //向栈中压入元素
//{
//    //保留当前头结点的下一个结点的指针，即当前指向栈顶结点的指针
//    Node* CurrTop = this->head->next;
//    //创建新的结点并压入栈中，新结点为新的栈顶结点，他的next指向原先的栈顶结点
//    Node* NewTop = new Node(elm, CurrTop);
//    //更新头结点的指向，使其指向新的栈顶结点
//    this->head->next = NewTop;
//    //栈内元素结点数加 1 。
//    this->length++;
//}
元素出栈，弹出栈顶元素 ，头删
//template
//T Stack::pop()  //元素出栈，弹出栈顶元素
//{
//    //保留当前头结点的下一个结点的指针，即当前指向栈顶结点的指针
//    Node* CurrTop = this->head->next;
//    //如果已是空栈返回空值
//    if (CurrTop == NULL)return this->head->data;
//    //将头结点指向的栈顶结点的指针，直接指向原先栈顶结点的下一个结点。
//    this->head->next = CurrTop->next;
//    //元素结点减 1。
//    this->length--;
//    //返回出栈的元素结点的数据
//    return CurrTop->data;
//}
遍历栈
//template
//void Stack::for_each() //遍历栈
//{
//    Node *curr=this->head;  //两个指针指向同一区域,可通过new新内存，重载构造函数解决方可正常释放内存
//    while (curr->next!=NULL)   //如果指向的下一结点不为空
//    {
//        cout << curr->next->data << "  ";      //打印下一结点的数据
//        curr = curr->next;      //指针往后移
//    }
//    cout << endl;
//}
//
h获取出栈顶元素
//template
//T Stack::top()  //h获取出栈顶元素
//{
//    return this->head->next->data;
//}