}SqStack;

void InitStack (SqStack &S)	      
{   
	//構造一個空棧s
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) exit (-1);										
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;				
}

bool GetTop (SqStack S,SElemType  &e)
{	
	//若棧不空，則用e返回s的棧頂元素，并返回OK；否則返回ERROR;
	if(S.top==S.base)
		return false;
	e=*(S.top-1);
	return true;
}

bool 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(-1);		
			S.top=S.base+S.stacksize;
			S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return true;
}

bool  Pop(SqStack &S,SElemType &e)
{
	//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR
	if(S.top==S.base)
		return false;
	e=*--S.top;				
	return true ;
}

char Precede(char a ,char b)
{
	//比較a，b的優先級，返回PR
	char PR;
	switch(b)
	{
		case'+':						
		case'-':if(a=='('||a=='#')
				   PR='<';
			    else
				   PR='>';
			    break;
		case'*':						
		case'/':if(a=='*'||a=='/'||a==')')
				   PR='>';
			    else
			   	   PR='<';
			    break;
		case'(':if(a==')')
				{
				  cout<<"括號匹配錯誤!"<<endl;
			      exit(-1);
				}
			    else
				  PR='<';
			    break;
		case')':if(a=='(')
		          PR='=';
			    else if(a=='#')
				      {
				         cout<<"error!沒有左括號"<<endl;
			             exit (-1);
				      }
			         else
				       PR='>';
			    break;
		case'#':  switch(a)
				  {
		             case'#':   PR='=';
				                break;
		             case'(':   cout<<"error!沒有右括號"<<endl;
				                exit(-1);
			         default:   PR='>';
				  }break;
	}
	return PR;
}
                   
bool In(char a)
{
	//判斷a是否為運算符
	switch(a)
	{
	case'+':
	case'-':
	case'*':
	case'/':
	case'(':
	case')':
	case'#':
		return true;
	default:
		return false;
	}
}

SElemType Operate( SElemType a, SElemType theta,SElemType b )
{
	//根據不同的theta進行不同的運算
	char n=char(theta);
	switch(n)    
	{
	case'+':   return a+b;
	case'-':   return a-b;
	case'*':   return a*b;
	default:
		if(b!=0)
			return a/b;
		else
		{
			cout<<"error!除數不能為零"<<endl;
			exit(-1);
		}
	}
}

SElemType EvaluateExpression()
{
	//算術表達式求值的算符優先算法、設OPTR和OPND分別為運算符棧和運算數棧
	SqStack OPTR,OPND;
	char c;
	char Number[10];
	SElemType a,b,d,e;
	InitStack(OPTR);
	InitStack(OPND);
	Push(OPTR,'#');
	c=getchar();
	GetTop(OPTR,e);
	while(c!='#'||e!='#')
	{
		if(In(c))
		{
			switch(Precede(e,c))
		   {
			case'<':			
				Push(OPTR,c);
				c=getchar();
				break;
			case'=':				
				Pop(OPTR,e);
				c=getchar();
				break;
			case'>':				
				Pop(OPTR,e);
				Pop(OPND,b);
				Pop(OPND,a);
				Push(OPND,Operate(a,e,b));
				break;
			}
		}
		else if(c>='0'&&c<='9'||c=='.')
		{
			int i=0;
			while(c>='0'&&c<='9'||c=='.')
			{
				Number[i]=c;
				i++;
				c=getchar();
			}
			Number[i]='\0';
			d=atof(Number);
			Push(OPND,d);
		}
		else
		{
			cout<<"error!輸入錯誤!"<<endl;
			exit(-1);
		}
		GetTop(OPTR,e);
	}
	GetTop(OPND,e);
	return e;
}

int main()
{
	SElemType  result;
	cout<<"請輸入表達式以#號結束!"<<endl;
	result=EvaluateExpression();
	cout<<"運算結果:"<<result<<endl;
	return 0;
}