|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
//main
#include <iostream>
#include"SqStack.h"
#include"Status.h"
using namespace std;
typedef char SElemtype;
int main()
{
SqStack S;
SElemtype e,c;
InitStack(S);
cout<<"请输入中缀表达式,以 '#' 作为结尾!";
cin>>c;
while('#'!=c)
{
while('0'<= c && '9'>= c)
{
cout<<c;
cin>>c;
if(c<'0'||c>'9')
{
cout<<" ";
}
}
if(')'==c)
{
Pop(S,e);
while('('!=e)
{
cout<<e<<" ";
Pop(S,e);
}
}
else if('+'==c||'-'==c)
{
if(!StackLen(S))
{
Push(S,c);
}
else
{
do
{
Pop(S,e);
if('('==e)
{
Push(S,e);
}
else
{
cout<<e<<" ";
}
}while(StackLen(S) && '('!=e);
Push(S,c);
}
}
else if( '*'==c || '/'==c )
{
if(StackLen(S))
{
Pop(S,e);
while('('!=e&&'+'!=e&&'-'!=e)
{
cout<<e<<" ";
Pop(S,e);
}
Push(S,e);
}
Push(S,c);
}
else if( '*'==c || '/'==c )
{
if(StackLen(s))
{
Pop(&s,&e);
while('('!=e&&'+'!=e&&'-'!=e)
{
printf("%c ",e);
Pop(&s,&e);
}
Push(&s,e);
}
Push(&s,c);
}
else if('('==c)
{
Push(&s,c);
}
else if('#'==c)
{
break;
}
else
{
cout<<"\n输入格式错误!\n";
return INFEASIBLE;
}
cin>>c;
}
while(StackLen(S))
{
Pop(S,e);
cout<<e<<" ";
}
return 0;
}
//SqStack头文件
#ifndef SQSTACK_H_INCLUDED
#define SQSTACK_H_INCLUDED
#endif // SQSTACK_H_INCLUDED
#include<iostream>
using namespace std;
#include<stdlib.h>
#include "Status.h"
#define MAXSIZE 80 //栈的储存空间初始分配量
typedef char SElemtype;
typedef struct
{
SElemtype *base; //栈底指针
SElemtype *top; //栈顶指针
int stacksize; //最大容量
}SqStack;
Status InitStack(SqStack &S) //栈的初始化
{
S.base=new SElemtype[MAXSIZE]; //分配最大容量为MAXSIZE的数组空间
if(!S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base; //初始为空栈
S.stacksize=MAXSIZE; //stacksize设置为栈的最大容量MAXSIZE
return OK;
}
Status Push(SqStack &S,SElemtype e) //入栈
{
if((S.top-S.base)==S.stacksize) //判断栈满
return ERROR;
else
{
*S.top=e;
++S.top; //栈顶指针加1
}
return OK;
}
Status Pop(SqStack &S,SElemtype &e) //出栈
{
if(S.top==S.base) //栈空
return ERROR;
else
{
e=*S.top;
--S.top; //栈顶指针减1
}
return OK;
}
Status StackLen(SqStack S) //求栈长
{
return(S.top-S.base);
}
int GotTop(SqStack S) //取栈顶元素
{
if(S.top!=S.base)
return *(S.top-1);
}
void SqStackTraverse(SqStack S)//遍历
{
SElemtype *p;
p=S.base;
while(S.top!=p)
{
cout<<*p++<<" ";
}
cout<<endl;
}
//Status文件
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
建立的是c++工程
|
|