kernel.cpp

计数器的算法 是一个小程序

//Kernel.cpp

///////////////////////////includes//////////////////////////////////

#include "stdafx.h"
#include "Kernel.h"
#include "Header.h"

#include <stdlib.h>
#include <cmath>
#include <string>

//////////////////////////definitions/////////////////////////////////

stack	stData,		//数据栈
	stOperator;	//算符栈

/*//////////////////////::g_initStack/////////////////////////////////

  描述:		初始化一个stack

  行为:		- 将pStack所有可用元素位置的值归零
		- pStack元素计数归零

*/////////////////////////////////////////////////////////////////////
int g_initStack(stack* pStack)
{
	memset(pStack->cData, 0, sizeof(char) * MAX_DATA_NUM);
	pStack->iPos = 0;
	return 0;
}
/*/////////////////////////::g_push///////////////////////////////////

  描述:		将一个数据写入stack栈

  行为:		- 将pStack新元素位置的值写为cData
		- pStack的元素计数加一

  注意:		- 如果该栈已满, 无法写入新值, 则返回-1

*/////////////////////////////////////////////////////////////////////
int g_push(stack* pStack, char cData)
{
	//防止下标越界
	if(pStack->iPos > MAX_DATA_NUM)
		return -1;

	pStack->cData[pStack->iPos] = cData;
	pStack->iPos++;
	return pStack->iPos;
}
/*//////////////////////////::g_pop///////////////////////////////////

  描述:		弹出一个stack结构的栈顶元素

  行为:		- 将pStack栈顶元素位置的值归零
		- pStack的元素计数减一

  注意:		- 如果该栈为空, 返回-1

*/////////////////////////////////////////////////////////////////////
int g_pop(stack* pStack)
{
	//同上
	if(!pStack->iPos)
		return -1;
	
	pStack->iPos--;
	pStack->cData[pStack->iPos] = 0;

	return pStack->iPos;
}
/*//////////////////////////::g_get///////////////////////////////////

  描述:		取得一个stack结构的栈顶元素

  行为:		- 将pStack的栈顶元素写入pValue
		- 返回0

  注意:		- 如果该栈为空, 则将pValue写为NULL, 并返回-1

*/////////////////////////////////////////////////////////////////////
int g_get(stack* pStack, char* pValue)
{
	if(!(pStack->iPos))
	{
		pValue = NULL;
		return -1;
	}

	if(pValue)
		*pValue = pStack->cData[pStack->iPos - 1];

	return 0;
}
/*////////////////////////::g_priority////////////////////////////////

  描述:		取得某字符的数学优先级

  行为:		- 传入一个数学字符
		- 返回其数学优先级

  注意:		- "!"操作符直接写入表达式, 不需要计算优先级	
		- 合法字符包括 + - * / ^ A S C ( [ {
		- 传入其它的字符将返回0
		- 左括号的优先级为0

*/////////////////////////////////////////////////////////////////////
int g_priority(char c)
{

	//左括号属于以下的"else", 优先级为0
	if(c == '+' || c == '-')
		return 1;
	else if(c == '*' || c == '/' || c == '^')
		return 2;
	else if(c == 'A' || c == 'S' || c == 'C')
		return 3;
	else
		return 0;
}
/*/////////////////////////::g_Parse//////////////////////////////////

  描述:		解析用户输入, 调用计算模块返回结果

  行为:		- 传入用户输入的字符串
		- 将其转换为后缀表达式
		- 调用g_Calc计算结果, 写入pValue
		- 返回R_OK

  注意:		- 任何的错误(包括计算模块中的错误)将导致返回非0值
		  可以通过返回值获取错误信息(详见"Kernel.h")

*/////////////////////////////////////////////////////////////////////
int g_Parse(char* szText, float* pValue)
{

	char c = 1,		//当前符号
	     cLast = c,		//上一个符号
	     cPop;		//栈顶元素符号
	int i = 0;
	int pri = 0;		//当前符号优先级
	int pri2 = 0;		//栈顶元素优先级

	g_initStack(&stData);
	g_initStack(&stOperator);

	//预先处理首数为负的情况, e.g. "-3*2"调整为"(0-3)*2"
	if(c = *szText, c == '-')
	{
		g_push(&stData, '0');
		g_push(&stData, ' ');
	}

	c = 1;

	//逐字符解析中缀表达式, 并转换成后缀表达式写入stData
	while(c = szText[i], c != '\0')
	{

		if(g_get(&stOperator, &cPop) == -1)	//取得符号栈顶元素
			cPop = 0;

		if(c == 32)
		{
			;				//跳过空格
		}
		else if((c >= 48 && c < 58) || c == 46)	//数字或小数点, 压入stData
		{
			if((cLast >= 48 && cLast < 58) || cLast == 46)
				g_push(&stData, c);
			else
			{
				g_push(&stData, 32);
				g_push(&stData, c);
			}
		}
		else
		{
			//一元算符
			if(c == '!')
			{
				g_push(&stData, '!');
			}
			else	//左括号算符
			if(c == '(')
			{
				g_push(&stOperator, c);
			}
			else	//同上
			if(c == '[')
			{
				g_push(&stOperator, c);
			}
			else	//同上
			if(c == '{')
			{
				g_push(&stOperator, c);			
			}
			else	//右括号算符
			if(c == ')')
			{
				while(cPop != '(')	//括号中的所有已入栈符号出栈
				{
					g_push(&stData, cPop);
					g_pop(&stOperator);
					g_get(&stOperator, &cPop);
				}

				g_pop(&stOperator);	//左括号出栈
			}
			else	//同上
			if(c == ']')
			{
				while(cPop != '[')
				{
					g_push(&stData, cPop);
					g_pop(&stOperator);
					g_get(&stOperator, &cPop);
				}
				
				g_pop(&stOperator);				
			}
			else	//同上
			if(c == '}')
			{
				while(cPop != '{')
				{
					g_push(&stData, cPop);
					g_pop(&stOperator);
					g_get(&stOperator, &cPop);
				}

				g_pop(&stOperator);
			}
			else	//其它算符(二元, 函数)
			if(c == '+' || c == '-' || c == '*' || c == '/' ||
			   c == '^' || c == 'A' || c == 'C' || c == 'S' ||
			   c == '(' || c == '[' || c == '{' )
			{
				pri = g_priority(c);			//当前符号优先级
				pri2 = g_priority(cPop);		//符号栈顶元素优先级


				//当前符号优先级小或者相等: 栈顶元素写入入表达式并出栈, 
				//当前符号继续与新的栈顶元素比较直到优先级大于栈顶元素 
				while(pri <= pri2)
				{
					g_push(&stData, cPop);
					g_pop(&stOperator);
					if(g_get(&stOperator, &cPop) == -1)
						cPop = 0;;
					pri2 = g_priority(cPop);
				}
				
				if(c == '-' && cLast == '(')	//如果是负数, 
				{				//插入一个空格和'0'
					g_push(&stData, 32);
					g_push(&stData, '0');
				}
				g_push(&stOperator, c);
			}
			else	//非法字符
			{
				::MessageBox(hWnd, "不合法的表达式", "非法字符", MB_OK);
				return -1;
			}

		}//else

		cLast = c;
		i++;
	}//while

	//符号栈中剩余的所有元素追加入后缀表达式, 并清空符号栈
	while(!g_get(&stOperator, &c))
	{
		g_push(&stData, c);
		g_pop(&stOperator);

	}

	//计算出后缀表达式的值并传给pValue
	g_Calc(stData.cData, pValue);
/*
	char buffer[32];
	
	sprintf(buffer, "%f", *pValue);

	::SetWindowText(hEdit, buffer);
	::SetWindowText(hEdit, stData.cData);
*/
	return R_OK;
}
/*/////////////////////////::g_Calc///////////////////////////////////

  描述:		计算一个后缀表达式的结果

  行为:		- 传入一个后缀表达式
		- 计算出结果写入pValue

  注意:		- 任何的错误(包括计算模块中的错误)将导致返回非0值
		  可以通过返回值获取错误信息(详见"Kernel.h")

*/////////////////////////////////////////////////////////////////////
int g_Calc(char* pPostfix, float* pValue)
{
	RESULT	r = R_OK;

	float	pbuffer[MAX_DATA_NUM];
	int	ibufnum = 0;
	char	c = 0, 
		c2 = c;
	int	i=1, 
		j=0;
	bool	bReset = false;		//fbuffer是否被重置. 如果为true, 将不会把fbuffer入栈
					//直到被设为false. 
					//此举是为防止后缀式中多余的空格导致pbuffer错误压栈
	float	fbuffer = 0;
	int	ipt	= 0,		//记录当前字符为小数点后多少位
		ibuffer = 0;		//一次性纸杯(即插即用 && 即用即弃^-^)

	memset(pbuffer, 0, sizeof(float) * MAX_DATA_NUM);

	while(c = pPostfix[i], c)
	{
		if(c >= 48 && c < 58)
		{
			bReset = false;
			if(!ipt)	//整数部分
				fbuffer = fbuffer * 10 + c - '0';
			else		//小数部分
			{
				fbuffer += (float)(c - '0') / ipt;
				ipt *= 10;
			}
		}
		else if(c == '.')
		{
			bReset = false;
			ipt = 10;
		}
		else
		{
			if(!bReset)
			{
				pbuffer[ibufnum] = fbuffer;	//写入数
				if(++ibufnum == MAX_DATA_NUM)	//下标增加
					return -1;
			}
			fbuffer = 0;			//清空缓存(以存放新数)
			ipt = 0;

			bReset = true;	//标志重置
			

			if(c == 32)
			{
				;
			}
			else
			{
				if(c == '!')	//一元算符阶乘, 弹出栈顶数做阶乘, 结果入栈
				{
					//借用fbuffer
					fbuffer = pbuffer[ibufnum - 1];

					//阶乘
					ibuffer = 0;
					if(r = g_Factorial((int)fbuffer, &ibuffer), r)
						return r;	//发生错误, 返回错误码
					pbuffer[ibufnum - 1] = ibuffer;

					fbuffer = 0;
				}
				else if(c == '+')	//二元算符, 弹出栈顶的两个数, 
				{			//相加并将结果入栈
					ibufnum--;
					pbuffer[ibufnum - 1] = 
						pbuffer[ibufnum - 1] + pbuffer[ibufnum];
					pbuffer[ibufnum] = 0;
				}
				else if(c == '-')
				{
					ibufnum--;
					pbuffer[ibufnum - 1] = 
						pbuffer[ibufnum - 1] - pbuffer[ibufnum];
					pbuffer[ibufnum] = 0;
				}
				else if(c == '*')
				{
					ibufnum--;
					pbuffer[ibufnum - 1] = 
						pbuffer[ibufnum - 1] * pbuffer[ibufnum];
					pbuffer[ibufnum] = 0;				
				}
				else if(c == '/')
				{
					ibufnum--;
					pbuffer[ibufnum - 1] = 
						pbuffer[ibufnum - 1] / pbuffer[ibufnum];
					pbuffer[ibufnum] = 0;				
				}
				else if(c == '^')	//乘方
				{
					ibufnum--;
					fbuffer = pbuffer[ibufnum - 1];	//借用fbuffer
									//保存乘方的底数

					//以下循环中j=0会导致多乘一次, 所以起始为1
					for(j=1; j < pbuffer[ibufnum]; j++)	
						pbuffer[ibufnum - 1] *= fbuffer; 
										
					pbuffer[ibufnum] = 0;	
					
					fbuffer = 0;
				}
				else if(c == 'S')	//平方根, 一元算符
				{
					//借用fbuffer
					fbuffer = pbuffer[ibufnum - 1];

					if(r = g_Extract(fbuffer, &pbuffer[ibufnum - 1]), r)
						return r;

					fbuffer = 0;
				}
				else if(c == 'A')	//排列, 二元算符
				{
					ibufnum--;

					if(r = g_Permutation((int)pbuffer[ibufnum - 1],
							     (int)pbuffer[ibufnum], 
							     &ibuffer), r)
						return r;

					pbuffer[ibufnum - 1] = (float)ibuffer;
					
					pbuffer[ibufnum] = 0;
				}
				else if(c == 'C')	//组合, 二元算符
				{
					ibufnum--;

					if(r = g_Combination((int)pbuffer[ibufnum - 1],
							     (int)pbuffer[ibufnum], 
							     &ibuffer), r)
						return r;

					pbuffer[ibufnum - 1] = (float)ibuffer;
					
					pbuffer[ibufnum] = 0;
					
				}
				else
				{
					return R_UNKNOWNCHAR;
				}
			}//else
		}//else

		c2 = c;
		i++;
	}//while
	
	*pValue = pbuffer[ibufnum - 1];

	return 0;
}
/*///////////////////////::g_Factorial////////////////////////////////

  描述:		被g_Calc调用, 计算一个数的阶乘值

  行为:		- 传入一个非负整数
		- 计算出阶乘结果并写入pValue

  注意:		- 任何的错误(包括计算模块中的错误)将导致返回非0值
		  可以通过返回值获取错误信息(详见"Kernel.h")

*/////////////////////////////////////////////////////////////////////
RESULT g_Factorial(int n, int* pValue)
{
	if(!pValue)
		return R_NULLPTR;

	if(n < 0)
		return R_F_MINUS;

	RESULT r = R_OK;

	if(n == 1 || !n)
	{
		*pValue = 1;
		return R_OK;
	}

	if(r = g_Factorial(n - 1, pValue), r)
		return r;

	*pValue *= n;

	return R_OK;
}
/*//////////////////////::g_Permutation///////////////////////////////

  描述:		被g_Calc调用, 计算一个排列的结果

  行为:		- 传入进行排列的两个参数
		- 计算出排列结果并写入pValue

  注意:		- 任何的错误(包括计算模块中的错误)将导致返回非0值
		  可以通过返回值获取错误信息(详见"Kernel.h")

*/////////////////////////////////////////////////////////////////////
RESULT g_Permutation(int X, int n, int* pValue)
{
	if(!pValue)
		return R_NULLPTR;

	if(X <= 0)
		return R_P_MINUS1;
	else if(n <= 0)
		return R_P_MINUS2;
	else if(X < n)
		return R_P_LESS;

	RESULT r = R_OK;
	int i = 0;

	int value1 = 0,
	    value2 = 0;

	*pValue = X;
	for(i = X - 1; i > X - n; i--)
		*pValue *= i;

	return R_OK;
}
/*//////////////////////::g_Combination///////////////////////////////

  描述:		被g_Calc调用, 计算一个组合的结果

  行为:		- 传入进行组合的两个参数
		- 计算出组合结果并写入pValue

  注意:		- 任何的错误(包括计算模块中的错误)将导致返回非0值
		  可以通过返回值获取错误信息(详见"Kernel.h")

*/////////////////////////////////////////////////////////////////////
RESULT g_Combination(int X, int n, int* pValue)
{
	if(!pValue)
		return R_NULLPTR;

	if(X <= 0)
		return R_C_MINUS1;
	else if(n <= 0)
		return R_C_MINUS2;
	else if(X < n)
		return R_C_LESS;

	RESULT r = R_OK;

	if(n > (X >> 1))	//e.g. C(9,6)转换为C(9,3)
		n = X - n;

	int value1 = X,
	    value2 = n;

	int i = 0;

	for(i = 1; i < n; i++)
	{
		value1 *= X - i;
		value2 *= n - i;
	}

	*pValue = value1 / value2;
	return R_OK;
}
/*////////////////////////::g_Extract/////////////////////////////////

  描述:		被g_Calc调用, 计算一个数的平方根

  行为:		- 传入一个非负底数
		- 计算出平方根并写入pValue

  注意:		- 任何的错误(包括计算模块中的错误)将导致返回非0值
		  可以通过返回值获取错误信息(详见"Kernel.h")

*/////////////////////////////////////////////////////////////////////
RESULT g_Extract(float A, float* pValue)
{
	if(!pValue)
		return R_NULLPTR;

	if(A < 0)
		return R_E_MINUS;

	*pValue = sqrt(A);

	return R_OK;
}