// 漏洞：01+2=3  誤認(rèn)為合法
//        (-2+3） 誤認(rèn)為非法 
//       1/0 默認(rèn)為允許
  ////////////  以上漏洞已經(jīng)修復(fù) 2007年5月22號(hào)
#include<iostream>
#include "計(jì)算.h"
#include "Windows.h"  //Sleep()函數(shù)
#define NUM 1
#define OPE 2 //判斷字符的類型
#define RK 3
#define LK 4
#define END 5
#define OTHER -1

typedef char SElemType;

using namespace std;

 struct SqStack
{
	SElemType *base;
	SElemType *top;
	int stackSize;
		
};

int kind(const char c);
bool checkOrder( const char *q)  ;
bool canKuoHaoMatch(const char *c) ; //檢查括號(hào)是否匹配
bool push(SqStack &S,SElemType e);
bool pop(SqStack &S,SElemType &e);
bool initSqStack(SqStack &S);
bool checkItNow(const SElemType *c);
char precede(const char a,const char b) ; //判斷運(yùn)算符a與b的優(yōu)先級(jí)  
SElemType getTop(SqStack S);
float calExpress(const SElemType *c);


int main()
{
	char b[78];
    char c[80];
	while(true)
	{		
		cout<<"請(qǐng)輸入表達(dá)式"<<endl;
		cin>>b;
		int j=0;
		if(b[0]=='-')  //若第一個(gè)字符為'-',則在它前面加上一個(gè)'0'
		{
			j=1;
			c[0]='0';
		}
		int i=0;
		while(b[i])		//將數(shù)組b處理后，存儲(chǔ)到數(shù)組c
		{
			if(b[i]=='('&&b[i+1]=='-')  //若是這種情況 "(-    ",則數(shù)組c前三個(gè)字符為 "(0-   "
			{
				c[j++]=b[i++];
				c[j++]='0';
			}
			else
				c[j++]=b[i++];
		}

		c[j]='\0';
		if (!checkItNow(c))
		{
			Sleep(500);
			cout<<"你輸入了非法表達(dá)式! "<<endl;
			Sleep(500);
			continue;
		}
		    
       	c[j]='#';
		c[j+1]='\0';
		
		cout<<b<<"=";
		Sleep(500);
		cout<<calExpress(c)<<endl;
		Sleep(500);
	}
	
	
	
	return 0;
}
bool initSqStack(SqStack &S)
{
	S.base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) return false;
	S.top=S.base;
	S.stackSize=STACK_INIT_SIZE;
	return true;
}
bool push(SqStack &S,SElemType e)
{
	if(S.top-S.base>=S.stackSize-1)
	{
		S.base =(SElemType *)realloc(S.base,(S.stackSize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) return false;
		S.top =S.base +(S.stackSize -1);
		S.stackSize+=STACKINCREMENT;
	}
	*S.top=e;
	S.top+=1;
	
	return true;
}


bool pop(SqStack &S,SElemType &e)
{
	if (S.base==S.top) return false;
	e=*--S.top;
	return true;
}



SElemType getTop(SqStack S)
{
	SElemType e;
	if(S.base ==S.top) exit(1);
	e=*--S.top;
	return e ;
}


int kind(const char c)		//判定字符種類
{
	if(c>='0'&&c<='9')	//數(shù)字字符
		return NUM;
	if(c=='+'||c=='-'||c=='*'||c=='/')	//運(yùn)算符號(hào)
		return OPE;
	if(c=='(')
		return LK;
	if(c==')')
		return RK;
	if(c=='\0')
		return END;
	return OTHER;  //其他非法字符
}
bool checkOrder(const char *q)  //檢測(cè)表達(dá)式符號(hào)順序是否正確
{
	if(kind(q[0])==OPE) return false;
	int t=0;	//判斷是否正在掃描操作數(shù)
	while(*q!='\0')
	{
		int flag=kind(*(q+1));
		
		switch(kind(*q))
		{
		case NUM:
			t++;
			if(*q=='0'&&flag==NUM&&t==1) return false;  //非零數(shù)的第一位不能為零
			if(flag==OPE||flag==RK||flag==END||flag==NUM)	//數(shù)字后面只能是：運(yùn)算符號(hào)，右括號(hào)，'\0',數(shù)字字符
			{
				q++;
				break;
			}
			else
				return false;
		case OPE:
			t=0;
			if(*q=='/'&&*(q+1)=='0')return false;  //分母不能為零
			if(flag==NUM||flag==LK)
			{
				q++;
				break;
			}
			else
				return false;
		case LK:
			t=0;
			if(flag==NUM||flag==LK)
			{
				q++;
				break;
			}
			else
				return false;
		case RK:
			t=0;
			if(flag==OPE||flag==END||flag==RK)
			{
				q++;
				break;
			}
			else
				return false;
		case OTHER:
			t=0;
			return false;
		}
	}
	return true;
}

bool canKuoHaoMatch(const SElemType *c)  //檢查括號(hào)是否匹配
{
	SqStack kuo;
	SElemType a;
 	initSqStack(kuo);
	while(*c!='\0')
	{
		if('('==*c) push(kuo,*c);		//若為左括號(hào)則進(jìn)棧
		if(')'==*c)			//若為右括號(hào)則出棧
		{
			if(kuo.base ==kuo.top ) return false;
			pop(kuo,a);
		}
		c++;
	}
	if(kuo.base ==kuo.top )		//遍歷整個(gè)字符串后，若括號(hào)匹配，棧應(yīng)該為空
		return true;
	else
		return false;
}
bool checkItNow(const SElemType *c)
{
	if(canKuoHaoMatch(c)&checkOrder(c))
		return true;
	else
		return false;
}

char precede(const char a,const char b)  //判斷運(yùn)算符a與b的優(yōu)先級(jí)  
{                            //假設(shè)a，b都是合法字符,即表達(dá)式正確
	switch(a)
	{
	case '+':
		if(b=='*'||b=='/'||b=='(') 
			return '<';
		else
			return '>';
	case '-':
		if(b=='*'||b=='/'||b=='(') 
			return '<';
		else
			return '>';
	case '*':
		if('('==b)
			return '<';
		else
			return '>';
	case '/':
		if('('==b)
			return '<';
		else
			return '>';
	case '(':
		if (')'==b)
			return '=';
		else
			return '<';
	case ')':
		return '>';
	case '#':
		if(b=='#')
			return '=';
		else
			return '<';
	default:
		return ' ';
	}
}

float calExpress(const SElemType *c)	//運(yùn)算表達(dá)式的值
{
	SqStack OPTR;
	calStack OPND;
	initSqStack(OPTR);
	push(OPTR,'#');
	initcalStack(OPND);
	while(*c!='#'||getTop(OPTR)!='#')
	{
		float temp=0;
		int i=0;   // i為數(shù)字的位數(shù)
		if(kind(*c)==NUM)
		{
			const SElemType *p;
			p =c;
			for(;kind(*p)==NUM;p++)	//當(dāng)*p為數(shù)字時(shí)，計(jì)算出有幾個(gè)數(shù)字字符連續(xù)個(gè)數(shù)
			{
				i++;
			}
			for(int j=i;j>=1;j--)
			{
				temp+=change(*c,j);
				c++;
			}	
			pushNum(OPND,temp);		//將操作數(shù)入棧
		}
		else
		{
			SElemType theta=getTop(OPTR);
			switch(precede(theta,*c))
			{
			case '<':
				push(OPTR,*c);
				c++;
				break;
			case '=':
				SElemType x;
				pop(OPTR,x);
				c++;
				break;
			case '>':
				float a,b;
				pop(OPTR,theta);
				popNum(OPND,b);
				popNum(OPND,a);
				pushNum(OPND,operate(a,theta ,b));
				break;
			}
		}
	}
	return getTopNum(OPND);
}