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