一个符号求导的小程序

本文主要是介绍一个符号求导的小程序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这两天写了一个符号求导的程序，没有任何化简，代码质量比较差。以后可以考虑把每个项coefficient * x^index单独提出来，把coefficient和index单独作为未知数x的属性。

该程序目前只支持多项式求导。

#include<bits/stdc++.h>
using namespace std;
const static int bign = 10033;
enum tokenType
{
	Openbracket = 1, CloseBracket, Variable, ConstVar, OpType
};

typedef pair<int, string> token;
typedef vector<token> tokenlist;
int mapbracket[bign];
int bstack[bign];
int mtop;

inline int getType(char c)
{
	if (c == '(')
	{
		return 1;
	}
	else if (c == ')')
	{
		return 2;
	}
	else if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))
	{
		return 3;
	}
	else if (c >= '0' && c <= '9')
	{
		return 4;
	}
	else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^')
	{
		return 5;
	}
	else if (c == ' ' || c == '\n' || c == ';')
	{
		return 6;
	}
	
}

void LexErrorOccur()
{
	printf("Lexical Error\n");
}

inline int matoi(string &numstr)
{
	int ret = 0;
	for (int i = 0; i < numstr.length(); i++)
	{
		ret = ret * 10 + numstr[i] - '0';
	}
	return ret;
}

inline string tokenToString(tokenlist u,int n1)
{
	string ret = "";
	for (int i = 0; i < n1; i++)
	{
		ret += u[i].second;
	}
	return ret;
}

void LexAnalysis(string& Expr, tokenlist& tlist)
{
	string lasttoken = "";
	int lasttype = 0;
	for (char c : Expr)
	{
		int typec = getType(c);
		if (typec == 1 || typec == 2 || typec == 5 || typec == 6)
		{
			if (lasttype > 0)
			{
				tlist.push_back(make_pair(lasttype, lasttoken));
				lasttype = 0;
				lasttoken = "";
			}
		}

		if (typec == 1 || typec == 2)
		{
			lasttype = typec;
			lasttoken.push_back(c);
			tlist.push_back(make_pair(lasttype, lasttoken));
			lasttype = 0;
			lasttoken = "";
		}
		else
		{
			if (typec == 4)
			{
				if (lasttype != 3)
				{
					lasttype = 4;
				}
				lasttoken.push_back(c);
			}
			else if (typec == 3)
			{
				if (lasttype == 4)
					LexErrorOccur();
				lasttype = 3;
				lasttoken.push_back(c);
			}
			else if (typec == 5)
			{
				lasttype = 5;
				lasttoken.push_back(c);
				tlist.push_back(make_pair(lasttype, lasttoken));
				lasttype = 0;
				lasttoken = "";
			}
		}
	}
	if (lasttype != 0)
	{
		tlist.push_back(make_pair(lasttype, lasttoken));
	}
}

bool testzero(token &u)
{
	if (u.first == tokenType::ConstVar && u.second == "0")
	{
		return true;
	}
	return false;
}

int mDerivative(tokenlist& Expr, int b1, int e1, tokenlist& res, int resb)
{
	assert(b1 >= 0 && b1 <= e1 && e1 <= Expr.size());
	if (b1 == e1)
		return resb;
	//vector<pair<int, string> > ret;
	//ret.push_back(make_pair(0, "+"));
	

	if (e1 - b1 >= 2 && Expr[b1].first == tokenType::Openbracket && Expr[e1 - 1].first == tokenType::CloseBracket && mapbracket[e1 - 1] == b1)
	{
		return mDerivative(Expr, b1 + 1, e1 - 1, res, resb);
	}


	int inbracket = 0;
	for (int i = b1; i < e1; i++)
	{
		if (Expr[i].first == tokenType::OpType)
		{
			char opchar = Expr[i].second[0];
			if ((opchar == '+' || opchar == '-') && inbracket == 0)
			{
				resb = mDerivative(Expr, b1, i, res, resb);

				res[resb++] = make_pair(tokenType::OpType, Expr[i].second);//derivative + & - rule
				resb = mDerivative(Expr, i + 1, e1, res, resb);
				return resb;
			}
		}
		else if (Expr[i].first == tokenType::Openbracket)
		{
			inbracket++;
		}
		else if (Expr[i].first == tokenType::CloseBracket)
		{
			inbracket--;
		}
	}

	for (int i = e1 - 1; i >= b1; i--)
	{
		if (Expr[i].first == tokenType::OpType)
		{
			char opchar = Expr[i].second[0];
			if (opchar == '*' && inbracket == 0) // derivative * rule
			{
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				resb = mDerivative(Expr, b1, i, res, resb);
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "*");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				for (int j = i + 1; j < e1; j++)
				{
					res[resb++] = Expr[j];
				}
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "+");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				for (int j = b1; j < i; j++)
				{
					res[resb++] = Expr[j];
				}
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "*");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				resb = mDerivative(Expr, i + 1, e1, res, resb);
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				return resb;
			}
			if (opchar == '/' && inbracket == 0) //derivative / rule
			{
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				resb = mDerivative(Expr, b1, i, res, resb);
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "*");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				for (int j = i + 1; j < e1; j++)
				{
					res[resb++] = Expr[j];
				}
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "-");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				for (int j = b1; j < i; j++)
				{
					res[resb++] = Expr[j];
				}
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "*");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				resb = mDerivative(Expr, i + 1, e1, res, resb);
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "/");
				res[resb++] = make_pair(tokenType::Openbracket, "(");
				for (int j = i + 1; j < e1; j++)
				{
					res[resb++] = Expr[j];
				}
				res[resb++] = make_pair(tokenType::CloseBracket, ")");
				res[resb++] = make_pair(tokenType::OpType, "^");
				res[resb++] = make_pair(tokenType::ConstVar, "2");
				return resb;
			}
		}
		else if (Expr[i].first == tokenType::Openbracket)
		{
			inbracket++;
		}
		else if (Expr[i].first == tokenType::CloseBracket)
		{
			inbracket--;
		}
	}


	if (Expr[b1].first == tokenType::Variable)
	{
		if (e1 - b1 >= 3)
		{
			int indexn = matoi(Expr[e1 - 1].second);
			res[resb++] = make_pair(tokenType::ConstVar, to_string(indexn));
			res[resb++] = make_pair(tokenType::OpType, "*");
			res[resb++] = make_pair(tokenType::Variable, Expr[b1].second);
			res[resb++] = make_pair(tokenType::OpType, "^");
			res[resb++] = make_pair(tokenType::ConstVar, to_string(indexn - 1));
		}
		else
		{
			res[resb++] = make_pair(tokenType::ConstVar, "1");
		}
	}
	else
	{
		res[resb++] = make_pair(tokenType::ConstVar, "0");
	}
	return resb;
}

void solve()
{
	string Expr = "(x^3 + 2 * x^2 + 19 * x)/(x^2 + x)";
	tokenlist tlist, res(bign);
	LexAnalysis(Expr, tlist);

	int tn = tlist.size();
	memset(mapbracket, -1, tn * sizeof(int));
	for (int i = 0; i < tn; i++)
	{
		if (tlist[i].first == 1)
			bstack[mtop++] = i;
		if (tlist[i].first == 2)
		{
			assert(mtop > 0);
			mapbracket[i] = bstack[--mtop];
		}
	}
	assert(mtop == 0);
	int ressize = mDerivative(tlist, 0, tlist.size(), res, 0);
	string restr = tokenToString(res, ressize);
	cout << restr << endl;
}

int main()
{
	solve();
}

这篇关于一个符号求导的小程序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！