1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

symbolic differentiation/ tree problem C++

Discussion in 'C++' started by Kris777, Apr 21, 2009.

  1. Kris777

    Kris777 New 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.:freak::freak::freak: :confused::confused::confused:

    Code:
    //---------------------------------------------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 a moderator: Apr 22, 2009
  2. xpi0t0s

    xpi0t0s 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.
     
  3. xpi0t0s

    xpi0t0s 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
    
     

Share This Page