/*
作者介紹：陳碩，男，1982年4月生，現(xiàn)就讀于北京師范大學(xué)電子系2000級(jí)。
通信方法：100875，北京師范大學(xué) 電子系1300信箱 陳碩 
E - Mail : chenshuo@chenshuo.com ，個(gè)人主頁(yè)：http://www.chenshuo.com 
代碼的說(shuō)明在readme.txt中
Version 0.99 beta
*/

#include "calculator.h"
#include <stdio.h>

void Calculator::Clear(void)
{ // 初始化計(jì)算器
	PO.Clear();
	Result = 0;
	ErrorID = ERR_NO_ERROR;
	VarCount = 0;
	Expression[0] = '\0';

	for(int i = 0; i < MaxNumber_of_Variable; i++) {
		VarName[i][0] = '\0';
		Vars[i] = 0.0;
	}
}

const char* Calculator::GetErrorMessage(int errid) const
{
	static const char *errmsg[] = {"no errors",
		"expression too long",
		"missing operand",
		"missing operator",
		"missing left parenthesis",
		"missing right paraenthesis",
		"devide by zero",
		"unknown operator",
		"invalid operator",
		"unknown error",
		"too many variables",
		"variable's name too long",
		"UNKNOWN ERROR ID!!!"};

	if(errid >= 0 && errid < 12)
		return errmsg[errid];
	else
		return errmsg[12];
}

void Calculator::Assign(double *pExtVars)
{ // 將pExtVars所指向數(shù)組的值賦給Vars[]
	double *pd = Vars; 
	while(pd < Vars + VarCount)
		*pd++ = *pExtVars++;
}

const char* Calculator::GetVariableName(int i)
{
	if (i>=0 && i<VarCount) {
		return VarName[i];
	} else {
		return 0;
	}
}

void Calculator::Trim(char *buf)
{ //初始化,去除str[]中的非法字符
	
	//char buf[MaxLength_of_Expression];
	char charset[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+-*/()^."; //合法的字符
	
	strupr(buf);
	
	int i = 0;
	int j = 0;
	char ch;
	
	while(ch = buf[i++]) {
		if(strchr(charset, ch))
			Expression[j++] = ch;
	}

	Expression[j] = '\0';
}

bool Calculator::IsOperandChar(int i) const
{ //判斷是否為操作數(shù)字符
	char ch, ch0, ch1;
	int l = strlen(Expression);
	ch = Expression[i];
	ch0 = Expression[i==0 ? 0:i-1];
	ch1 = Expression[i==l-1 ? i:i+1];

	if(isdigit(ch) || ch == '.')
		return true;

	if(ch == '-'||ch == '+') //判斷這個(gè)"+"或"-"是不是數(shù)字的一部分
		if(strchr("+-*/^(", ch0) != 0 && (isdigit(ch1) || ch1 == '.'))
			return true;

	return false;
}

bool Calculator::IsOperatorChar(int i) const
{ //判斷是否為操作符字符
	char ch = Expression[i];
	
	if(strchr("+-*/^", ch)!=NULL)
		return true;
	if(isalpha(ch))
		return true;
	return false;
}

void Calculator::GetOperand(int &i, char *buf) const
{ //讀取完整的操作數(shù)
	int t = 0;
	
	while(IsOperandChar(i)) 
		buf[t++] = Expression[i++];
	buf[t] = '\0';
}

bool Calculator::GetOperator(int &i, char *buf) const
{ //讀取完整的操作符 如SIN COS及變量名等
	int t = 0;
	char ch;
	ch = Expression[i];

	if(strchr("+-*/^", ch) != 0) { //取單字符的雙目操作符
		buf[t++]=ch;
		i++;
    	buf[t] = '\0';
	    return true;
	} 
	
	//取連續(xù)的由字母和數(shù)字組成的字符串
	while(isalnum(Expression[i])) {
		buf[t++] = Expression[i++];
		if(t >= MaxLength_of_VariableName) {
			Error(ERR_VARIABLE_NAME_TOO_LONG, __LINE__);
			return false;
		}
	}
	
	buf[t] = '\0';
	return true;
}

bool Calculator::GetUnary(element &EL, char ch, int rank) const
{ // 處理單字符非字母操作符
	if(rank == 1) { // 需要雙目操作符
    	EL.isp = 1; EL.icp = 1;
	    switch (ch) {
		    case '+': EL.type = OPTR_ADD; break;
		    case '-': EL.type = OPTR_SUBTRACT; break;
		    case '*': EL.type = OPTR_MULTIPLY; EL.isp = EL.icp = 2; break;
		    case '/': EL.type = OPTR_DIVIDE; EL.isp = EL.icp = 2; break;
		    case '^': EL.type = OPTR_POWER; EL.isp = 3; EL.icp = 4; break;
		    default : Error(ERR_UNKNOWN_OPERATOR, __LINE__); return false;
	    }
	    return true;
	}
	
	if(rank == 0) { // 需要單目操作符
	    EL.isp = 4; EL.icp = 5;
	    switch (ch) {
    		case '+': EL.type = OPTR_POSITIVE; break;
		    case '-': EL.type = OPTR_MINUS; break;
		    default : Error(ERR_UNKNOWN_OPERATOR, __LINE__); return false;
	    }
	    return true;
	}
	
	return false; //Error!
}

bool Calculator::GetVariable(element &EL, const char *buf, int &rank)
{
    int j;
    
    for(j = 0; j < VarCount; j++) {//是否為已知變量
		if(strcmp(VarName[j], buf) == 0) { //若是變量,則EL為操作數(shù)
			EL.type = 1 + j;
			EL.isp = 0; EL.icp = 0;
			rank++; // 操作數(shù)的等級(jí)為1,累計(jì)等級(jí)rank自加1
			if (rank > 1) {
				Error(ERR_MISS_OPERATOR, __LINE__);
				return false;
			}
		    return true;
    	}
	}
	
	if (VarCount < MaxNumber_of_Variable) {
		strcpy(VarName[VarCount], buf); //添加新變量
		EL.type = 1 + j;
		EL.isp = 0; EL.icp = 0;
		VarCount++;
		rank++;
		if (rank > 1) {
			Error(ERR_MISS_OPERATOR, __LINE__);
			return false;
		}
		return true;
	} else {
		Error(ERR_TOO_MANY_VARIABLES, __LINE__);
		return false;
	}
}

bool Calculator::GetElement(element &EL, const char *buf, int &rank)
{ // 得到buf所指的字符串對(duì)應(yīng)的表達(dá)式元素的屬性
	static char *fname[]={"SIN", "COS", "TAN", "SQR", "LOG10", 
			"LOG", "COT", "ABS", "INT", "ARCSIN", "ARCCOS", "ARCTAN",
			"SINH", "COSH", "TANH", "EXP", "SQRT", 0}; //支持的數(shù)學(xué)函數(shù)的名稱
	int l, j;
	char ch;

	l = strlen(buf);
	ch = buf[0];
	if(l == 1 && !isalpha(ch))  //非字母的單字節(jié)操作符
	    return GetUnary(EL, ch, rank);

     //處理字母字符串
	for(j = 0; fname[j] != 0; j++) {//是否為已有的數(shù)學(xué)函數(shù)
		if(strcmp(fname[j], buf) == 0) {
			EL.type = 51 + j;
			EL.isp = 4; EL.icp = 5;
			return true;
		}
	}
		
	if(GetVariable(EL, buf, rank)) {
		return true;
    }

	return false;
}

bool Calculator::Construe_Numeric(element &EL, int &i, int &rank) const
{
	char buf[MaxLength_of_Expression];
	GetOperand(i, buf);
	EL.type = 0;
	EL.value = atof (buf);
	
	rank++;
	if (rank > 1) {
		Error(ERR_MISS_OPERATOR, __LINE__);
		return false;
	}
	return true;
}

bool Calculator::Construe_Operator(element &EL, int &i, int &rank)
{
	char buf[MaxLength_of_VariableName];

	if(!GetOperator(i, buf)) // 取得整個(gè)操作符的名稱
		return false; //發(fā)生錯(cuò)誤

	if(!GetElement(EL, buf, rank)) // 取得相應(yīng)的屬性
		return false ; //發(fā)生錯(cuò)誤

	if(EL.type < 40 && EL.type > 20) // 若是雙目操作符,rank自減1
		rank--;
		
	if (rank < 0) {
		Error(ERR_MISS_OPERAND, __LINE__);
		return false;
	}
	return true;
}

void Calculator::Construe(Queue<element> &IN)
{ // 把輸入的表達(dá)式整理為中綴表達(dá)式
	element EL;

	char ch;
	int rank = 0; //表達(dá)式等級(jí)
	int i = 0;
	
	EL.icp = 0; EL.isp = 0; EL.value = 0;

	IN.Clear();

	while((ch = Expression[i]) != '\0') { //掃描表達(dá)式
		if(IsOperandChar(i)) { //處理數(shù)字
		    if(!Construe_Numeric(EL, i, rank))
		        return;
            IN.Insert(EL);
			continue;
			}
		
		if(ch == '(') {
			EL.type = 20; EL.icp = 6; EL.isp = -1;
			i++;
			IN.Insert(EL);
			continue;
			}
		
		if(ch == ')') {
			EL.type = 40; EL.icp = 0; EL.isp = 0;
			i++;
			IN.Insert(EL);
			continue;
			}
		
		if(IsOperatorChar(i)) { //處理操作符
            if (!Construe_Operator(EL, i, rank))
                return;
			IN.Insert(EL);
            continue;
		}
	} // end of while()

	if(rank != 1) 
		Error(ERR_MISS_OPERAND, __LINE__);
	return;
}

void Calculator::Conversion(Queue<element> &IN)
{ //轉(zhuǎn)換中綴表達(dá)式為后綴式

	element EL;
	int type;
	Stack<element> STE; // Stack to elements

	PO.Clear();
	
	while(!IN.IsEmpty()) { //依次取出中綴表達(dá)式的元素EL
		EL = IN.Delete();
		type = EL.type;
		
		if(type < 20) { // 若是操作數(shù)
			PO.Insert(EL);
			continue;
		}
		
		if(STE.IsEmpty()) { // 棧空時(shí),操作符直接壓棧
			STE.Push(EL);
			continue;
		}
		
		if(type == OPTR_RIGHT_PARENTHESIS) { // 若為右括號(hào)
			while(!STE.IsEmpty() \
				&& STE.Peek().type != OPTR_LEFT_PARENTHESIS) { // 取出左括號(hào)之前的操作符
				EL = STE.Pop();
				PO.Insert(EL);
			}
			if(STE.IsEmpty()) { 
				Error(ERR_MISS_LEFT_PARENTHESIS, __LINE__);
				return;
			}
			STE.Pop(); // 彈出左括號(hào)
			continue;
		}
		
		if(STE.Peek().isp < EL.icp) // 棧外優(yōu)先級(jí)高,則直接把EL壓棧
			STE.Push(EL);
		else { // 否則彈出棧內(nèi)的優(yōu)先級(jí)比EL.icp高的元素
			while(!STE.IsEmpty() && STE.Peek().isp >= EL.icp) {
				PO.Insert(STE.Pop());
			}
			STE.Push(EL);
		}
	}

	while(!STE.IsEmpty()) { // 棧內(nèi)剩余的操作符送入中綴表達(dá)式PO
		EL = STE.Pop();
		if(EL.type == OPTR_LEFT_PARENTHESIS) {
			Error(ERR_MISS_RIGHT_PARAENTHESIS, __LINE__);
			return;
		}
		PO.Insert(EL);
	}
}

bool Calculator::Input(char *exp)
{
	Queue<element> IN;
	
	Clear();

	if (strlen(exp) > MaxLength_of_Expression) {
		Error(ERR_EXPRESSION_TOO_LONG, __LINE__);
		return false;
	}

	Trim(exp); // 去除表達(dá)式的非法字符
	
	Construe(IN); // 整理為中綴表達(dá)式
	
	if(GetErrorID() != ERR_NO_ERROR)
		return false;
	
	Conversion(IN); // 轉(zhuǎn)換為后綴表達(dá)式
	return GetErrorID() == 0;
}

double Calculator::Calculate(element EL, double x, double y) const
{ // 雙目運(yùn)算符的具體運(yùn)算
	int type = EL.type;
    
	if (type > 20 && type < 40) //處理雙目運(yùn)算
   		switch(type)  { // '+' , '-' , '*' , '/' , '^'
   		case OPTR_ADD : return ( x + y ); 
   		case OPTR_SUBTRACT : return ( x - y ); 
   		case OPTR_MULTIPLY : return ( x * y ); 
   		case OPTR_DIVIDE : 
			if (y == 0.0) 
				Error(ERR_DEVIDE_BY_ZERO, __LINE__);
   			else
				return ( x / y );
    		break;
		case OPTR_POWER : return (pow( x, y));
		default : Error(ERR_INVALID_OPERATOR, __LINE__); return 0.0;
		}
    else {
		Error(ERR_INVALID_OPERATOR, __LINE__); 
		return 0.0;
    }
	return 0.0;
}

double Calculator::Calculate(element EL, double x) const
{// 單目運(yùn)算符的具體運(yùn)算
    static double (*fun[])(double)={sin, cos, tan, sqrt, 
		log10, log, cot, fabs, floor, asin, acos, atan, sinh,
		cosh, tanh, exp, sqrt}; //*fname[]對(duì)應(yīng)的C函數(shù)名,其中cot為自己寫的
	int type = EL.type;

	if (type > 40) { //處理單目運(yùn)算
		switch(type)  {
		case OPTR_MINUS: return -x;
		case OPTR_POSITIVE: return  x;
		}
		if(type>50) //函數(shù)運(yùn)算
			return ((*fun[type-51])(x));
		else {
			Error(ERR_INVALID_OPERATOR, __LINE__); return 0.0;
		}
	}
	else {
		Error(ERR_INVALID_OPERATOR, __LINE__); return 0.0;
	}
	return 0.0;
}


bool Calculator::Compute(void)
{ // 后綴表達(dá)式求值
    int i, l, type;
	double x, y, r;
    element EL;
	Stack<double> ST; //Stack to operands
    Queue<element> postfix(PO); // 將PO復(fù)制到postfix

    ST.Clear();
    l = postfix.GetLength();

    for (i = 0; i < l; i++) { //逆波蘭表達(dá)式求值
    	EL = postfix.Delete();
    	type = EL.type;
    	
		if (type < 20) { // 操作數(shù)直接壓棧
    		if (type == 0) // 壓入數(shù)字
    		  ST.Push(EL.value);
    		else // 壓入變量
    		  ST.Push(Vars[type-1]);
			continue;
    	}

		if (type > 40) { // 單目操作符
			x = ST.Pop();
			r = Calculate(EL, x);
			ST.Push(r);
			continue;
    	}

		if (type > 20 && type < 40) { // 雙目操作符
			y = ST.Pop(); x = ST.Pop();
			r = Calculate(EL, x, y);
			ST.Push(r);
			continue;
    	}
    }

	if(!ST.IsEmpty()) { // 取出最后結(jié)果
		Result = ST.Pop();
		if (ST.IsEmpty())
			return true;
		else {
			Error(ERR_MISS_OPERATOR, __LINE__);
			return false;
		}
	}
	else  
		Error(ERR_UNKNOWN_ERROR, __LINE__);
	return false;
}


void Calculator::Test(void)
{ // 測(cè)試計(jì)算器的功能
	int i, nv;
	int errid;
	char buf[1000];
	const char *name;
	const char *pch;
	double varsfrom[MaxNumber_of_Variable], var;
	
	cout << "Input a expression: "<<endl;
	//cin.getline(buf, sizeof(buf));
	fgets(buf, sizeof(buf), stdin);

	if(!Input(buf)) {
		errid = GetErrorID();
		pch = GetErrorMessage(errid);
		cout << endl << "ERROR : " << pch << "\nNear Line "<< GetErrorLineNo() <<endl;
		return ;
	}
	
	nv = GetNumberOfVariables();
	if (nv > 0) {
		cout << "\nThere seems to be " << nv << 
			" Variable(s) in your expression, please input them :" << endl;
		for(i = 0; i < nv; i++) {
			name = GetVariableName(i);
			cout << "No." << i + 1 << "  " << name << " = ";
			cin >> var;
			varsfrom[i] = var;
		}
		Assign(varsfrom);
	}
	
	if(!Compute()) {
		errid = GetErrorID();
		
		cout << endl << "ERROR : " << GetErrorMessage(errid) << "\nNear Line "<< GetErrorLineNo() << endl;
		return ;
	}

    cout << "Answer: " << GetResult() << endl;
}