栈的简单应用.doc

//头文件“stack.h”

#ifndef STACK_H
#define STACK_H

template <class Type>
class Node
{
public:
Node();
Node(const Type& date);
~Node();
//private:
Type Date;
Node<Type> *Next;
};
template <class Type>
class Stack
{
public:
Stack();//Head->Date不可知
~Stack();
void Puah_Head(const Node<Type>& node);
void Pop_Head();
Type& Top();

void MakeEmpty();
void Travel();
bool IsEmpty();
//private:
Node<Type> *Head;
};

template <class Type>
Stack<Type>::Stack()
{
Head=new Node<Type>;
}

template<class Type>
void Stack<Type>::MakeEmpty()
{
Node<Type> *cur=Head;
for(;Head->Next!=NULL;)
{
cur=Head->Next;
Head->Next=cur->Next;
delete cur;
}
}

template <class Type>
Stack<Type>::~Stack()
{
if(Head->Next!=NULL) MakeEmpty();

delete Head;
}

template <class Type>
void Stack<Type>::Puah_Head(const Node<Type>& node)
{
Node<Type>* cur=new Node<Type>(node);

if(Head->Next!=NULL) cur->Next=Head->Next;
Head->Next=cur;
}

template <class Type>
void Stack<Type>::Pop_Head()\
{
Node<Type>* cur=new Node<Type>;
if(Head->Next==NULL)
return;
cur=Head->Next;
Head->Next=cur->Next;
delete cur;
}

template <class Type>
Type& Stack<Type>::Top()
{
if(Head->Next==NULL)
{
cout<<"Stack为空"<<endl;
return Head->Date;
}
return Head->Next->Date;
}

template <class Type>
void Stack<Type>::Travel()
{
Node<Type>* cur=new Node<Type>;

cur=Head;
for(;cur->Next!=NULL;)
{
cur=cur->Next;
cout<<cur->Date<<endl;
}

}

template <class Type>
bool Stack<Type>::IsEmpty()
{
if(Head->Next==NULL) return true;
return false;
}
template <class Type>
Node<Type>::Node():Next(NULL)
{
;
}

template <class Type>
Node<Type>::Node(const Type& date):Date(date),Next(NULL)
{
;
}

template <class Type>
Node<Type>::~Node()
{
;
}

#endif

//主程序cpp文件“main.cpp”

#include<iostream>
#include<string>
#include "string"
#include"stack.h"
using 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个字符开始，将其到空格之前的所有字符换算成int

void main()
{
//字符串格式 每个操作数或者操作符号后面加一个空格，最后一个操作符号可以不加
//数据为int
string a="3424 665 + 542 / 85 * 544 - 7655 +";
int b=Post(a);
cout<<a<<"的计算结果为"<<b<<endl;

/*
char* a=Change(15,16); //15转化为16进制
cout<<a<<endl;
*/

/*
string infixexp; //中缀转换为后缀，输入eof停止
cout<<"连续输入直到输入eof，即ctrl+z"<<endl;
cout<<"操作符仅限 （ + - * / ）"<<endl;
for(;cin>>infixexp;)
cout<<"Postfix expression is"<<PostFix(infixexp)<<endl;
*/
}

int Post(string postfixexp)
{
postfixexp.append(2,' ');
Stack<int>* NumberStack=new Stack<int>;
int i=0;
int number;
int first;
int last;
for(;postfixexp[i]!=32;)
{
int ch;
ch=FindNumber(postfixexp[i]);
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 b[10];
int num=0;
int k=0;
int jie=1;
for(;a[i]!=32;i++,k++)
{
b[k]=a[i]-48;
jie=jie*10;
}
b[k]=10;
for(int j=0;b[j]<10;j++)
{
num=num+b[j]*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<char>* m=new Stack<char>;
int zheng=1;
n=new char[100];
char jinzhi[]="0123456789ABCDEF";
//cout<<number<<"转换为"<<a<<"进制后的结果为：";
for(;zheng!=0;number=zheng)
{
zheng=number/a;
m->Puah_Head(jinzhi[number%a]);
}
for(zheng=0;m->Head->Next!=NULL;zheng++)
{
n[zheng]=(*m).Top();
m->Pop_Head();
}
n[zheng]='\0';
return n;
}

string PostFix(string exp)
{
bool flag=true;
int TokenNumber,TopTokenNumber;
Stack<char>* OpStack=new Stack<char>;
string PostFixExp;
string Op="0(+-*/)";
string Blank=" ";
int j=exp.length();
if(FindNumber(exp[0])>1) flag=false;
for(int i=0;i<j;i++)
{
TokenNumber=FindNumber(exp[i]);
switch(TokenNumber)
{
case 1: OpStack->Puah_Head(exp[i]);break;
case 6: for(;;)
{
if(OpStack->IsEmpty())
{
flag=false;
break;
}
TopTokenNumber=FindNumber(OpStack->Top());
OpStack->Pop_Head();
if(TopTokenNumber==1) break;
PostFixExp.append(Blank+Op[TopTokenNumber]);
}break;
case 2:
case 3:
case 4:
case 5:for(;;)
{
if(i<j-1)
if(FindNumber(exp[i+1])>1)
{
flag=false;
break;
}

if(OpStack->IsEmpty()||((TokenNumber/2)>(FindNumber(OpStack->Top())/2)))
{
OpStack->Puah_Head(Op[TokenNumber]);
break;
}
else
{
TopTokenNumber=FindNumber(OpStack->Top());
OpStack->Pop_Head();
PostFixExp.append(Blank+Op[TopTokenNumber]);
}
}
break;
case 0:PostFixExp.append(Blank+exp[i]);
for(;i<(j-1);)
{
if(FindNumber(exp[i+1])==1)
{
flag=false;
break;
}

if(FindNumber(exp[i+1])!=0) break;
i++;
PostFixExp.append(1,exp[i]);
}
break;
default:
flag=false;
}
}
for(;!OpStack->IsEmpty();)
{
TopTokenNumber=FindNumber(OpStack->Top());
OpStack->Pop_Head();
if(TopTokenNumber==1)
{
flag=false;
break;
}
else
PostFixExp.append(Blank+Op[TopTokenNumber]);
}

if(!flag)
PostFixExp="输入错误";

return PostFixExp;

}