栈的简单应用.doc

/头文件“stack.h”#ifndef STACK_H #define STACK_H template class Nodepublic:Node();Node(const Type& date);Node();/private:Type Date;Node *Next;template class Stackpublic:Stack();/Head-Date不可知Stack();void Puah_Head(const Node& node);void Pop_Head();Type& Top();void MakeEmpty();void Travel();bool IsEmpty();/private:Node *Head;template 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 Node& node) Node* cur=new Node(node); if(Head-Next!=NULL) cur-Next=Head-Next; Head-Next=cur;template void Stack:Pop_Head()Node* cur=new Node;if(Head-Next=NULL) return;cur=Head-Next;Head-Next=cur-Next;delete cur;template Type& Stack:Top() if(Head-Next=NULL) coutStack为空Date;return Head-Next-Date;template void Stack:Travel()Node* cur=new Node;cur=Head;for(;cur-Next!=NULL;)cur=cur-Next;coutDateendl;template bool Stack:IsEmpty()if(Head-Next=NULL) return true;return false;template Node:Node():Next(NULL) ;template Node:Node(const Type& date):Date(date),Next(NULL) ;template Node:Node() ;#endif/主程序cpp文件“main.cpp”#include#include#include string#includestack.husing namespace std;char* Change(int number,int a);/把number转换为a进制的一个数； string PostFix(string exp);/把一个中缀改为后缀；int FindNumber(char a);/把字符转换为数字int Post(string postfixexp);/计算后缀表达式char* n;int ShuRu(string ,int& i);/从第i个字符开始，将其到空格之前的所有字符换算成intvoid main() /字符串格式 每个操作数或者操作符号后面加一个空格，最后一个操作符号可以不加/数据为intstring a=3424 665 + 542 / 85 * 544 - 7655 +;int b=Post(a);couta的计算结果为bendl;/*char* a=Change(15,16); /15转化为16进制coutaendl;*/*string infixexp; /中缀转换为后缀，输入eof停止cout连续输入直到输入eof，即ctrl+zendl;cout操作符仅限 （ + - * / ）infixexp;) coutPostfix expression isPostFix(infixexp)endl; */int Post(string postfixexp) postfixexp.append(2, ); Stack* NumberStack=new Stack; int i=0; int number; int first; int 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;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(number);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,int&i)int b10;int num=0;int k=0;int jie=1;for(;ai!=32;i+,k+) bk=ai-48; jie=jie*10;bk=10;for(int j=0;bj10;j+) num=num+bj*jie/10; jie=jie/10; return num;int FindNumber(char a)if(a=() return 1;if(a=+) return 2;if(a=-) return 3;if(a=*) return 4;if(a=/) return 5;if(a=) return 6;return 0;char* Change(int number,int a)Stack* m=new Stack;int zheng=1;n=new char100;char jinzhi=0123456789ABCDEF;/coutnumber转换为aPuah_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 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.append(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);