原题地址：http://poj.org/problem?id=1467
题目大意：
对一个式子求导，给的式子包括常量，字母x，+,-,*,/,ln()运算符，任意嵌套的括号。求的导数式子不用化简，如1*x这样的式子不用变成x。下面给出了一些求导规则和运算优先级：
1.乘除的优先级大于加减。
2.同优先级结合性从左往右。
3. 求导规则:
(a + b)' = a' + b'
(a - b)' = a' - b'
(a * b)' = (a' * b + a * b')
(a / b)' = (a' * b - a * b') / b^2 Note: 写 b^2 而不是 (b*b)
ln(a)' = (a')/(a)
x' = 1
常数的导数 = 0
要注意的是，如上所给的规则中，有括号的部分要在求导式子中相应的加上括号。如：
输入1*1
输出(0*1+1*0)
这里的括号不能去掉。
解题思路：
将整个式子当做一个字符串来处理。
如果这个字符串是一个数字，则求导结果是 0
如果这个字符串是一个x，则求导结果是 1
否则，找到最后计算的那一个运算符（这个字符不能在任何括号里），如：" (2*ln(x+1.7)-x*x)/((-7)+3.2*x*x)+(x+3*x)*x "中，先最后计算的运算符是红色的加号。然后以这个加号为分界点，将整个式子分解成两部分，“ (2*ln(x+1.7)-x*x)/((-7)+3.2*x*x) ” 和“(x+3*x)*x” 然后根据加法求导法则，分别求两部分的导数，则将两部分分别递归一遍。
若没有找到上一条所述的运算符（即整个字符串包含在括号里，或者为ln运算）
如果是整个括号包含的字符串，则去掉这个括号得到的字符串递归一遍。
如果是ln()运算符，则根据ln()求导法则递归。
解题代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
using namespace std;
class String
{
public:
char s[];
String(){s[]=;}
String(String& s1){strcpy(s,s1.s);}
bool isnum();
};
char ans[];
ostream& operator<<(ostream& out,String &s1)
{
cout<<s1.s;
return out;
}
bool String::isnum()
{
int i=;
if(s[]=='-') i++;
for(;s[i];i++)
{
if(s[i]=='.'||(s[i]>=''&&s[i]<='')) ;
else break;
}
if(!s[i]) return true;
else return false;
}
void qiudao(String s1);
void jia(String s1,String s2)
{
qiudao(s1);
strcat(ans,"+");
qiudao(s2);
}
void jian(String s1,String s2)
{
qiudao(s1);
strcat(ans,"-");
qiudao(s2);
}
void cheng(String s1,String s2)
{
strcat(ans,"(");
qiudao(s1);
strcat(ans,"*");
strcat(ans,s2.s);
strcat(ans,"+");
strcat(ans,s1.s);
strcat(ans,"*");
qiudao(s2);
strcat(ans,")");
}
void chu(String s1,String s2)
{
strcat(ans,"(");
qiudao(s1);
strcat(ans,"*");
strcat(ans,s2.s);
strcat(ans,"-");
strcat(ans,s1.s);
strcat(ans,"*");
qiudao(s2);
strcat(ans,")/");
strcat(ans,s2.s);
strcat(ans,"^2");
}
void ln(String s1)
{
strcat(ans,"(");
qiudao(s1);
strcat(ans,")/(");
strcat(ans,s1.s);
strcat(ans,")");
}
void qiudao(String s1)
{
int i;
if(s1.isnum()) {strcat(ans,"");return ;}//如果字符串表示一个数字，则求导结果为 0
if(strcmp(s1.s,"x")==) {strcat(ans,"");return ;}//如果字符串是一个x，则求导结果为 1
int len=strlen(s1.s);
//下面用于计算优先级最低的一个运算符。
int n=-,you=;
for(i=;s1.s[i];i++)
{
if(i!=&&((s1.s[i]=='+'||s1.s[i]=='-')&&you>=)) {n=i;you=;break;}
if(i!=&&((s1.s[i]=='*'||s1.s[i]=='/')&&you>=)) {n=i;you=;}
if(s1.s[i]=='(')
{
int n=;
while(n)
{
i++;
if(s1.s[i]=='(')n++;
if(s1.s[i]==')')n--;
}
}
}
if(you!=)
{
String ss1,ss2;
strncpy(ss1.s,s1.s,n);
ss1.s[n]=;
strncpy(ss2.s,&s1.s[n+],len-n-);
ss2.s[len-n-]=;
switch(s1.s[n])
{
case '+':jia(ss1,ss2);break;
case '-':jian(ss1,ss2);break;
case '*':cheng(ss1,ss2);break;
case '/':chu(ss1,ss2);break;
}
return ;
}
if(s1.s[]=='('&&s1.s[len-]==')')
{
String s2;
strncpy(s2.s,s1.s+,len-);
s2.s[len-]=;
strcat(ans,"(");
qiudao(s2);
strcat(ans,")");
return ;
}
if(strncmp(s1.s,"ln(",)==&&s1.s[len-]==')')
{
String ss1;
strncpy(ss1.s,s1.s+,len-);
ss1.s[len-]=;
ln(ss1);
}
}
int main()
{
String s1;
int i;
while(cin>>s1.s)
{
ans[]=;
qiudao(s1);
for(i=;ans[i];i++)
{
if(ans[i+]=='-')
{
if(ans[i]=='+') {cout<<'-';i++;continue;}
if(ans[i]=='-') {cout<<'+';i++;continue;}
}
cout<<ans[i];
}
cout<<endl;
}
return ;
}