Hi
this program calculate the differentiation of a polynomial by using a tree structure.
It's assumed that the variable is x and valid operations are +, -, * and /. The valid operands are x and digits.The program doesn't check the validity!
e.g. x*x*x-2*x+7 (valid)
x*x*x-12*x+15 (invalid)
But I need some advice to make it more efficient by lopping some useless nodes e.g.
cutting the x*0 or instead of (x*x)+(x*x) have 2*x*x.

// differentiation of a polynomial

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#include<stdio.h>

struct snode{              // Linked stack used to convert an inorder
    char sym;              // expression to postorder
    snode *next;
    }*top=NULL;

struct tree{              // expression tree
    char info;
    tree *left;
    tree *right;
    }*root;

struct pnode{            // Linked stack to convert a postorder
   tree *psym;           // expression to a tree
   pnode *next;
   }*ptop;

void push(char ch){           //for snode: push a char into stack
    snode *p=new snode;
    p->sym=ch;
    p->next=top;
    top=p;
    }

void ppush(tree *ptr){        //for pnode: push a node(tree) into stack
    pnode *pp=new pnode;
    pp->psym=ptr;
    pp->next=ptop;
    ptop=pp;
    }

char pop(){                             //for snode: remove a char from stack
    if(top==NULL){                      // and return it
        cout<<"Stack is empty!\n";
        return NULL;
        }
    else{
         snode *help=top;
         top=top->next;
         char ch=help->sym;
         delete help;
         return(ch);
         }
    }

tree *ppop(){                            //for pnode: remove a node (tree) from
    if(ptop==NULL){                      // a stack and return it
        cout<<"Stack is empty!\n";
        return NULL;
        }
    else{
        pnode *help=ptop;
        ptop=ptop->next;
        tree *ptr=help->psym;
        delete help;
        return ptr;
        }
    }

char *convert(char s[]){            //convert inorder to postorder
    int j=0;
    char *postfix;
    postfix=new char[strlen(s)];
    for(int i=0;s[i]!='\0';i++){
        if(s[i]=='*' || s[i]=='/' || s[i]=='(') push(s[i]);
        else if(s[i]=='+' || s[i]=='-'){
            if(top!=NULL){
                if( top->sym=='*' || top->sym=='/' ){
                    postfix[j++]=pop();
                    push(s[i]);
                    }
                else push(s[i]);
            }
            else push(s[i]);
            }
        else if(s[i]==')'){
            while(top->sym!='(') postfix[j++]=pop();
            pop();
            }
        else postfix[j++]=s[i];
        }
    while(top!=NULL)postfix[j++]=pop();
    postfix[j]='\0';
    return postfix;
    }


int test(char c){
    return(c=='+' || c=='-' || c=='*' || c=='/');
    }


void plant(char *p){                 //construct the expression tree
    ptop=NULL;                       //from a postorder expression
    tree *temp;
    for(int i=0;p[i]!='\0';i++){
        if(test(p[i])==0){
            temp=new tree;
            temp->info=p[i];
            temp->left=temp->right=NULL;
            ppush(temp);
            }
        else{
            temp=new tree;
            temp->info=p[i];
            temp->right=ppop();
            temp->left=ppop();
            ppush(temp);
            }
        }
    root=ppop();
    }


void inorder(tree *root){      //print an expression tree
    if(root!=NULL){
        if(root->right!=NULL || root->left!=NULL) cout<<'(';
        inorder(root->left);
        cout<<root->info;
        inorder(root->right);
        if(root->right!=NULL || root->left!=NULL) cout<<')';
        }
    }


tree *copy(tree *root){       //copy a tree
    tree *new_root;
    if(root!=NULL){
        new_root=new tree;
        new_root->info=root->info;
        new_root->left=copy(root->left);
        new_root->right=copy(root->right);
        }
    else if(root==NULL) return NULL;
    return new_root;
    }


tree *diff(tree *root){
    if(root->info=='+' || root->info=='-'){
        root->left=diff(root->left);
        root->right=diff(root->right);
        }
    else if(root->info=='x') root->info='1';
    else if((root->info)>='0' && (root->info)<='9') root->info='0';
    else if(root->info=='*'){
        tree *help1=new tree;
        tree *help2=new tree;
        help1->left=root->left;
        help1->right=diff(copy(root->right));
        help2->left=diff(copy(root->left));
        help2->right=root->right;
        help1->info='*';
        help2->info='*';
        root->left=help1;
        root->right=help2;
        root->info='+';
        }
    else if(root->info=='/'){
        tree *help1=new tree;
        tree *help2=new tree;
        tree *help3=new tree;
        tree *help4=new tree;
        help1->left=diff(copy(root->left));
        help1->right=root->right;
        help1->info='*';
        help2->left=root->left;
        help2->right=diff(copy(root->right));
        help2->info='*';
        help3->left=help1;
        help3->right=help2;
        help3->info='-';
        help4->left=root->right;
        help4->right=root->right;
        help4->info='*';
        root->left=help3;
        root->right=help4;
        }

    return root;
    }


void main(){
    char s[30];
    tree *diff_root;
    cout<<"Enter a polynomial containing the variable x\n";
    gets(s);   //user enters an expression inorder
    cout<<"--------------------------------------------------------------------------\n";
    char *p=convert(s); //Before constructing the tree, convert the string into postorder
    plant(p);   //build up the tree
    inorder(root);  //print the expression
    cout<<"\n------------------------------------------------------------------------\n";
    diff_root=copy(root);
    diff_root=diff(diff_root);
    inorder(diff_root);  //print the diffrentiation of expression
    getch();
    }

Optimizing the tree can be really tricky but there are some ways to do it. So if the parent node is '*' and one of the child nodes is 0 then you can delete the child nodes. For changing x + x in 2 * x it doesn't really matter because you convert only the operation but you can check if the child nodes are the same.

The problem is that I don't know how to do that.Once I've tried this code to lop x+0 or 0+x but it doesn't work.And I know that this code looks very silly!

tree *lop(tree *root){
    if(root->left!=NULL || root->right!=NULL){
        root=lop(root->left);
        if(root->info=='+'){
            if(root->left->info=='0'){
                root->info=root->right->info;
                delete root->left;
                delete root->right;
                }
            else if(root->right->info=='0'){
                root->info=root->left->info;
                delete root->left;
                delete root->right;
                }
            }
        root=lop(root->right);
        }
    return root;
    }

Finally I could do something! This code is ran successfully if the expression doesn't include division!!!
:-/ :confused: :?:

void lop(tree *root){                 ///////// remove useless nodes
    if (root->left!=NULL && root->right!=NULL )
    {
        lop(root->left);
        lop(root->right);
        if (root->info=='*')
        {
            if (root->left->info=='0' || root->right->info=='0')
            {
                root->info='0';
                delete root->left;
                delete root->right;
                root->left=NULL;
                root->right=NULL;
            }
            else if (root->left->info=='1')
            {
                delete root->left;
                tree *temp= root->right;
                root->info = temp->info;
                root->left = temp->left;
                root->right = temp->right;
                delete temp;
            }
            else if (root->right->info=='1')
            {
                delete root->right;
                tree *temp= root->left;
                root->info = temp->info;
                root->left = temp->left;
                root->right = temp->right;
                delete temp;
            }

        }
        else if (root->info=='+')
        {
            if (root->left->info=='0')
            {
                delete root->left;
                tree *temp= root->right;
                root->info = temp->info;
                root->left = temp->left;
                root->right = temp->right;
                delete temp;
            }
            else if (root->right->info=='0')
            {
                delete root->right;
                tree *temp= root->left;
                root->info = temp->info;
                root->left = temp->left;
                root->right = temp->right;
                delete temp;
            }
            else if (root->right->info == root->left->info)
                if (test(root->left->info) == 0)
                {
                    root->info='*';
                    root->left->info='2';
                }
        }
        else if (root->info=='-')
        {
            if (root->right->info=='0')
            {
                delete root->right;
                tree *temp= root->left;
                root->info = temp->info;
                root->left = temp->left;
                root->right = temp->right;
                delete temp;
            }
            else if (root->left->info==root->right->info)
                if ( test(root->left->info)==0 )
                {
                    root->info='0';
                    delete root->left;
                    delete root->right;
                    root->left=NULL;
                    root->right=NULL;
                }
        }
    }
}

Edited 5 Years Ago by Hojjat.Mojallal: n/a

This article has been dead for over six months. Start a new discussion instead.