expression.cpp

能计算如下表达式：x=3 y=4 z=x^2+sin(y)

//unit expression Parser;
/*==========================================================================*/
/* Expression Evaluator v2.0                                                */
/* suport: +, -, *, /, ^, (), sin, cos, tan, asin, acos, atan, sinh, cosh,  */
/*           tanh, exp, ln/log, log10, sqr, trunc                           */
/*                                              11/2003 by wangjian/ZJU     */
/*==========================================================================*/
#include ".\expression.h"




void Expression::setExpression(string exp)
{	
	expression = exp;
	if(!idMap.empty()) idMap.clear();
}


/////////////////////////////////////////////
/////////////**词法分析程序**////////////////
/////////////////////////////////////////////
void Expression::lex(void)
{
	unsigned int position =0;//记录词法分析位置
	unsigned int tLen;//位置游标
	char ch;//记录当前字符
	Token tok;
	parseSucc = true; //清除编译错误标记
	if(expression.empty()) 
	{ 
		parseSucc = false;
		resultStr = "表达式为空字符串!";
	}
	while (position < expression.length() && parseSucc)
	{	
		//去空格并读取当前字符
		while (position < expression.length() && expression[position] == ' ') position++;
		ch = expression[position];

		//   如果 ch 在 ['0'..'9', '.']中，接受数字
		if((ch >= '0' && ch <= '9') || ch == '.')
		{
			string numString = "";
			tLen = position;
			bool decimal = false;

			while ((tLen < expression.length()) &&
				((expression[tLen] >= '0' && expression[tLen]  <= '9' ) ||
				(expression[tLen]  == '.' && !decimal))) 
			{
				numString = numString + expression[tLen];
				if (expression[tLen] == '.')	decimal = true;
				tLen++;
			}

			if (tLen < expression.length() && expression[tLen] == 'E'
				&&(expression[tLen+1] == '+'||expression[tLen+1] == '-')
				&& (expression[tLen+2] >= '0' && expression[tLen+2]  <= '9' ))
			{//如果是E指数形式
				numString = numString + 'E' + expression[tLen+1];
				tLen +=2;

				int numLen = 1;//记录E指数的长度
				while (tLen < expression.length() &&
					(expression[tLen] >= '0' && expression[tLen]  <= '9' ) && 
					numLen <=MaxExpLen)
				{
					numString = numString + expression[tLen];
					numLen++;
					tLen++;
				}
			}

			if (numString[0] == '.') numString = '0' + numString;

			tok =Token(position, NUM, atof(numString.c_str()),"");
			tokenQue.push_back(tok);
			position = tLen;
		}


		//如果ch在[a,z]或[A,Z]或'_'内,接受变量或函数
		else if ((ch>='a' && ch <= 'z') || (ch>='A' && ch <= 'Z'))
		{	
			string str;
			tLen = position;
			str = str + expression[tLen];
			tLen++;

			while (tLen < expression.length() &&
				((expression[tLen] >= '0' && expression[tLen]  <= '9' ) ||
				(expression[tLen] >='a' && expression[tLen] <= 'z') || 
				(expression[tLen]>='A' && expression[tLen] <= 'Z'))) 
			{
				str = str + expression[tLen];
				tLen++;
			}
			
			//如果是函数,则...
			if(str =="abs"|| str =="sin" || str =="cos"  || str =="tan" || str =="lg"||				str =="asin" || str =="acos"  || str =="atan" || str =="sinh" || 
				str =="cosh"  || str =="tanh" || str =="exp" || str =="ln" || 
				str =="trunc" || str =="sqr" || str =="log10" || str =="log")
			{
				tok =Token(position, FUNC, 0,str);
				tokenQue.push_back(tok);
			}
			
			//如果是圆周率pi,则...
			else if(str == "pi" || str == "Pi" || str == "pI" || str == "PI")
			{
				tok =Token(position, NUM, 3.1415926535,"");
				tokenQue.push_back(tok);
			}
			
			//否则为标识符.
			else{
				tok =Token(position, ID, 0,str);
				tokenQue.push_back(tok);				
			}
			position = tLen;
		}

		//如果ch在{+ - * / ^ ! = ; ( ) }
		else
		{
			switch(ch) {
			case '+': tok =Token(position,PLUS,0,"");
				tokenQue.push_back(tok);
				break;
			case '-': tok =Token(position,MINUS,0,"");
				tokenQue.push_back(tok);
				break;
			case '*': tok =Token(position,TIMES,0,"");
				tokenQue.push_back(tok);
				break;			
			case '/': tok =Token(position,DIVIDE,0,"");
				tokenQue.push_back(tok);
				break;	
			case '^': tok =Token(position,EXPO,0,"");
				tokenQue.push_back(tok);
				break;			
			case '(': tok =Token(position,OPAREN,0,"");
				tokenQue.push_back(tok);
				break;			
			case ')': tok =Token(position,CPAREN,0,"");
				tokenQue.push_back(tok);
				break;			
			case '=': tok =Token(position,EQU,0,"");
				tokenQue.push_back(tok);
				break;			
			case ';': tok =Token(position,SEMI,0,"");
				tokenQue.push_back(tok);
				break;
			default: //出现非法字符,产生错误信息
				tok =Token(position,BAD,0,"");
				tokenQue.push_back(tok);
				parseSucc = false;
				ostringstream buf;
				buf <<"在表达式的第" <<position+1 <<"个字符处出现了非法字符:  "
					<<expression[position];
				resultStr = buf.str();
			}
			position++;
		}
	}
}


///////////////////////////////////////////////
/////////////**计算表达式程序**////////////////
///////////////////////////////////////////////
void Expression::parse()
{
	bool accepted = true;
	stack<Token> tokenStack;
	TokenTypes currTokTypes;
	Token t1(0,BAD,0,""),t2(0,EOL,0,"");
	Token currTok;
	lex();
	
	if(parseSucc)
	{
		currTok = tokenQue.front();
		currTokTypes = currTok.type;

		//初始化堆栈和单词队列
		tokenStack.push(t1);
		if(tokenQue.back().type == SEMI) tokenQue.pop_back();
		tokenQue.push_back(t2);
	}
	
	//解析表达式
	while(accepted && parseSucc)
	{
		int lr = action[tokenStack.top().state][currTok.type];
		if(lr == -1)
		{//语法错误
			ostringstream buf;
			if(currTok.type == EOL) buf<<"表达式非法结束,可能缺少括号 ),或以操作符+,*,^,(等结尾.";
			else buf <<"在表达式的第" <<currTok.position+1 <<"个字符处出现了不合语法的符号:  "
						<<typetable[currTokTypes];
			resultStr = buf.str();
			parseSucc = false;
		}

		else if(lr<200 && lr>=100)
		{//移进shift(lr-10);
			currTok.state = lr-100;
			tokenStack.push(currTok);
			tokenQue.pop_front();
			currTok = tokenQue.front();
			currTokTypes = currTok.type;
		}

		else if (lr>=200 &&lr<300) 
		{//规约reduce(lr-200);
			switch(lr)
			{//S' -> S
			case 200://A -> E
				{	
					currTok = tokenStack.top();	
					tokenStack.pop();
					currTok.type = A;
					currTok.str = "ans";
					idMap[currTok.str] = currTok.value;
					break;
				}
			case 202://S -> S;A
				{
					currTok = tokenStack.top();	
					tokenStack.pop();
					tokenStack.pop();
					tokenStack.pop();
					currTok.type = S;
					break;
				}
			case 203://S -> A
				{				
					currTok = tokenStack.top();
					tokenStack.pop();
					currTok.type = S;
					break;
				}
			case 204://A -> ID=E
				{	
					t1 = tokenStack.top();	
					tokenStack.pop();
					tokenStack.pop();
					currTok = tokenStack.top();	
					tokenStack.pop();
					currTok.value = t1.value;
					currTok.position = t1.position;
					idMap[currTok.str] = currTok.value;
					currTok.type = A;
					break;
				}
			case 205://E -> E+T
				{				
					currTok = tokenStack.top();
					tokenStack.pop(); tokenStack.pop();
					t1 = tokenStack.top();
					tokenStack.pop();
					currTok.value = t1.value + currTok.value;
					currTok.type = E;
					break;
				}
			case 206://E -> E-T
				{		
					currTok = tokenStack.top();
					tokenStack.pop(); tokenStack.pop();
					t1 = tokenStack.top();
					tokenStack.pop();
					currTok.value = t1.value - currTok.value;
					currTok.type = E;
					break;
				}
			case 207://E -> T
				{				
					currTok = tokenStack.top();