qd.h

最优化方法newton法求极值的vc++实现 环境：vs2008

#include<iostream>
#include<fstream>
#include<string>
#include<sstream>
using namespace std;

string s,oss;
class node
{
public:
		double f;
		bool bracket;
		int ep;
		node *l,*r;
		char op;
	node(){}
	node(double f1,int ep1=0,char op1=' ',node *l1=NULL,node *r1=NULL,bool b1=false)
		{
			f=f1;ep=ep1;op=op1;l=l1;r=r1;bracket=b1;
		}
};
	node *Term(int &k);
	node *Expr(int &k);
	node *Fact(int &k)
		{
			node *l=NULL;
		if(k>=s.size())
			return l;
		if((s[k]=='-' || s[k]=='+') && k+1<s.size() && isdigit(s[k+1]) || isdigit(s[k]))
		{
			int flag=1;
			double r=0,r1=1;
		if(s[k]=='-')
		{
			flag=-1;
			k++;
		}
		while(isdigit(s[k]))
		{
			r=10*r+s[k]-'0';
			k++;
		}
		if(s[k]=='.')
		{
			k++;
		while(isdigit(s[k]))
		{
			r1/=10;
			r+=r1*(s[k]-'0');
			k++;
		}
		}
			l=new node(r*flag);
		}
		else if((s[k]=='-' || s[k]=='+') && k+1<s.size() && s[k+1]=='x' || s[k]=='x')
		{
		if(s[k]=='x')
		{
			k++;
			l=new node(1,1);
		}
		else
		{
			int flag=1;
			if(s[k]=='-')
			flag=-1;
			k+=2;
			l=new node(flag,1);
		}
		}
		else if(s[k]=='(')
		{
			k++;
			l=Expr(k);
			l=new node(0,0,' ',NULL,l,true);
			if(s[k]==')')
			k++;
		}
		else if(s[k]=='l')
		{
		if(s[k+1]=='n' && s[k+2]=='(')
		{
			k+=3;
			l=Expr(k);
		if(s[k]==')')
			k++;
			l=new node(0,0,'l',NULL,l);
		}
		}
			return l;
		}

//--------------------------------------------------------------------------------

node *Term(int &k)
{
	node *l,*r;
	char c;
	l=Fact(k);
	while(k<s.size() && (s[k]=='*' || s[k]=='/'))
	{
		c=s[k];
		k++;
		r=Fact(k);
		l=new node(0,0,c,l,r);
	}
		return l;
	}
		node *Expr(int &k)
	{
		node *l,*r;
		char c;
		l=Term(k);
	while(k<s.size() && (s[k]=='+' || s[k]=='-'))
	{
		c=s[k];
		k++; 
		r=Term(k);
		l=new node(0,0,c,l,r);
	}
		return l;
	}
	bool less(char c1,char c2,bool flag)
	{
	if(c2=='l')
	return true;
	if(c1=='+' || c1=='-')
	{
	if(c2=='*' || c2=='/' || c2=='^')
	return true;
	}
	if(c1=='*' || c1=='/')
	{
	if(c2=='^')
	return true;
	}
	if(flag)
	{
	if(c1=='+' || c1=='-')
	{
	if(c2=='-')
	return true;
	}
	if(c1=='*' || c1=='/')
	{
	if(c2=='/')
	return true;
	}
	}
	return false;
	}


	void output(node *T)
	{
	string str;
	if(!T)
	return;
	if(T->bracket)
	oss+='(';
	if(!T->l && !T->r)
	{
	if(T->ep)
	oss+='x';
	else
	{
	ostringstream os;
	os<<T->f; 
	str=os.str();
	oss+=str; 
	}
	//return;
	} 
	if(T->l)
	{
	if(less(T->l->op,T->op,false) && !T->l->bracket)
	{
	oss+='(';
	}
	output(T->l);
	if(less(T->l->op,T->op,false) && !T->l->bracket)
	{
	oss+=')';
	}
	}
	if(T->op!='l')
	{
	if(T->op!=' ')
	{
	ostringstream os;
	os<<T->op;
	str=os.str();
	oss+=str;
	}
	}
	else
	oss+="ln";
	if(T->r)
	{
	if(less(T->r->op,T->op,true) && !T->r->bracket)
	{
	oss+='(';
	}
	output(T->r);
	if(less(T->r->op,T->op,true) && !T->r->bracket)
	{
	oss+=')';
	}
	}
	if(T->bracket)
	oss+=')';
	}
	node *Derivation(node *T,node *temp)
	{

	if(T->op=='+' || T->op=='-')
	{
	T->l=Derivation(T->l,temp->l);
	T->r=Derivation(T->r,temp->r);
	}
	else if(T->op=='*')
	{
	node *a,*b;
	T->op='+';
	a=T->l;
	b=T->r;
	T->l=new node(0,0,'*',Derivation(a,temp->l),temp->r);
	T->r=new node(0,0,'*',temp->l,Derivation(b,temp->r));
	T->bracket=true;
	}
	else if(T->op=='/')
	{
	node *a,*b,*c;
	T->op='/';
	a=T->l;
	b=T->r;
	c = new node(0,0,'-',new node(0,0,'*',Derivation(a,temp->l),temp->r),new node(0,0,'*',temp->l,Derivation(b,temp->r)));
	T->l=c;
	T->r=new node(0,0,'^',temp->r,new node(2));
	}
	else if(T->op=='l')
	{
	node *a;
	a=T->r;
	T->l=Derivation(a,temp->r);
	T->l->bracket=true;
	T->op='/';
	T->r=temp->r;
	T->r->bracket=true;
	} 
	else if(!T->l && !T->r)
	{
	if(T->ep!=0)
	{
	T->f*=T->ep;
	T->ep--; 
	}
	else
	T->f=0;
	}
	else if(T->op==' ' && T->bracket)
	{
	T->r=Derivation(T->r,temp->r);
	}
	return T;
}


	CString GetExpretion(CString str)//求得导数表达式返回
	{
	ifstream fin(str);
	node *T,*temp;
	int k;
	s=str.GetBuffer(0);
		k=0;
		T=Expr(k);
		k=0;
		temp=Expr(k);
		T=Derivation(T,temp);
		oss="";
		output(T);
		for(int i=0;i<oss.size();i++)
	{
	if(oss[i]=='+' && i+1<oss.size() && (oss[i+1]=='-' || oss[i+1]=='+'))
	{
		oss.erase(oss.begin()+i);
		i--;
	}
	if(oss[i]=='-' && i+1<oss.size() && (oss[i+1]=='-' || oss[i+1]=='+'))
	{
		if(oss[i+1]=='-')
		{
		oss[i]='+';
		}
		oss.erase(oss.begin()+i+1);
		i--;
	}
	}
		return oss.c_str();
	}


double Abs(double a)
{
	if (a>=0)
		return a;
	else
	return -a;
}