#include<stdio.h>
#include<math.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>

#define STACK_INIT_SIZE 100 //存儲空間初始分配量
//#define STACKINCREMENT 10

#define OK 1
#define ERROR 0
#define MAX 40
int fix=1;

#define n 7    //運算符個數

 #   define     LESS                   '<'  
 #   define     EQU                     '='  
 #   define     MORE                   '>'
 #   define     ERR                     ' '  

 char    Precede[n][n]={{   MORE,MORE,LESS,LESS,LESS,MORE,MORE   },   /*     +     */   
                                          {   MORE,MORE,LESS,LESS,LESS,MORE,MORE   },   /*     -     */   
                                          {   MORE,MORE,MORE,MORE,LESS,MORE,MORE   },   /*     *     */   
                                          {   MORE,MORE,MORE,MORE,LESS,MORE,MORE   },   /*     /     */   
                                          {   LESS,LESS,LESS,LESS,LESS,   EQU,   ERR   },   /*     (     */   
                                          {   MORE,MORE,MORE,MORE,   ERR,MORE,MORE   },   /*     )     */   
                                          {   LESS,LESS,LESS,LESS,LESS,   ERR,   EQU   }};/*     #    */   
    
 char OP[n]={'+','-','*','/','(',')','='};

typedef struct{
	char *base;
	char *top;
	
	int stacksize;
}SqStack;



int InitStack(SqStack &s)
{
	s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
	if(!s.base )
		exit(OVERFLOW);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return OK;
}

char GetTop(SqStack s){
	char e;
	if(s.top==s.base) 
		return ERROR;
	e=*(s.top-1);
	return e;
}

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


int Pop (SqStack &s,char &e) 
{ 
	if(s.top==s.base)
		return ERROR;
	e=*--s.top;
	return OK;
}

int In(char c,char p[])
{
	for(int i=0;i<n;i++)
		if(c==p[i])
			return 1;
	if(c>='0' && c<='9')
		return 0;
	else 
		fix=0;
	printf("表達式有錯誤,不可識別的字符!\n");
	return OVERFLOW;
}

float GetNum(char &c)
{

	float num=0;
	int k=10;


	while(!In(c,OP) && c!='.')
	{	
		num=num*10+c-48;
		c=getchar();
	}
	if(c=='.')
	{
		c=getchar();
		while(!In(c,OP))
		{
			
			num=num+(float)(c-48)/k;
			k*=10;
			c=getchar();
		}
	}
	return	num;

}

int Order(char c)
{
	 for(int i=0;i<n;i++)
	 {
		 if(c==OP[i])
			 return i;
	 }
	 return OVERFLOW;
	
}

float Operate(float a,char theta,float b)
{
	switch(theta)
	{
	case '+':
		return a+b;
	case '-':
		return a-b;
	case '*':
		return a*b;
	case '/':
		if(b==0)
		{
			printf("表達式錯誤，有除0操作!\n");
			fix=0;
			return OVERFLOW;
		}
		return a/b;
	default:
		return ERROR;
	}
}

float EvaluateExpression()
{
	int count=1;
	char theta,c,x;
	SqStack OPTR;
	float OPND[MAX];

	InitStack(OPTR);
	Push (OPTR,'=');  //初始化運算符棧
	c=getchar();  
	if(c=='-')
		OPND[count++]=0;
	
	fix=1;
	for(int i=0;i<MAX;i++)
		OPND[i]=0;
       
	while ((c!='=' || GetTop(OPTR)!='=') && fix!=0)
	{ 

		if (!In(c,OP) )        //讀入的c不是運算符                 
		{ 
			x=' ';
			OPND[count]=GetNum(c);
			count++;
		} //操作數進棧             
		else  
		{
			if(c=='-' && x=='(')
				OPND[count++]=0;
			switch (Precede[Order(GetTop(OPTR))][Order(c)])
			{ 
				case LESS:
					Push(OPTR,c);
					x=c;
					c=getchar( ); 
					break; //棧頂元素優先權低，運算符進棧
                case EQU:
					Pop(OPTR,c);
					c=getchar( );
					break; //脫括號并接收下一字符
                case MORE:
					Pop(OPTR, theta);
					float a,b;
                   
					a=OPND[count-2];
					b=OPND[count-1];
					count-=2;
					if(count<=0)
					{
						fix=0;
						printf("請檢查表達式!\n");
					}
					OPND[count++]=Operate(a,theta,b); 
					break; //退棧并將運算結果入棧
				case ERR:
					printf("表達式有錯誤,括號不匹配!\n");
					fix=0;
					return ERROR;
           } //switch
		}
    } //while         
	return OPND[count-1];
} // EvaluateExpression             


void main()
{
	char choose='y';
	while(choose=='y' || choose=='Y')
	{
		printf("請輸入表達式：");
		float num=EvaluateExpression();
		if(fix!=0)
			printf("結果為：%f\n",num);
		while(getchar()!='\n')
		{}
		printf("繼續(Y)?\n請選擇(其它鍵退出)：");
		choose=getche();
		printf("\n\n");
	}
}