symbolic differentiation/ tree problem C++

Kris777's Avatar, Join Date: Apr 2009
Newbie Member
Hello everybody,
For 4 days now I am trying to finish my program but it seems that I am missing something. The way it is now it is supposed to work but it doesn’t. There are no compilation errors but I cannot find where I am missing something.

Basically, you should input a expression of the sort (2*x)+3-1 and you should get the derivative of the expression but I cannot even get it to calculate 2+4-2*3. I am hitting my head in the wall for some time now and I need help. here is the source code... PLS I will really appreciate it.

Code: Cpp
//---------------------------------------------starts here
// NEW.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <string>
using namespace std;
//------------------
#define SIZE 32
#define length(a) (sizeof a / sizeof a[0])
//------------------
struct node{
int tn; /* 0,1,2 */
char op;
double v;
node *arg1, *arg2;
};
 
/******** tree creation ************/
char str[999];
char ch;
int spos;
void next() {ch=str[spos++];}
void expression(node*& pt);
 
 
void factor(node*& pt)
{ if(ch=='(')
{ next(); expression(pt); next();}
else
{pt = new node; pt->tn=0; pt->v=0; pt->op=ch;
pt->arg1=NULL; pt->arg2=NULL; next();
}
}
 
 
void term(node*& pt)
{char op; node *a1, *a2;
factor(a1); pt=a1;
while ((ch=='*') || (ch=='/'))
{op=ch; next(); factor(a2);
pt=new node; pt->tn=2; pt->v=0; pt->op=op;
pt->arg1=a1; pt->arg2=a2; a1=pt;
}
}
 
 
void expression(node*& pt)
{ char op; node *a1, *a2;
term(a1); pt=a1;
while ((ch=='+') || (ch=='-'))
{op=ch; next(); term(a2);
pt = new node; pt->tn=2; pt->v=0; pt->op=op; pt->arg1=a1; pt->arg2=a2; a1=pt;
}
}
 
 
 
 
 
void create_tree(node*& pt)
{spos=0; next(); expression(pt);}
/********* output tree as a string ***********/
 
 
 
void output_tree(node* pt, char ch)
{char s;
switch(pt->tn)
{case 0: cout << pt->op; break;
case 2:
{ s=pt->op;
switch(s)
{case '*':
if(ch=='/') cout <<'(';
output_tree(pt->arg1,s); cout << s; output_tree(pt->arg2,s);
if(ch=='/') cout << ')';
break;
case '/':
if((ch=='*')||(ch=='/')) cout << '(';
output_tree(pt->arg1,s); cout << s; output_tree(pt->arg2,s);
if((ch=='*')||(ch=='/')) cout << ')';
break;
case '+': case '-' :
if((ch=='-')||(ch=='*')||(ch=='/')) cout << '(';
if(ch=='+') output_tree(pt->arg1,s);
else output_tree(pt->arg1,' ');
cout << s;
output_tree(pt->arg2,s);
if((ch=='-')||(ch=='*')||(ch=='/')) cout << ')';
break;
}
}
}
}
/********** computing using tree ***********/
typedef char varnameType[21];
typedef double varvalType[21];
varnameType varname;
varvalType varval;
int maxvar;
 
void initval() /** example only **/
{ maxvar=4;
varname[1]='a'; varname[2]='b'; varname[3]='c'; varname[4]='d';
varval[1]=1.0; varval[2]=2.0; varval[3]=3.0; varval[4]=4.0;
}
 
 
void argcalc(node* pt)
{ for(int i=1;i<=maxvar;i++)
if(pt->op==varname[i])
{pt->v=varval[i];
return;}
}
 
 
void twoargcalc(node* pt)
{
if((pt->arg1->tn==0)&&(pt->arg2->tn==0))
{switch(pt->op)
{ case '+' : pt->v = pt->arg1->v + pt->arg2->v; break;
case '-' : pt->v = pt->arg1->v - pt->arg2->v; break;
case '*' : pt->v = pt->arg1->v * pt->arg2->v; break;
case '/' : pt->v = pt->arg1->v / pt->arg2->v; break;
}
pt->tn=0;
}
}
 
 
void numcalc(node* pt)
{switch(pt->tn)
{case 0 : argcalc(pt); break;
case 2 : numcalc(pt->arg1);
numcalc(pt->arg2);
twoargcalc(pt);
break;
}
}
 
 
double value(node* pt)
{
numcalc(pt);
return pt->v;
}
int _tmain(int argc, _TCHAR* argv[])
{
//-------------------------------------
//int tempINDEX = 0;
//char fx[999], fxNS[999];;
cout << "Enter f(x) = ";

//cin.getline (fx, 999);
// for (int i = 0; fx[i]; ++i)
// { if (fx[i] != ' ')
//{
// fxNS[tempINDEX++] = fx[i];
//}
// }
// fxNS[tempINDEX] = '\0';
 

//-----------------------------
 
node* pt;

//for (int i = 0; fxNS[i]; ++i)
// { if (fx[i] != '\0')
// {
// str[i] = fxNS[i];
// }
// }
cin >> str;
cout << "\n";
cout << "f'(x) = ";
create_tree(pt);
 
output_tree(pt, ' ');
cout << endl;
initval();
cout << "\n\n\n"<< value(pt) << endl;


_getch();
return 0;
}
 
//---------------------------------------------ends here
 

Last edited by shabbir; 22Apr2009 at 08:41.. Reason: Code blocks
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
Code:
...
{pt = new node; pt->tn=0; pt->v=0; pt->op=ch;
pt->arg1=NULL; pt->arg2=NULL; next();
...
I'm not surprised you're finding this program difficult to debug. Are you planning to enter it in the next IOCCC competition or something?

Use one statement per line, and use sensible variable names (i.e. meaningful). Then you can step through it with the debugger and see exactly where it goes wrong. And use correct formatting too, although I appreciate that posting code without code blocks loses the formatting. Repost correctly formatted code and I'll have a go.

BTW, the derivative of 2x+3-1 is just 2. In general, d/dx x^n = nx^(n-1)

Here's an interesting puzzle for you if you're into calculus. d/dx x^2 = 2x. But d/dx (x+x+x...) (with x x's, so if x=5 then this is d/dx (x+x+x+x+x) ) which is 1+1+1...(x times) = x. Why the difference?

Both equations are absolutely correct; when faced with this contradiction, people will often say something like "well d/dx x^2 isn't 2x", or "well d/dx (x+x+x) isn't 1+1+1", but neither of those objections is valid.
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
OK, against my own better judgement I have stepped through the code, although it's not easy to see what it's supposed to be doing.

What exactly are you expecting it to do?

Currently all it does is to get an expression from the user, create an expression tree from that, then output the same expression. It doesn't attempt to differentiate the expression before displaying it.

The zero output after the expression tree has been printed seems to be an attempt to evaluate the expression, but as all operations are done on v, and this is always initialised to zero, that probably explains why you don't get a non-zero result. If I add a line like this:
Code:
printf("term() creating pt(tn=%d,v=%d,op=%c)\n",pt->tn,pt->v,pt->op);
after the assignments to tn,v and op in each of expression(), term() and factor() I get the following output:
Code:
Enter f(x) = (2*x)+3-1
f'(x) = factor() creating pt(tn=0,v=0,op= )
factor() creating pt(tn=0,v=0,op= )
term() creating pt(tn=2,v=0,op= )
factor() creating pt(tn=0,v=0,op= )
expression() creating pt(tn=2,v=0,op= )
factor() creating pt(tn=0,v=0,op= )
expression() creating pt(tn=2,v=0,op= )
2*x+3-1

0