栈的简单应用.doc

//头文件“stack.h”

#ifndef STACK_H
#define STACK_H

template
class Node
{
public:
Node();
Node(const Type& date);
~Node();
//private:
Type Date;
Node *Next;
};
template
class Stack
{
public:
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;
}

template
void 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)
{
cout<<"Stack为空"<Date;
}
return Head->Next->Date;
}

template
void Stack::Travel()
{
Node* cur=new Node;

cur=Head;
for(;cur->Next!=NULL;)
{
cur=cur->Next;
cout<Date<
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"
#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<"<>infixexp;)
cout<<"Postfix expression is"<st(string postfixexp)
{
postfixexp.append(2,' ');
Stack* NumberStack=new Stack;
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* m=new Stack;
int zheng=1;
n=new char[100];
char jinzhi[]="0123456789ABCDEF";
//cout<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* OpStack=new Stack;
string PostFixExp;
string Op="0(+-*/)";
string Blank=" ";
int j=exp.length();
if(FindNumber(exp[0])>1) flag=false;
for(int i=0;iPuahHead(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(i1)
{
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;

}