栈是计算机术语中比较重要的概念,实质上栈就是一段内存区域,但是栈满足一定的特性,那就是只有一个口,具有先入后出的特性,这种特性在计算机中有很广泛的运用。其中几个典型的运用如下:判断平衡符号,实现表达式的求值(也就是中缀表达式转后缀表达式的问题以及后缀表达式求值问题),在路径探索中实现路径的保存也可以说是栈的经典运用之一。具体的问题具体分析,只要满足先入后出特性的问题都能找到现成的数据结构---栈。
本文采用C++中的vector实现栈结构,然后利用栈实现判断平衡符号,实现中缀表达式到后缀表达式的转换,并依据栈实现简单的整数加减乘除运算。
首先栈的实现,由于在C++中采用了vector来代替原始的数组操作,这种比较方便的容器能较好的实现数组的功能,而且在实际的计算机里也是采用连续的存储空间作为栈空间的,因此选择vector。主要实现三个操作,push、pop以及为空判断。
补充:栈也可以采用单向链表实现,在表顶端插入元素来实现push,通过删除表顶端元素实现pop。top操作访问表顶。
基本的形式如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#ifndef __MYSTACK_H_H_ #define __MYSTACK_H_H_ #include <vector> using namespace std; template<typename Object> class MyStack{ public: MyStack(){} ~MyStack(){objects.swap(vector<Objects>()) ; } void push(const Object &x) { objects.push_back(x); } const Object &pop(){ int len; if(!isempty()){ len = objects.size(); Object top = objects[len - 1]; objects.pop_back(); return top;//返回栈顶元素 } } bool isempty()const{ return (objects.size() == 0); } int size(){ return objects.size(); } private: vector<Object> objects; }; #endif |
栈的链表实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#ifndef __MYSTACK1_H_H_ #define __MYSTACK1_H_H_ #include <vector> #include <cassert> using namespace std; template<typename T> class MyStack1; template<typename T> class Node{ T data; Node<T> * next;//嵌套,只有指针类型才允许 //C/C++允许结构成员是结构自身的指针类型,通过指针访问与自身同类型的结构变量; //结构成员不能是结构自身类型的变量,会导致一个无穷递归的定义。 public: Node(T mydata = 0, Node<T>*mynext = NULL){ data = mydata; next = mynext; } friend class MyStack1 < T > ; }; template<typename T> class MyStack1{ Node<T> *top;//链头 public: MyStack1(){ top = NULL;} //构造函数,使栈顶top也就是链表head为NULL ~MyStack1(); void Push(const T&mydata);//压栈 T Pop(); T GetTop(); void MakeEmpty(); bool IsEmpty(){ return top == NULL; } }; template <typename T> MyStack1<T>::~MyStack1() { MakeEmpty(); } template <typename T> void MyStack1<T>::MakeEmpty() { Node<T> * temp; while (top != NULL){ temp = top; top = top->next; delete temp; } } //链栈向前生成,新结点在链头找 template <typename T> void MyStack1<T>::Push(const T& mydata){ top = new Node<T>(mydata, top);//添加一个新的结点 } template<typename T> T MyStack1<T>::Pop(){ assert(!IsEmpty()); Node<T> *temp = top; T topdata = temp->data; top = top->next; delete temp; return topdata;//返回栈顶元素 } template<typename T>T MyStack1<T>::GetTop(){ assert(!IsEmpty()); return top->data; } #endif |
1 2 3 4 5 6 7 |
MyStack1<char> mystack1; string src = "a+b*c+(d*e+f)*g"; string::size_type len= src.size(); for (string::size_type i = 0; i < len; i++){ mystack1.Push(src[i]);//可以观察其添加过程,向前生成链表方法 } char topop = mystack1.Pop();//弹出栈顶元素 |
典型应用一:当函数调用时,系统会做以下工作:
1)建立栈空间
2)保护现场。将当前主调函数的执行状态和返回地址保存在栈中。
3)为被调函数中的局部变量(包括形参)分配栈空间,并将实参传递给形参。
4)执行被调函数。
5)释放被调函数的所有局部变量栈空间。
6)恢复现场。取出主调函数的执行状态及返回地址,释放栈空间。
典型应用二:符号的平衡问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include "stdafx.h" #include "Mystack.h" #include <string> #include <iostream> using namespace std; bool isBalance(const string &str){ string::size_type len = str.size(); MyStack<char> mystack; for (string::size_type i = 0; i < len; i++){ //如果遇到对称符号的左边部分,则将其压入栈中 if (str[i] == '[' || str[i] == '{' || str[i] == '(' || str[i] == '<'){ mystack.push(str[i]); } //当遇到对称符号的右边部分,则弹出栈中的一个对象,实现比对 if (str[i] == ']' || str[i] == '}' || str[i] == ')' || str[i] == '>'){ /*如果栈中没有对象,则说明不平衡*/ if (mystack.isempty()){ cout << "the string is Unbalanced" << endl; return false; } switch (str[i]){ case ']':{ if ('[' != mystack.pop()){ cout << "the string is Unbalanced" << endl; return false; } break; } case ')':{ if ('(' != mystack.pop()){ cout << "the string is Unbalanced" << endl; return false; } break; } case '}':{ if ('{' != mystack.pop()){ cout << "the string is Unbalanced" << endl; return false; } break; } case '>':{ if ('<' != mystack.pop()){ cout << "the string is Unbalanced" << endl; return false; } break; } //非对称字符 default:break; } } } //当字符串读完以后,如果所有的符号都是平衡的,栈中此时应该就是为空, //通过判断栈中是否为空,说明字符串是否是符号平衡的。 if (mystack.isempty()){ cout << "string is balanced!!" << endl; return true; } else{ cout << mystack.pop() << " " << "Unblance string!!" << endl; return false; } } int _tmain(int argc, _TCHAR* argv[]){ string a = "{(nihaoma)}"; bool isbalanced = isBalance(a); system("pause"); return 0; } |
典型应用三:表达式的求值问题
表达式的求值问题主要设计到操作符的优先级问题,比如()、*/、+-这几种符号的优先级是不一样的,其中括号的优先级最高,乘除其次,加减最低,我们通常看到的表达式都是中缀表达式。
1 2 |
中缀表达式 a+b*c+(d*e+f)*g 后缀表达式 a b c * + d e *f + g * + |
转换规则:当读到一个操作数的时候,立即将它放到输出中。操作符不立即输出,而是存放在栈中。当遇到左括号时(有最高优先级),放入栈中。如果遇到右括号,将栈元素弹出,将符号写出直到遇到一个对应的左括号(被弹出而不输出)。
如果遇到其他的符号,那么从栈中弹出栈元素直到发现优先级更低的元素为止。当输入为空时,将栈中元素全部弹出并置空。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
bool midtolast(string &src, string &dst){ string::size_type len = src.size(); char temp = '\0'; MyStack<char> mystack; for (string::size_type i = 0; i < len; i++){ switch (src[i]){ case '(':{ mystack.push(src[i]); break; } case ')':{ if (mystack.isempty()){ return false; } /*非空,弹出对象*/ temp = mystack.pop(); while ('(' != temp){ dst += temp;//保存并输出到后缀表达式 if (mystack.isempty()) break; temp = mystack.pop(); } break; } //从栈中弹出栈元素直到发现优先级更低的元素为止 case'*': case'/': { /*判断非空的栈,为空则直接入栈即可*/ if (!mystack.isempty()) { temp = mystack.pop(); while (temp != '+'&&temp != '-'&&temp != '('){ dst += temp; if (mystack.isempty()){//异常处理 temp = '\0'; break; } temp = mystack.pop(); } } if (temp == '+' || temp == '-' || temp == '('){ mystack.push(temp); } /*将当前操作符压栈*/ mystack.push(src[i]); break; } case'-': case'+':{ /*判断非空的栈,加减操作的优先级最低,因此需要弹出所有非左括号的操作符*/ if (!mystack.isempty()){ temp = mystack.pop(); while (temp != '('){ dst += temp; if (mystack.isempty()){ temp = '0'; break;//跳到if (temp == '(') } temp = mystack.pop(); } } if (temp == '('){ mystack.push(temp); } /*将当前操作符压栈*/ mystack.push(src[i]); break; } default:{ /*针对字符而言直接输出到后缀表达式*/ dst += src[i]; break; } } } while (!mystack.isempty()){ temp = mystack.pop(); dst += temp; } return true; } int _tmain(int argc, _TCHAR* argv[]){ string src = "a+b*c+(d*e+f)*g"; string dst; midtolast(src, dst); system("pause"); return 0; } |