#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <iostream>
using namespace std;
int balance (char *exp)             //判斷括號是否匹配
{
	int count=0,i,len=strlen(exp);
	for (i=0;i<len;i++)
	{
		if (*(exp+i)=='(')	count++;	
		if (*(exp+i)==')')
			
		{
			if (count>0) count--;
			else return(0);
		}
	}
	if (!count) return(1);
	else return(0);
}
int table	(char op)              //取優先級數
{
	switch (op)
	{
	case '+': case '-':	return(12);
	case '*': case '/': case '%':	return(13);
	case ';': case '\0': case ')':	return(1);
	}
	return(-1);
}
void push (float *stack,int &top,float x)     //入棧
{
	
	top++;	
	*(stack+top)=x;
}
float pop (float *stack,int &top)      //出棧
{
	float temp=*(stack+top);
	top--;
	return(temp);
}
float count	(float val1,float val2,char op)    //兩數之間的運算
{
	switch (op)
	{
	case '+':	return(val1+val2);
	case '-':	return(val1-val2);
	case '*':	return(val1*val2);
	case '/':	return(val1/val2);
	};
	return(-1);
}
float operate	(char *exp,int len,int &k)      //求值
{
	int   ostop=0,nstop=-1;
	float *ns,val1,val2,temp;
	char  *os,op,opin;
	ns=(float *)malloc(len*sizeof(int));				//根據需要申請空間
	os=(char  *)malloc(len*sizeof(char));
	*os=';';
	*ns=0;
	while ((*(exp+k))!='\0' || nstop>0)
	{
		if ((*(exp+k))=='(')
		{
			k++;
			push(ns,nstop,operate(exp,len-k,k));
		}
		else
		{
			if ((*(exp+k))==')' && nstop==0) k++;
			else
			{
				if (47<(*(exp+k)) && (*(exp+k))<58)			//下一個運算元是數
				{
					temp=0;
					do
					{
						temp=temp*10+((float)(*(exp+k))-48);
						k++;
					}
					while (47<(*(exp+k)) && (*(exp+k))<58);
					push(ns,nstop,temp);
				}
				else
				{
					opin=*(os+ostop);
					op=(*(exp+k));
					if (table(opin) >= table(op))		//比較兩個運算符的優先級
					{
						val1=*(ns+nstop-1);
						val2=pop(ns,nstop);
						*(ns+nstop)=count(val1,val2,opin);
						ostop--;
					}
					else
					{
						k++;
						ostop++;
						*(os+ostop)=op;
					};
				};
			};
		};
	};
	temp=*ns;
	free(ns);						//釋放空間
	free(os);
	return(temp);
}



void main ()
{
	char exp[100];
	int k=0;
	cout<<"輸入表達式:"<<endl;;
	cin>>exp;
	if (balance(exp))
	{
		cout<<"計算結果為:"<<endl;;
		cout<<exp<<"="<<operate(exp,strlen(exp),k)<<endl;
	
	}
	else cout<<"表達式輸入錯誤，括號不匹配!"<<endl;;
	
}