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();
}``````

## All 3 Replies

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;
}
}
}
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.