OTS/OTSCPP/OTSClassifyEngine/ParticleEngine/MathExpression.cpp

#include "stdafx.h"
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include "MathExpression.h"
namespace expInterpreter {
	const int expr_str_err_N = 5;
	const char *expr_str_err[] =
	{
		"unknown error.",			// error code 0
		"unexcepted end.",			// error code 1
		"operator error.",			// error code 2
		"input data error.",		// error code 3
		"expression too long."		// error code 4
	};

	const int compute_err_N = 5;
	const char *compute_err[] =
	{
		"unknown error.",			// error code 0
		"compute data error.",		// error code 1
		"input data error.",		// error code 2
		"devided by zero.",			// error code 3
		"pow return non."			// error code 4
	};

	// 从字符串的start位置开始读一个元素放入atom，返回结束位置，若解析结束，返回-1
	int read_atom(Atom *atom, const char *exprStr, int start);
	// 从字符串尝试读取一个数字，返回结束位置，若解析结束，返回start
	int read_digit(double *result, const char *exprStr, int start);
	// 判断是否为数字符号
	inline bool isEmpty(char ch);
	// 判断是否为数字符号
	inline bool isDigit(char ch);
	// 判断是否为运算符
	inline bool isSymbol(char ch);
	// 判断是否为变量
	inline bool isVariable(char ch);

	// 获取Atom的字符表示
	char atom_symbol(Atom *atom);

	// 判断符号是否合法
	enum BL { F = 0, T = 1 };	// T true，F false
	BL legel_Atom(Atom *atom1, Atom *atom2);
	BL legel_Atom(char ch1, char ch2);
	enum CR { A = 0, B = 1, D = 2, E = 3 };	// A大于，B小于，D相等，E错误
	// 判断符号优先级
	CR compare_symbol(char ch1, char ch2);

	// 表达式的最大长度
	const int Expression::poland_MAX = 255;

	Expression::Expression()
	{
		this->poland = new Atom[poland_MAX];
		this->poland[0].type = ATOM_END;
		this->poland_N = 0;
		this->var = new double[26];
		for (unsigned int i = 0; i < 26; i++)
		{
			this->var[i] = 1;	// 初始化所有变量为1
		}
	}

	Expression::~Expression()
	{
		delete[] this->poland;
		delete[] this->var;
	}

	int Expression::SetExprStr(const char *exprStr)
	{
		Atom Bak, Now;
		this->poland_N = 0;
		char symbol_stack[poland_MAX];
		int symbol_stack_N = 0;
		symbol_stack[symbol_stack_N++] = '#';
		Bak.type = ATOM_END;
		int index = 0;
		int error_code = 0;
		while (symbol_stack_N)
		{
			if (index < 0)	// 解析式是否结束
			{
				error_code = 1;
				goto error_return;
			}
			index = read_atom(&Now, exprStr, index);
			if (!legel_Atom(&Bak, &Now))	// 判断是否合法
			{
				if (Now.type == ATOM_SYMBOL && Now.value.symbol == '-')	// 尝试一元运算符的多义
				{
					Now.value.symbol = '~';
					if (!legel_Atom(&Bak, &Now))
					{
						error_code = 2;
						goto error_return;
					}
				}
				else
				{
					error_code = 2;
					goto error_return;
				}
			}
			switch (Now.type)	// 根据类别计算
			{
			case ATOM_ERROR:
				error_code = 3;
				goto error_return;
				break;
			case ATOM_SYMBOL:	// 运算符号，包括结束符号
			case ATOM_END:
			{
				bool poped = true;
				char ch = atom_symbol(&Now);
				while (poped)
				{
					switch (compare_symbol(symbol_stack[symbol_stack_N - 1], ch))	// 比较当前运算符和符号栈顶的优先级
					{
					case A:	// 上一个符号优先级高，先完成上一个运算符的运算
						this->poland[this->poland_N].type = ATOM_SYMBOL;
						this->poland[this->poland_N].value.symbol = symbol_stack[symbol_stack_N - 1];
						this->poland_N++;
						if (this->poland_N >= poland_MAX)
						{
							error_code = 4;
							goto error_return;
						}
						symbol_stack_N--;
						poped = true;
						break;
					case B:	// 这次的优先级高，则压入符号栈，等待处理
						symbol_stack[symbol_stack_N++] = ch;
						poped = false;
						break;
					case D:	// 优先级相等，例如'('和')'，同时弹出
						symbol_stack_N--;
						poped = false;
						break;
					case E:	// 优先级出错
						error_code = 2;
						goto error_return;
					}
				}
			}
			break;
			case ATOM_CONSTANT:	// 变量或常量，自己压入逆波兰式
			case ATOM_VARIABLE:
				this->poland[this->poland_N++] = Now;
				if (this->poland_N >= poland_MAX)
				{
					error_code = 4;
					goto error_return;
				}
				break;
			}
			Bak = Now;
		}
		this->poland[this->poland_N].type = ATOM_END;
		return 0;
	error_return:
		return error_code;
	}

	const char *Expression::GetExprErrorStr(int err)
	{
		return err < 1 ?
			expr_str_err[0] :
			err >= expr_str_err_N ?
			expr_str_err[0] :
			expr_str_err[err];
	}

	const char *Expression::GetResultErrorStr(int err)
	{
		return err < 1 ?
			compute_err[0] :
			err >= compute_err_N ?
			compute_err[0] :
			compute_err[err];
	}

	void Expression::SetVar(char x, double value)
	{
		if (!isVariable(x)) return;
		x |= 0x20;					// 将变量转换为小写
		this->var[x - 'a'] = value;
	}

	int Expression::GetResult(double *result)
	{
		double digit[poland_MAX];	// 逆波兰式的辅助堆栈
		int digit_N = 0;
		int index = 0;
		int error_code = 0;

		for (index = 0; index < this->poland_N; index++)
		{
			switch (this->poland[index].type)
			{
			case ATOM_ERROR:
				error_code = 2;
				goto error_return;
				break;
			case ATOM_SYMBOL:
				switch (this->poland[index].value.symbol)
				{
				case '+':
					if (digit_N < 2)
					{
						error_code = 1;
						goto error_return;
					}
					digit[digit_N - 2] = digit[digit_N - 2] + digit[digit_N - 1];
					digit_N--;
					break;
				case '-':
					if (digit_N < 2)
					{
						error_code = 1;
						goto error_return;
					}
					digit[digit_N - 2] = digit[digit_N - 2] - digit[digit_N - 1];
					digit_N--;
					break;
				case '*':
					if (digit_N < 2)
					{
						error_code = 1;
						goto error_return;
					}
					digit[digit_N - 2] = digit[digit_N - 2] * digit[digit_N - 1];
					digit_N--;
					break;
				case '/':
					if (digit_N < 2)
					{
						error_code = 1;
						goto error_return;
					}
					digit[digit_N - 2] = digit[digit_N - 2] / digit[digit_N - 1];
					digit_N--;
					if (!_finite(digit[digit_N - 1]))
					{
						error_code = 3;
						goto error_return;
					}
					break;
				case '^':
					if (digit_N < 2)
					{
						error_code = 1;
						goto error_return;
					}
					digit[digit_N - 2] = pow(digit[digit_N - 2], digit[digit_N - 1]);
					digit_N--;
					if (_isnan(digit[digit_N - 1]))
					{
						error_code = 4;
						goto error_return;
					}
					break;
				case '~':
					if (digit_N < 1)
					{
						error_code = 1;
						goto error_return;
					}
					digit[digit_N - 1] = -digit[digit_N - 1];
					break;
				}
				break;
			case ATOM_CONSTANT:
				digit[digit_N++] = this->poland[index].value.constant;
				break;
			case ATOM_VARIABLE:
				digit[digit_N++] = this->var[this->poland[index].value.variable - 'a'];
				break;
			case ATOM_END:
				break;
			}
		}

		if (digit_N != 1)
		{
			error_code = 1;
			goto error_return;
		}
		else
		{
			*result = digit[0];
			return 0;
		}

	error_return:
		return error_code;
	}

	const Atom *Expression::GetPoland()
	{
		return this->poland;
	}

	// 兼容矩阵
	BL legel_matrix[10][10] =
	{
		//	+	-	*	/	^	(	)	i	~	#
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// +
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// -
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// *
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// /
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// ^
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// (
			T,	T,	T,	T,	T,	F,	T,	F,	F,	T,	// )
			T,	T,	T,	T,	T,	F,	T,	F,	F,	T,	// i
			F,	F,	F,	F,	F,	T,	F,	T,	F,	F,	// ~
			F,	F,	F,	F,	F,	T,	F,	T,	T,	F,	// #
	};

	// 兼容矩阵下标值
	char legel_matrix_ch[10] = { '+', '-', '*', '/', '^', '(', ')', 'i', '~', '#', };

	// 优先级矩阵
	CR cmp_matrix[9][9] =
	{
		//	+	-	*	/	^	(	)	~	#
			A,	A,	B,	B,	B,	B,	A,	B,	A,	// +
			A,	A,	B,	B,	B,	B,	A,	B,	A,	// -
			A,	A,	A,	A,	B,	B,	A,	B,	A,	// *
			A,	A,	A,	A,	B,	B,	A,	B,	A,	// /
			A,	A,	A,	A,	A,	B,	A,	B,	A,	// ^
			B,	B,	B,	B,	B,	B,	D,	B,	E,	// (
			E,	E,	E,	E,	E,	E,	E,	E,	E,	// )
			A,	A,	A,	A,	A,	B,	A,	A,	A,	// ~
			B,	B,	B,	B,	B,	B,	E,	B,	D,	// #
	};

	// 优先级矩阵下标值
	char cmp_matrix_ch[9] = { '+', '-', '*', '/', '^', '(', ')', '~', '#', };

	BL legel_Atom(char ch1, char ch2)
	{
		int index1 = 0;
		while (legel_matrix_ch[index1] != ch1 && index1 < 10) index1++;
		if (index1 == 10) return F;
		int index2 = 0;
		while (legel_matrix_ch[index2] != ch2 && index2 < 10) index2++;
		if (index2 == 10) return F;
		return legel_matrix[index1][index2];
	}

	char atom_symbol(Atom *atom)
	{
		switch (atom->type)
		{
		case ATOM_ERROR:
			return -1;
		case ATOM_SYMBOL:
			return atom->value.symbol;
		case ATOM_CONSTANT:
		case ATOM_VARIABLE:
			return 'i';
		case ATOM_END:
			return '#';
		}
		return -1;
	}

	BL legel_Atom(Atom *atom1, Atom *atom2)
	{
		char ch1 = atom_symbol(atom1);
		if (ch1 < 0) return F;
		char ch2 = atom_symbol(atom2);
		if (ch2 < 0) return F;
		return legel_Atom(ch1, ch2);
	}
	CR compare_symbol(char ch1, char ch2)
	{
		int index1 = 0;
		while (cmp_matrix_ch[index1] != ch1 && index1 < 9) index1++;
		if (index1 == 9) return E;
		int index2 = 0;
		while (cmp_matrix_ch[index2] != ch2 && index2 < 9) index2++;
		if (index2 == 9) return E;
		return cmp_matrix[index1][index2];
	}

	int read_atom(Atom *atom, const char *exprStr, int start)
	{
		while (isEmpty(exprStr[start])) start++;
		if (exprStr[start] == '\0')
		{
			atom->type = ATOM_END;
			return -1;
		}
		if (isVariable(exprStr[start]))
		{
			atom->type = ATOM_VARIABLE;
			atom->value.variable = exprStr[start] | 0x20;	// 变量长度只为1，转换为小写
			start++;
		}
		else if (isSymbol(exprStr[start]))
		{
			atom->type = ATOM_SYMBOL;
			atom->value.symbol = exprStr[start];
			start++;
		}
		else if (isDigit(exprStr[start]))	// 是数字时，调用库函数读入一个实数
		{
			double digit;
			start = read_digit(&digit, exprStr, start);
			atom->type = ATOM_CONSTANT;
			atom->value.constant = digit;
		}
		else
		{
			atom->type = ATOM_ERROR;
			start++;
		}
		return start;
	}

	int read_digit(double *result, const char *exprStr, int start)	// 利用库函数读入一个实数
	{
		int len = 0;
		while (isDigit(exprStr[start + len])) len++;
		*result = atof(exprStr + start);
		start += len;
		return start;
	}

	inline bool isEmpty(char ch)
	{
		return (ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n');
	}

	inline bool isDigit(char ch)
	{
		return (ch == '.' || (ch >= '0' && ch <= '9'));
	}

	const int sml_N = 7;
	const char sml[] = { '+', '-', '*', '/', '^', '(', ')' };

	inline bool isSymbol(char ch)
	{
		for (unsigned int i = 0; i < sml_N; i++)
		{
			if (ch == sml[i])
				return true;
		}
		return false;
	}

	inline bool isVariable(char ch)
	{
		return ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'));
	}
}