栈的简单应用.doc

1、/头文件“stack.h”#ifndef STACK_H#define STACK_Htemplate class Nodepublic:Node();Node(const TypeNode();/private:Type Date;Node *Next;template class Stackpublic:Stack();/Head-Date不可知Stack();void Puah_Head(const Nodevoid Pop_Head();Typevoid MakeEmpty();void Travel();bool IsEmpty();/private:Node *Head;templ

2、ate Stack:Stack()Head=new Node;templatevoid Stack:MakeEmpty()Node *cur=Head;for(;Head-Next!=NULL;) cur=Head-Next;Head-Next=cur-Next;delete cur;template Stack:Stack()if(Head-Next!=NULL) MakeEmpty();delete Head;template void Stack:Puah_Head(const Nodeif(Head-Next!=NULL) cur-Next=Head-Next;Head-Next=cu

3、r;template void Stack:Pop_Head()Node* cur=new Node;if(Head-Next=NULL)return;cur=Head-Next;Head-Next=cur-Next;delete cur;template Typereturn Head-Next-Date;template void Stack:Travel()Node* cur=new Node;cur=Head;for(;cur-Next!=NULL;)cur=cur-Next;coutDatebool Stack:IsEmpty()if(Head-Next=NULL) return t

4、rue;return false;template Node:Node():Next(NULL);template Node:Node(const Typetemplate Node:Node();#endif/主程序 cpp 文件“main.cpp”#include#include#include “string“#include“stack.h“using namespace std;char* Change(int number,int a);/把number转换为a进制的一个数； string PostFix(string exp);/把一个中缀改为后缀；int FindNumber(

5、char a);/把字符转换为数字int Post(string postfixexp);/计算后缀表达式char* n;int ShuRu(string ,int/从第i个字符开始，将其到空格之前的所有字符换算成intvoid main() /字符串格式 每个操作数或者操作符号后面加一个空格，最后一个操作符号可以不加/数据为intstring a=“3424 665 + 542 / 85 * 544 - 7655 +“;int b=Post(a);coutinfixexp;)cout* NumberStack=new Stack;int i=0;int number;int first;in

6、t last;for(;postfixexpi!=32;)int ch;ch=FindNumber(postfixexpi);switch(ch)case 0:number=ShuRu(postfixexp,i);NumberStack-Puah_Head(number);break;case 2:first=NumberStack-Top();NumberStack-Pop_Head();last=NumberStack-Top();NumberStack-Pop_Head();number=first+last;NumberStack-Puah_Head(number);i+;break;

7、case 3:first=NumberStack-Top();NumberStack-Pop_Head();last=NumberStack-Top();NumberStack-Pop_Head();number=last-first;NumberStack-Puah_Head(number);i+;break;case 4:first=NumberStack-Top();NumberStack-Pop_Head();last=NumberStack-Top();NumberStack-Pop_Head();number=first*last;NumberStack-Puah_Head(num

8、ber);i+;break;case 5:first=NumberStack-Top();NumberStack-Pop_Head();last=NumberStack-Top();NumberStack-Pop_Head();number=last/first;NumberStack-Puah_Head(number);i+;break;i+;number=NumberStack-Top();return number;int ShuRu(string a,intint num=0;int k=0;int jie=1;for(;ai!=32;i+,k+)bk=ai-48;jie=jie*10

9、;bk=10;for(int j=0;bj* m=new Stack;int zheng=1;n=new char100;char jinzhi=“0123456789ABCDEF“;/coutPuah_Head(jinzhinumber%a);for(zheng=0;m-Head-Next!=NULL;zheng+)nzheng=(*m).Top();m-Pop_Head();nzheng=0;return n;string PostFix(string exp)bool flag=true;int TokenNumber,TopTokenNumber;Stack* OpStack=new

10、Stack;string PostFixExp;string Op=“0(+-*/)“;string Blank=“ “;int j=exp.length();if(FindNumber(exp0)1) flag=false;for(int i=0;iPuah_Head(expi);break;case 6: for(;)if(OpStack-IsEmpty() flag=false;break;TopTokenNumber=FindNumber(OpStack-Top();OpStack-Pop_Head();if(TopTokenNumber=1) break;PostFixExp.app

11、end(Blank+OpTopTokenNumber);break;case 2:case 3:case 4:case 5:for(;)if(i1) flag=false;break;if(OpStack-IsEmpty()|(TokenNumber/2)(FindNumber(OpStack-Top()/2) OpStack-Puah_Head(OpTokenNumber);break;else TopTokenNumber=FindNumber(OpStack-Top();OpStack-Pop_Head();PostFixExp.append(Blank+OpTopTokenNumber);break;case 0:PostFixExp.append(Blank+expi);for(;iIsEmpty();)TopTokenNumber=FindNumber(OpStack-Top();OpStack-Pop_Head();if(TopTokenNumber=1)flag=false;break;elsePostFixExp.append(Blank+OpTopTokenNumber);if(!flag)PostFixExp=“输入错误“;return PostFixExp;