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

#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 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(SElemType a,SElemType b);
int Operate(SElemType a, SElemType theta, SElemType b);

//-----------基本操作的算法描述----------------

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)//销毁栈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)//把S置为空栈 
{
	while(S.top!=S.base){
		free(S.top);
		S.top--;
	}
	free(S.base);
	return OK;

}


Status StackEmpty(SqStack S)//若栈不为空，则用e返回s的栈顶元素，并返回OK；否则返回ERROR
{
	if(S.base==S.top) return TRUE;
	else return FALSE;
}


int StackLength(SqStack S)//返回栈S的长度 
{
	int i;
	for(i=0;S.base!=S.top;i++){
		S.top--;
	}
	return i;
}


Status GetTop(SqStack S,SElemType &e)//读取栈顶元素到e 
{
	if(S.top==S.base) return ERROR;
	e=*(S.top-1);
	return OK;
}

Status Push(SqStack &S,SElemType e)//插入元素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)//若栈不为空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
{
	if(S.top==S.base) return ERROR;
	e=*(--S.top);
	return OK;
}


Status StackTraverse(SqStack S)//遍历栈S 
{
	int flag=0 ;
	while(S.top!=S.base){
		printf("%c\t",*S.base);
		S.base++;
		flag=1;
	}
	if(flag==1) return OK;
	else return ERROR;
}


char Precede(char a,char b)//判断运算符a和b的优先级 
{
	int i,j;
	char pre[][7]={//算符间的优先关系表 
		{'>','>','<','<','<','>','>'},
		{'>','>','<','<','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'>','>','>','>','<','>','>'},
		{'<','<','<','<','<','=','0'},
		{'>','>','>','>','0','>','>'},
		{'<','<','<','<','<','0','='}
		};
	switch(a){
		case '+':
			i=0;
			break;
		case '-':
			i=1;
			break;
		case '*':
			i=2;
			break;
		case '/':
			i=3;
			break;
		case '(':
			i=4;
			break;
		case ')':
			i=5;
			break;
		case '#':
			i=6;
			break;
	}
	switch(b){
		case '+':
			j=0;
			break;
		case '-':
			j=1;
			break;
		case '*':
			j=2;
			break;
		case '/':
			j=3;
			break;
		case '(':
			j=4;
			break;
		case ')':
			j=5;
			break;
		case '#':
			j=6;
			break;
	}
	return pre[i][j];
}


int Operate(SElemType a, SElemType theta, SElemType b)//计算二元表达式a theta b 
{
	int i,j,result;
	i=a-'0';
	j=b-'0';
	
	switch(theta){
		case '+': result=i+j;break;
		case '-': result=i-j;break;
		case '*': result=i*j;break;
		case '/': result=i/j;break;
	}
	return result;
}


Status In(char c,char op[])//判断c是否为运算符，是则返回1，否则返回0
{
	char *p;
	p=op;
	while(*p!='\0'){
		if(c==*p)
			return TRUE;
		p++;
	}
	return FALSE;
}

SElemType EvaluateExpression(){
  
    char c;//每次读入的字符 
    char theta; 
    char x;
    char a,b;

    char OP[]="+-*/()#";//运算符集 
    SqStack  OPTR;				//运算符栈 
    SqStack  OPND;				//操作数栈

    InitStack(OPTR);      
    Push(OPTR,'#');
    InitStack(OPND);
    c=getchar();
    GetTop(OPTR,x);
    while(c!='#'||x!='#'){
    	if(!In(c,OP)){
    		Push(OPND,c);
    		c=getchar();
		}
		else 
			switch (Precede(x,c)){
				case '<' ://栈顶元素优先权低 
					Push(OPTR,c);
					c=getchar();
					break;
				case '=' ://脱括号并接收下一个字符 
					Pop(OPTR,x);
					c=getchar();
					break;
				case '>' ://退栈并将结果入栈 
					Pop(OPTR,theta);
					Pop(OPND,b);
					Pop(OPND,a);
					Push(OPND,Operate(a,theta,b)+'0');
					break;
			}//end of switch
		GetTop(OPTR, x);
	}//end of while
	GetTop(OPND,c);
	return c;
}


Status SaveFile(SqStack S){
	FILE *fp;
	if((fp=fopen("data.dat","w"))==NULL){
		printf("File open error\n");
		return ERROR;
	}
	while(S.base!=S.top){
		fwrite(S.base,sizeof(SElemType),1,fp);
		S.base++;
	}
	fclose(fp);
	return OK; 
} 


Status ReadF(SqStack &S)
{
	FILE *fp;
	SElemType *basee;
	basee=S.base;
	if ((fp=fopen("data.dat","r"))==NULL)
	{
	 printf("File open erroe\n ");
	 return ERROR;
	}
	while(fread(S.top,sizeof(SElemType),1,fp))
	   S.top++;
		//这里从文件中逐个读取数据元素恢复栈
	fclose(fp);
	return OK;
}


/*int main(){
    char c;
    printf("Please input one expression,end with \"#\":");
    c=EvaluateExpression();
    printf("Result=%c\n",c);
    getchar();
    return 0;
}*/


int main(){
  SqStack S;
  SElemType e;
  int op=1;
  while(op){
	system("cls");
	printf("\n\n");
	printf("      Menu for Linear Table On Sequence Structure \n");
	printf("-------------------------------------------------\n");
	printf("    	  1. IntiaStack        8. StackTrabverse\n");
	printf("    	  2. DestroyStack      9. ReadFile\n");
	printf("    	  3. ClearStack        10. SaveFile\n");
	printf("    	  4. StackEmpty        11. EvaluateExpression\n");
	printf("    	  5. StackLength       12. GetTop\n");
	printf("    	  6. PushStack        \n");
	printf("    	  7. PopStack		  \n");
	printf("    	  0. Exit\n");
	printf("-------------------------------------------------\n");
	printf("    请选择你的操作[0~12]:");
	scanf("%d",&op);
    switch(op){
	   case 1:
	   	{
		 if(InitStack(S)==OK) printf("栈创建成功！\n");
		     else printf("栈创建失败！\n");
		 getchar();getchar();
	   	}
		 break;
	   case 2:
		 if(DestroyStack(S)==OK) printf("栈销毁成功！\n");
		     else printf("栈销毁失败！\n");
		 getchar();getchar();
		 break;
	   case 3:
		 if(ClearStack(S)==OK) printf("栈清空成功！\n");
		     else printf("栈清空失败！\n");     
		 getchar();getchar();
		 break;
	   case 4:
		 if(StackEmpty(S)) printf("栈是空的\n");
		 else printf("栈不是空的\n");
		 getchar();getchar();
		 break;
	   case 5:
	   	{
		 printf("栈长度为%d\n",StackLength(S));
		 getchar();getchar();
	   	}
		 break;
	   case 6:
	   	{
		 printf("请输入要入栈的字符：");
		 getchar(); 
		 scanf("%c",&e);
		 
		 if(Push(S,e))
			printf("入栈成功");
		else printf("入栈失败");
		 getchar();getchar();
	   	}
		 break;
	   case 7:
	   	{
		 if(Pop(S,e)) printf("%c出栈成功",e);
		 else printf("出栈失败");
		 getchar();getchar();
	   	}
		 break;
	   case 8:     
		 if(!StackTraverse(S)) printf("栈是空的！\n");
		 getchar();getchar();
		 break;
	   case 9:
	   	{
	   		if(ReadF(S)){
	   			printf("文件读取成功！\n");
	   		}
	   		else printf("文件读取失败！\n");
			 getchar();getchar(); 
	   	}
	   	break;
	   case 10:
	   	{
	   		if(SaveFile(S)) printf("文件保存成功！\n");
	   		else printf("文件保存失败！");
	   		getchar();getchar();
	   	}
		break;
	   case 11:
	   {
			char c;
			printf("Please input one expression,end with \"#\":");
			c=EvaluateExpression();
			printf("Result=%c\n",c);
			getchar();getchar();
	   }
	   break;
	   case 12:
			if(GetTop(S,e)) printf("栈顶元素是%c\n",e);
			else printf("栈为空\n");
	   case 0:
         break;
	}//end of switch
  }//end of while
  printf("欢迎下次再使用本系统！\n");
  return 0;
}//end of main()