/////////////////////////////////////////////////////////// 
//--------------------------------------------------------- 
//            顺序栈存储结构及基本操作 
//--------------------------------------------------------- 
/////////////////////////////////////////////////////////// 

#include<stdio.h> 
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<ctype.h>

//以下为函数运行结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0 
#define INFEASIBLE -1 
#define OVERFLOW -2 

#define STACK_INIT_SIZE 100  //顺序栈存储空间的初始分配量 
#define STACKINCREMENT 10  //顺序栈存储空间分配增量 

typedef int Status; //函数类型，其值为函数结果状态代码 

typedef char TElemType; //数据类型定为字符型 
typedef struct BiTNode{
		TElemType  data;//结点存储数据的值 
		BiTNode *lchild, *rchild;//指向左子树 
} *BiTree;
typedef BiTree SElemType; 

typedef struct 
{ 
    SElemType *base; //存储空间基址 
    SElemType *top; //栈顶指针 
    int stacksize; //当前分配的存储容量 ，以元素为单位 
}SqStack; 

//-------------基本操作的函数原型说明----------------
Status IninStack(SqStack &S);
Status DestroyStack(SqStack &S);
Status ClearStack(SqStack &S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType &e);
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackTraverse(SqStack S);

char Precede(char a,char b);
int Operate(int a, char theta, int b);

//-----------基本操作的算法描述----------------
///////////////////////////////////////
//函数名：InitStack()
//参数：SqStack *S
//初始条件：无
//功能：构造一个空栈
//返回值：存储分配失败：OVERFLOW
//        存储分配成功：OK
/////////////////////////////////////// 
Status InitStack(SqStack &S)
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) exit(OVERFLOW);//存储分配失败 
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
} 


Status DestroyStack(SqStack &S)
{
	while(S.top!=S.base){
		free(S.top);
		S.top--;
	}
	free(S.base);
	S.base=NULL;
	S.top=NULL;
	return OK;
} 


Status ClearStack(SqStack &S)
{
	while(S.top!=S.base){
		free(S.top);
		S.top--;
	}
}


Status StackEmpty(SqStack S)
{
	if(S.base==S.top) return TRUE;
	else return FALSE;
}


int StackLength(SqStack S)
{
	int i;
	for(i=0;S.base!=S.top;i++){
		S.top--;
	}
	return i;
}


Status GetTop(SqStack S,SElemType &e)
{
	if(S.top==S.base) return ERROR;
	e=*(S.top-1);
	return OK;
}

Status Push(SqStack &S,SElemType e)
{
	if(S.top-S.base>=S.stacksize){
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return OK;
}


Status Pop(SqStack &S,SElemType &e)
{
	if(S.top==S.base) return ERROR;
	e=*--S.top;
	return OK;
}


Status StackTraverse(SqStack S)
{
	while(S.top!=S.base){
		printf("%d\t",*S.base);
		S.base++;
	}
	return OK;
}