栈的简单应用

//头文件“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

return Head->Date;

}

return Head->Next->Date;

}

template

void Stack::Travel()

{

Node* cur=new Node;

cur=Head;

for (;cur->Next!=NULL;)

{

cur=cur->Next;

coutDate

}

}

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"

#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

/*

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

cout*/

/*

string infixexp; //中缀转换为后缀，输入eof 停止

cout

cout

for(;cin>>infixexp;)

cout

}

int Post(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]

{

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" ;

//coutfor (;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* 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;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

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

{

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;

}

//头文件“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

return Head->Date;

}

return Head->Next->Date;

}

template

void Stack::Travel()

{

Node* cur=new Node;

cur=Head;

for (;cur->Next!=NULL;)

{

cur=cur->Next;

coutDate

}

}

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"

#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

/*

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

cout*/

/*

string infixexp; //中缀转换为后缀，输入eof 停止

cout

cout

for(;cin>>infixexp;)

cout

}

int Post(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]

{

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" ;

//coutfor (;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* 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;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

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

{

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;

}


相关内容

  • 小学数学大纲

    • 六年制小学数学教学大纲 一 年 级 每周4课时) 教学内容 (一) 数与计算 (1)20以内数的认识.加法和减法. 数数.数的组成.顺序.大小.读法和写法.加法和减法. 连加.连减和加减混合式题. (2)100以内数的认识.加法和减法. 数数.个位.十位.数的顺序.大小.读法和写法. 两位数加.减整 ...

  • [生活中的读与写]教学计划

    • 2009年<生活中的数与算>教学计划 梁贵珍 一.指导思想 开展扫盲工作,是提高全民族人口素质,消除贫困.促进社会文明进步的重要途径:是推进社会主义新农村建设的迫切需要:是实践"三个代表"重要思想和落实科学发展观的具体体现:是构建社会主义和谐社会的重要基础. 二.教学 ...

  • 百分数单元教案

    • 百分数的应用 主备人:张金利 一.单元教学的目标 1.在具体情境中理解"增加百分之几"或"减少百分之几"的意.义,加深对百分数意义的理解. 2.能利用百分数的有关知识以及方程解决一些实际问题,提高解决实际问题的能力,感受百分数与日常生活的密切联系. 二.教学内 ...

  • 应用文宣传提纲

    • 应用文写作系列 (三):宣传纲要 [例题(2010年·国考地市级申论真题·第三题)] a市市政府准备大力宣传推进对近海水域的污染整治工作,请你结合给定资料,以市政 府工作人员的身份,草拟一份宣传纲要.(20分) 要求: (1)对有关宣传内容的要点进行提纲挈领的陈述; (2)体现政府精神,使全市各界关 ...

  • 2015年全国新课标卷数学考试大纲(理科)

    • 2015年普通高等学校招生全国统一考试大纲(理科数学) Ⅰ．考试性质 普通高等学校招生全国统一考试是合格的高中毕业生和具有同等学力的考生参加的选拔性考试．高等学校根据考生成绩,按已确定的招生计划,德.智.体全面衡量,择优录取．因此,高考应具有较高的信度.效度,必要的区分度和适当的难度． Ⅱ．考试内容 ...

  • 陕西高考数学大纲2012(文)

    • 2012年高考考试说明(陕西省)--数学(文) 根据教育部考试中心<普通高等学校招生全国统一考试大纲(文科·课程标准试验·2012年版)>(以下简称<大纲>)和<2010年陕西省普通高校招生考试改革方案>,结合我省普通高中数学教学实际情况,制定了<2012年 ...

  • 最新高中数学教学大纲

    • 全日制普通高级中学数学教学大纲 数学是研究空间形式和数量关系的科学.数学能够处理数据.观测资料,进行计算.推理和证明,可提供自然现象.社会系统的数学模型.随着社会的发展,数学的应用越来越广泛.它已经成为人们参加社会生活.从事生产劳动的需要.它是学习和研究现代科学技术的基础:它在培养和提高思维能力方面 ...

  • 微积分教学大纲

    • 本人精心整理的文档 微 积 分 课 程 教 学 大 纲 (试 用 稿) 郑大昇达经贸管理学院共科部 微积分课程教学大纲 适用对象:财经类各专业 选用教材:微积分 (赵树嫄主编 中国人民大学出版社) 总 学 时:120学时 前 言 制定本教学大纲是为了规范和加强微积分课程的教学.提高教学质量．教学大纲 ...

  • 中国现当代文学

    • 黑龙江省高等教育自学考试 对外汉语专业(独立本科段) <中国现当代文学作品导读>考试大 纲 (课程代码 01207 ) 黑龙江省高等教育自学考试委员会办公室 二○一○年四月 中国现当代文学作品导读考试大纲 一. 课程性质与设置目的 <中国现当代文学作品导读>是高等教育自学考试 ...

  • 市场营销经理助理资格证考试大纲

    • 教育部考试中心 目 录 Ⅰ 考核能力要求 Ⅱ 考试形式和试卷结构 Ⅲ 考试内容和考核要求 (上)营销原理 第一部分 市场营销导论 第二部分 顾客价值与顾客满意 第三部分 战略计划与营销过程 第四部分 企业营销环境分析 第五部分 消费者购买行为 第六部分 组织购买行为 第七部分 市场细分.市场选择选择 ...

热门内容

标签

城市低保申请书范文   月销售工作计划范文   2012思想汇报范文   通知书的格式及范文   领导发言稿结尾范文   医药学术邀请函范文   公务员年度考核表范文   顶撞领导检讨书范文   体育老师求职信范文   农村批房申请书范文   班委意见范文   高中学习感想范文   铁路实习报告范文3000字