gisexpression.cpp

此程序实现了表达式求值

	此为表达式求值的核心算法
*/
int CGisExpression::MidToPostfix()
{
	if(!VerifyExpression())
		return 0;

	if(m_bPostfix)//已经转换过了
		return 1;

	m_postfix.clear();

	TCHAR buf[MAX_BUF];
	TStack<COpPri> stack;
	int pos = 0; 
	while(pos >= 0)
	{
		pos = Divide(buf, MAX_BUF, pos);
		if(0 == lstrcmp(buf, _T("")))
			continue;

		if(IsOperator(buf))
		{
			if(buf[0] == ')')
			{
				while(0 != lstrcmp(stack.GetTop().name, _T("(")))
				{
					m_postfix.push_back(CSegment(stack.Pop().name));
				}
				stack.Pop();
			}
			else if(!stack.IsEmpty() && 
				GetOperatorPri(buf) <= stack.GetTop().pri &&
				0 != lstrcmp(stack.GetTop().name, _T("(")))
			{
				while(GetOperatorPri(buf) <= stack.GetTop().pri && 
							!stack.IsEmpty() &&
							0 != lstrcmp(stack.GetTop().name, _T("(")))
				{
					m_postfix.push_back(CSegment(stack.Pop().name));
				}

				COpPri op;
				assert(GetOperatorOb(buf, op));
				stack.Push(op);
			}
			else
			{
				COpPri op;
				assert(GetOperatorOb(buf, op));
				stack.Push(op);
			}
		}
		else//if is not operator
		{
			m_postfix.push_back(buf);
		}// end if Isoperator
	}
	while(!stack.IsEmpty())
	{
		m_postfix.push_back(CSegment(stack.Pop().name));
	}

	m_bPostfix = TRUE;

	return 1;
}

/*
	计算表达式的值
	[out]fp - 计算的表达式的值
	返回值：
		0 - 成功
		-3 - 不认识的运算符
		-2 - 转换后的后缀式有误（很可能是输入的中缀式不正确）
		-1 - 变量不存在
*/
int CGisExpression::Calculate(double* pf)
{
	assert(pf != NULL);

	TStack<CSegment> stack;
	vector<CSegment>::iterator it;

	for(it = m_postfix.begin(); it != m_postfix.end(); it++)
	{
		//printf("degug - %s\n", (*it).name);
		if(!IsOperator((*it).name))//如果是操作数（不是操作符）,压栈
		{
			stack.Push(*it);
			//printf("debug - %s\n", (*it).name);
		}
		else if(IsOperator((*it).name[0]))//如果是运算符：如+-，不是函数：如sqrt,sin
		{
			//取得操作数
			CVarType vartemp;//临时变量

			double a = 0.0, b = 0.0;
			int ret = -1;
			int rettemp1 = -1, rettemp2 = -1;
			CSegment temp;

			//取得运算符右边的数据
			temp = stack.Pop();
			if((ret = GetVarValue(temp.name, &b)) != 0)
				return ret;

			//判断取出的数据是否为临时变量
			if((rettemp1 = IsTempVar(temp.name)) >= 0)
			{
				vartemp = m_varList[rettemp1];
			}

			//取得运算符左边的数据
			temp = stack.Pop();
			if((ret = GetVarValue(temp.name, &a)) != 0)
				return ret;

			//判断取出的数据是否为临时变量
			if((rettemp2 = IsTempVar(temp.name)) >= 0)
			{
				vartemp = m_varList[rettemp2];
			}

			//如果两个操作数全不是临时变量则重新生成临时变量。
			if(rettemp1 < 0 && rettemp2 < 0)
			{
				assert(MakeTempVar(vartemp));
				//将临时变量添加到变量列表中
				AddVar(vartemp);
			}

			//
			if(0 == lstrcmp((*it).name, _T("+")))
			{
				a = a + b;
			}
			else if(0 == lstrcmp((*it).name, _T("-")))
			{
				a = a - b;
			}
			else if(0 == lstrcmp((*it).name, _T("*")))
			{
				a = a * b;
			}
			else if(0 == lstrcmp((*it).name, _T("/")))
			{
				a = a / b;
			}
			else if(0 == lstrcmp((*it).name, _T("^")))
			{
				a = pow(a, b);
			}
			else 
			{
				return -3;//永远不可能发生
			}

			//将操作数写入变量中，并且将变量重新压入堆栈
			SetVarValue(vartemp.name, a);
			stack.Push(CSegment(vartemp.name));
		}//
		else//如果是函数操作：如sin cos tan sqrt等
		{
			CVarType vartemp;
			CSegment temp;
			int ret = -1;
			double a = 0.0;

			//取操作数
			temp = stack.Pop();
			if((ret = GetVarValue(temp.name, &a)) != 0)
				return ret;

			//判断是否为临时变量
			if((ret = IsTempVar(temp.name)) >= 0)
			{
				vartemp = m_varList[ret];
			}

			//如果操作数不是临时变量则生成一个新的临时变量
			if(ret < 0)
			{
				assert(MakeTempVar(vartemp));
				//将临时变量添加到变量列表中
				AddVar(vartemp);
			}

			if(0 == lstrcmp((*it).name, _T("sin")))
			{
				a = sin(a);
			}
			else if(0 == lstrcmp((*it).name, _T("cos")))
			{
				a = cos(a);
			}
			else if(0 == lstrcmp((*it).name, _T("tan")))
			{
				a = tan(a);
			}
			else if(0 == lstrcmp((*it).name, _T("sqrt")))
			{
				a = sqrt(a);
			}
			else if(0 == lstrcmp((*it).name, _T("log10")))
			{
				a = log10(a);
			}
			else if(0 == lstrcmp((*it).name, _T("ln")))
			{
				a = log(a);
			}
			else
			{
				return -3;//永远不可能发生
			}

			SetVarValue(vartemp.name, a);
			stack.Push(CSegment(vartemp.name));
		}//endif
	}

	//取结果
	CSegment temp;
	int ret = -1;
	temp = stack.Pop();
	if((ret = GetVarValue(temp.name, pf)) != 0)
		return ret;

	return 0;
}

/*
	注意，添加函数时一定要将flag标志位设置为1
*/
void CGisExpression::SetPRI()
{
	lstrcpy(m_pPri[0].name, _T("+"));
	m_pPri[0].pri = 20;
	m_pPri[0].flag = 0;

	lstrcpy(m_pPri[1].name, _T("-"));
	m_pPri[1].pri = 20;
	m_pPri[1].flag = 0;

	lstrcpy(m_pPri[2].name, _T("*"));
	m_pPri[2].pri = 40;
	m_pPri[2].flag = 0;

	lstrcpy(m_pPri[3].name, _T("/"));
	m_pPri[3].pri = 40;
	m_pPri[3].flag = 0;

	lstrcpy(m_pPri[4].name, _T("^"));//乘方
	m_pPri[4].pri = 60;
	m_pPri[4].flag = 0;

	lstrcpy(m_pPri[5].name, _T("sqrt"));//开方
	m_pPri[5].pri = 80;
	m_pPri[5].flag = 1;

	lstrcpy(m_pPri[6].name, _T("sin"));//
	m_pPri[6].pri = 80;
	m_pPri[6].flag = 1;

	lstrcpy(m_pPri[7].name, _T("cos"));//
	m_pPri[7].pri = 80;
	m_pPri[7].flag = 1;

	lstrcpy(m_pPri[8].name, _T("tan"));//
	m_pPri[8].pri = 80;
	m_pPri[8].flag = 1;

	lstrcpy(m_pPri[9].name, _T("("));//
	m_pPri[9].pri = 200;
	m_pPri[9].flag = 0;

	lstrcpy(m_pPri[10].name, _T(")"));//
	m_pPri[10].pri = 200;
	m_pPri[10].flag = 0;

	lstrcpy(m_pPri[11].name, _T("log10"));//10为底的对数
	m_pPri[11].pri = 80;
	m_pPri[11].flag = 1;

	lstrcpy(m_pPri[12].name, _T("ln"));//自然对数
	m_pPri[12].pri = 80;
	m_pPri[12].flag = 1;

	m_iOperator = 13;
}

/*
	每次返回一个段，比如:234+152分为：234,+,152三段
	pos表示起始点
	返回值为-1表示处理完毕
*/
int CGisExpression::Divide(TCHAR* dest, int length, int pos/*=NULL*/)
{
	assert(m_pExp != NULL && dest != NULL);

	memset(dest, 0, length);

	int len = lstrlen(m_pExp);
	int index = 0;

	if(pos < len && pos >= 0)
	{
		dest[index++] = m_pExp[pos];
		if(IsOperator(m_pExp[pos]))
			return pos+1;
	}

	for(int i = pos + 1; i < len; i++)
	{
		if(IsOperator(m_pExp[i]))
		{
			dest[index] = _T('\0');
			trim(dest);//去掉前后的空格
			return i;
		}
		
		dest[index++] = m_pExp[i];
	}
	dest[index] = _T('\0');
	trim(dest);

	return -1;
}

int CGisExpression::IsOperator(TCHAR ch)
{
	for(int i = 0; i < m_iOperator; i++)
	{
		if(m_pPri[i].flag == 0 && m_pPri[i].name[0] == ch)
			return 1;
	}

	return 0;
}

/*
	判断是否是操作符
*/
int CGisExpression::IsOperator(const TCHAR* str)
{
	if(NULL == str)
		return 0;

	for(int i = 0; i < m_iOperator; i++)
	{
		if(0 == lstrcmp(str, m_pPri[i].name))
			return 1;
	}

	return 0;
}

/*
	取得操作符的优先级
*/
int CGisExpression::GetOperatorPri(const TCHAR* str)
{
	if(NULL == str)
		return -1;

	for(int i = 0; i < m_iOperator; i++)
	{
		if(0 == lstrcmp(str, m_pPri[i].name))
			return m_pPri[i].pri;
	}

	return -1;
}

/*
	取得操作符对象COpPri
*/
int CGisExpression::GetOperatorOb(const TCHAR* str, COpPri& op)
{
	if(NULL == str)
		return 0;

	for(int i = 0; i < m_iOperator; i++)
	{
		if(0 == lstrcmp(str, m_pPri[i].name))
		{
			op = m_pPri[i];
			return 1;
		}
	}

	return 0;
}

int CGisExpression::GetIderCount()
{
	int cnt = 0;
	int pos = 0;
	
	TCHAR buf[MAX_BUF];
	while(pos >= 0)
	{
		pos = Divide(buf, MAX_BUF, pos);
		if(!IsOperator(buf[0]) && (buf[0] != _T('\0')))
			cnt++;
	}

	return cnt;
}

LPTSTR CGisExpression::StrCat(LPTSTR str, TCHAR ch)
{
	TCHAR buf[2];

	buf[0] = ch;
	buf[1] = _T('\0');

	return lstrcat(str, buf);
}