//栈的类定义 const int maxSize=50; enum bool{false,true}; template<class T> class Stack { public: Stack(){}; virtual void Push(const T&x)=0;//新元素x进栈 virtual bool Pop(T&x)=0; //栈顶元素出栈，由x返回 virtual bool getTop(T&x)const=0;//读取栈顶元素，由x返回 virtual bool IsEmpty()const=0;//判断栈空 virtual bool IsFull()const=0;//判断栈满 virtual int getSize()const=0;//计算栈中元素的个数 } //顺序栈类的定义 #include<assert.h> #include<iostream.h> #include"stack.h" const int stackIncreament=20;//栈溢出时扩展空间的增量 template<class T> class SeqStack:public Stack<T> { public: SeqStack(int sz=50);//建立一个空栈 ~SeqStack(){delete[]elements;}//析构函数 void Push(const T& x) bool Pop(T &x);//如果栈是空的则返回flase bool getTop(T& x);//如果空则返回false bool IsEmpty()const{return (top==-1)?true:false;} bool IsFull()const{return (top==maxSize-1)?true:false;} int getSize()const (return top+1;) void MakeEmpty(){top=-1;} friend ostream& operator << (ostream& os,SeqStack<T>& s); //输出栈中元素的重载操作 private: T *elements; int top; int maxSize; void overflowProcess();//栈溢出的处理 }; //顺序栈的构造函数 template<class T> SeqStack<T>::SeqStack(int sz):top(-1),maxSize(sz) { elements=new T[maxSize]; assert(elements!=NULL);//断言机制，若为真程序则继续运行下面的 } //扩充栈的存储空间 template<class T> void SeqStack<T>::overflowProcess() { T *newarray=new T[maxSize+stackIncreament]; if(newArray==NULL) { cerr<<"存储分配失败!"<<endl; exit(1); } for(int i=0;i<=top;i++) newArray[i]=element[i]; maxSize=maxSize+stackIncreament; delete []elements; elements=newArray; } template<class T> void SeqStack<T>::Push(const T& x) { if(IsFull()==true) overflowProcess(); elements[++top]=x; } template<class T> bool SeqStack<T>::Pop(T& x) { if(IsEmpty()==true) return false; x=elements[top--]; return true; } template<class T> bool Seqstack<T>::getTop(T& x) { if(IsEmpty()==true) return false; x=elements[top]; return true; } //输出栈中元素的重载操作 template<class T> ostream& operator << (ostream& os,SeqStack<T>& s) { os<<"top="<<s.top<<endl; for(int i=0;i<=s.top;i++) { os<<i<<":"<<s.elements[i]<<endl; } return os; }; //栈的空间共享 双栈的插入和删除 bool push(DualStack& DS,T x,int d) //在双栈中扎入元素x，d=0插在第0号栈，d！=0插在第1号栈 { if(DS.t[0]+1==DS.t[1]) return false;//栈满了 if(d==0) DS.t[0]++; else DS.t[1]--; DS.Vector[DS.t[d]]=x; return true; }; bool Pop(DualStack& DS,T& x,int d) //从双栈中推出栈顶元素，通过x返回。d=0从第0号栈推栈，d!=0从第1号栈退栈 { if(DS.t[d]==DS.b[d]) return false; x=DS.Vector[DS.t[d]]; if(d==0) DS.t[0]--; else DS.t[1]++; return true; }; //链式栈 #include<iostream.h> #include"LinkedList.h" #include"stack.h" template<class T> class LinkedStack:public Stack<T> //链式栈类定义 { public: LinkedStack():top(NULL){} //构造函数，置空栈 ~LinkedStack(){makeEmpty();} //析构函数 void Push(const T&x); bool Pop(T&x); bool getTop(T& x); bool IsEmpty()const{return (top==NULL)?true:false;} int getSize()const; void makeEmpty(); friend ostream&operator << (ostream& os,SeqStack<T>& s); //输出栈中元素的重载操作<< private: LinkNode<T>*top; //栈顶指针，即链头指针 }; template<class T> LinkedStack<T>makeEmpty() { //逐次删去链式栈中的元素直至栈顶指针为空 LinkNode<T>*p; while(top!=NULL) { p=top;top=top->link;delete p; } }; template<class T> void LinkedStack<T>::Push(const T& x) { top=new LinkNode<T>(x,top);//创建新节点的link为top assert(top!=NULL); }; template<class T> bool LinkedStack<T>::Pop(T& x) { if(IsEmpty()) return false; LinkNode<T>*p=top; top=top->link; x=p->data;delete p; return true; }; template<class T> int LinkStack<T>::getTop(T& x)const { if(IsEmpty()) return false; x=top->data; return true; } template<class T> int LinkedStack<T>::getSize()const { LinkNode<T>*p=top;int k=0; while(top!=NULL) { top=top->link; k++; } return k; }; //输出栈中元素的重载操作 template<class T> ostream& operator << (ostream& os,LinkedStack<T>& s) { os<<"栈中元素的个数="<<s.getSize()<<endl; LinkNode<T>*p=S.top();int i=0; while(p!=NULL) { os<<++i<<":"<<p->data<<endl; p=p->link; } return os; }; /* 如果同时使用n个链式栈，其头指针数组可以用一下方式定义： LinkNode<T>*s=new LinkNode<T>[n]; */
//栈的应用---括号匹配 #include<iostream.h> #include<string.h> #include<stdio.h> #include"stack.h" const int maxLength=100; void PrintMatchedPairs(char *expression) { Stack<int>s(maxLength); int j,length=strlen(expression); for(int i=1;i<length;i++) { if(expression[i-1]=='(') s.Push(i); else if(expression[i-1]==')') { if(s.Pop(j))cout<<j<<"与"<<i<<"匹配"<<endl; else cout<<"没有与第"<<i<<"个右括号匹配的左括号！"<<endl; } } while(s.IsEmpty()==false) { s.Pop(j); cout<<"没有与第"<<j<<"个左括号相匹配的右括号!"<<endl; } } //栈的应用--表达式计算 #include<math.h> #include<stack.h> #include<iostream.h> class Calculator { //模拟一个简单的计算器。此计算机对后缀表达式求值。 public: Calculator(int sz):s(sz){} void Run(); void Clear(); private: Stack<double>s; void AddOperand(double value); //进操作数栈 bool get2Operands(double& left,double& right);//从栈中退出两个操作数 void DoOperator(char op); //形成运算指令，进行计算 }; void Calculator::DoOperator(char op) { //私有函数：取俩个操作数，根据操作符op形成运算指令并计算 double left,right,vlaue;int result; result=Get2Operands(left,right); if(result==true) { switch(op) { case'+':value=left+right;s.Push(value);break; case'-':value=left-right;s.Push(value);break; case'*':value=left*right;s.Push(value);break; case'/':if(right==0.0) { cerr<<"Divide by 0!"<<endl; Clear(); }else{value=left/right;s.Push(value);} break; } }else Clear(); }; bool Calculator::Get2Operands(double& left,double& right) { //私有函数：从操作数栈中取出两个操作数。 if(s.IsEmpty()==true) { cerr<<"缺少右操作数！"<<endl; return false; } s.Pop(right); if(s.IsEmpty()==true) { cerr<<"缺少左操作数!"<<endl; return false; } s.Pop(left); return true; }; void Calculator::AddOperand(double value) { s.Push(value); }; void Calculator::Run() { //读取一个字符串并求一个后缀表达式的值。以字符'#'结束。 char ch;double newOperand; while(cin>>ch,ch!='#') { switch(ch) { case'+':case'-':case'*':case'/':DoOpertor(ch);break; default:cin.putback(ch);//将字符放回输入流 cin>>newOperand; AddOperand(newOperand); //将操作数放入栈中 } } }; void Calculator::Clear() { S.makeEmpty(); }; //将中缀表达式转换为后缀表达式的算法 void postfix(expression e) { /* 把中缀表示e转换成后缀表示并输出，设定e中最后一个符号是'#'，而且'#'一开始就放在 栈s的栈底。 */ Stack<char>s;//定义栈的对象s,其元素为字符。 char ch='#',ch1,op; s.Push(ch);cin.get(ch); while(s.IsEmpty()==false&&ch!='#') { if(isdigit(ch)) {cout<<ch;cin.get(ch);}//是操作数，输出 else { s.getTop(ch1);//从栈顶取出操作符ch1; if(isp(ch1)<icp(ch)) //新输入操作符ch优先级高 { s.Push(ch);cin.Get(ch);//进栈，读取下一个字符 }else if(isp(ch1)>icp(ch)) //新输入操作符优先级低 { s.Pop(op);cout<<op; //退栈并输出 } else { s.Pop(op); //输入操作符优先级等于栈顶优先级 if(op=='(') cin.Get(ch); } } } }