Am a beginner to C++,i'm trying to construct an expression tree for the infix expression, username eq "xxx xx" and (email co "gmail.com" or email co "example.com" and (email sw "nnn" or email sw "aaa")) into a tree of the form as shown in the image attached, how can i construct a tree like thuis?
The code i did doesn't work properly, please tell me if there is any other method for constructing the expression tree.
#include <iostream>
#include <cstdlib>
#include <string>
#include <string.h>
using namespace std;
struct node
{
string data;
struct node *left,*right;
};
void inorder(struct node *tree)
{
//printing the left child and right child of the operator
if(tree!=NULL)
{
inorder(tree->left);
//cout<<tree->data<<" ";
if(tree->data.compare("eq")==0 || tree->data.compare("and")==0 || tree->data.compare("or")==0 || tree->data.compare("co")==0 )
cout<<tree->left->data<<" "<<tree->data<<" "<<tree->right->data<<endl;
inorder(tree->right);
}
}
struct node* construct_tree(string arr[],int size)
{
struct node *temp,*op,*current,*root,*log,*log1,*op1;//tempoaray pointers
struct node *blog,*blog1,*root1;
blog=blog1=NULL;
temp=op=root=root1=log=op1=NULL;
int i=0;
while(i<=size)
{
current=new node;
current->left=current->right=NULL;
current->data.assign(arr[i]);
if(arr[i].compare("eq")==0 ||tree->data.compare("co")==0 )
{
op=current;
op->left=temp;
temp=NULL;
}
else if(arr[i].compare("and")==0 || tree->data.compare("or")==0 )
{
log1=log;
log=current;
if(log1!=NULL)
{
if(log->left==NULL)
log->left=log1;
else
log->right=log1;
}
else if(op!=NULL)
{
log->left=op;
op=NULL;
}
}
else if(arr[i].compare("(")==0)
{
delete current;
i++;
//constructing a seperate tree for cases within brackets and then attaching it to the main tree.
while(arr[i].compare(")")!=0)
{
current=new node;
current->left=current->right=NULL;
current->data.assign(arr[i]);
if(arr[i].compare("eq")==0 || tree->data.compare("co")==0)
{
op1=current;
op1->left=temp;
temp=NULL;
}
else if(arr[i].compare("and")==0 )
{
blog1=blog;
blog=current;
if(blog1!=NULL)
{
if(blog->left==NULL)
blog->left=blog1;
else
blog->right=blog1;
}
else if(op1!=NULL)
{
blog->left=op1;
op1=NULL;
}
}
else
temp=current;
if(op1!=NULL)
{
if(op1->left!=NULL && temp!=NULL)
{
op1->right=temp;
temp=NULL;
}
}
if(blog!=NULL&& op1!=NULL)
{
if(blog->left!=NULL && op1->right!=NULL)
{
blog->right=op1;
op1=NULL;
}
}
i++;
}
if(log->left==NULL)
{
log->left=blog;
blog=NULL;
}
else
{
log->right=blog;
blog=NULL;
}
}
else
temp=current;
if(op!=NULL)
{
if(op->left!=NULL && temp!=NULL)
{
op->right=temp;
temp=NULL;
}
}
if(log!=NULL&& op!=NULL)
{
if(log->left!=NULL && op->right!=NULL)
{
log->right=op;
op=NULL;
}
}
i++;
}
log1=blog=blog1=op1=NULL;
if(op!=NULL)
root=op;
else
root=log;
return root;
}
class token
{
//seperating the string expression into seperate tokens
public:
char a;
int size;
string str[100],complex,temp,mid;
void split_tokens(string filter)
{
int i=0;
for (string::const_iterator it = filter.begin(); it != filter.end();it++)
{
if(*it=='(')
{
a=*it;
str[i]=a;
i++;
}
else if(*it==')')
{
i++;
a=*it;
str[i]=a;
}
else if(*it=='"')
{
it++;
while(*it!='"')
{
a=*it;
str[i]=str[i]+a;
it++;
}
}
else if(*it!=' ')
{
a=*it;
str[i]=str[i]+a;
}
else
i++;
}
size=i;
struct node *root=NULL;
root=construct_tree(str,size);
cout<<"inorder traversal"<<endl;
inorder(root);
}
};
int main()
{
string filter,str[100];
cout<<"filter:"<<endl;
std::getline (std::cin,filter);
token t1;
t1.split_tokens(filter);
return 0;
}
Aucun commentaire:
Enregistrer un commentaire