Tuesday 3 January 2017

Expression Tree (using BST)

/*For given expression eg. a-b*c-d/e+f construct inorder sequence and traverse 
it using postorder traversal(non recursive).*/
#include<iostream>
#include<string>
using namespace std;
typedef struct node { char cData;
class Cstack
struct node *pRt,*pLf; }NODE; { NODE *pS[20];
void fPush(NODE* pPtr)
int iTop; public: Cstack() { iTop=-1; } {
pTmp=pS[iTop];
iTop++; pS[iTop]=pPtr; } NODE* fPop() { NODE *pTmp;
return(pS[iTop]);
iTop--; return(pTmp); } NODE* fTop() { } int fIsempty() {
string sExpr;
if(iTop==-1) return 1; return 0; } }; class Cexp { Cstack oS1,oS2;
void fDisplayPos(NODE*);
int iLen; public: void fGetExp(); int fPriority(char); NODE* fBuildTree();
cout<<"Enter Expression : ";
void fDisplay(NODE*,int,NODE*); }; void Cexp::fGetExp() { cin>>sExpr; iLen=sExpr.size(); }
if(sExpr[i]!='*'&&sExpr[i]!='/'&&sExpr[i]!='+'&&sExpr[i]!='-')
NODE* Cexp::fBuildTree() { NODE *pNn,*pOpr,*pOp1,*pOp2; for(int i=iLen-1;i>=0;i--) { { pNn=new NODE;
if(!oS2.fIsempty()&&(fPriority((oS2.fTop())->cData)>fPriority(sExpr[i])))
pNn->cData=sExpr[i]; pNn->pLf=pNn->pRt=NULL; oS1.fPush(pNn); } else { {
pOp1=oS1.fPop();
while( fPriority((oS2.fTop())->cData)>fPriority(sExpr[i]) ) { pOpr=oS2.fPop(); pOp2=oS1.fPop(); pOpr->pRt=pOp1;
while(!oS2.fIsempty())
pOpr->pLf=pOp2; oS1.fPush(pOpr); } } pNn=new NODE; pNn->cData=sExpr[i]; pNn->pRt=pNn->pLf=NULL; oS2.fPush(pNn); } } {
int Cexp::fPriority(char cCh)
pOpr=oS2.fPop(); pOp2=oS1.fPop(); pOp1=oS1.fPop(); pOpr->pRt=pOp1; pOpr->pLf=pOp2; oS1.fPush(pOpr); } return oS1.fTop(); } { if(cCh=='+'||cCh=='-')
oS2.fPush(pTmp);
return 1; else return 2; } void Cexp::fDisplayPos(NODE *pRoot) { Cstack oS1,oS2; NODE *pTmp; oS1.fPush(pRoot); while(!oS1.fIsempty()) { pTmp=oS1.fTop(); oS1.fPop(); if(pTmp->pLf)
void Cexp::fDisplay(NODE *ptr, int level,NODE *pRoot)
oS1.fPush(pTmp->pLf); if(pTmp->pRt) oS1.fPush(pTmp->pRt); } while(!oS2.fIsempty()) { pTmp=oS2.fTop(); oS2.fPop(); cout<<pTmp->cData<<" "; } } { int i; if (ptr != NULL) { fDisplay(ptr->pRt, level+1,pRoot);
pRoot=o.fBuildTree();
cout<<endl; if (ptr == pRoot) cout<<"Root->: "; else { for (i = 0;i < level;i++) cout<<" "; } cout<<ptr->cData; fDisplay(ptr->pLf, level+1,pRoot); } } int main() { NODE *pRoot; Cexp o; o.fGetExp();
o.fDisplay(pRoot,1,pRoot);
cout<<"\n";
o.fDisplayPos(pRoot);
cout<<"\n";
return 0;
}

Monday 2 January 2017

Dictionary using BST

/*
A Dictionary stores keywords & its meanings. Provide facility for adding new
keywords, deleting keywords, updating values of any entry. Provide facility to display whole data sorted in ascending/ Descending order. Also find how many maximum comparisons may require for finding any keyword. Use Binary Search Tree for implementation.
*/

#include<iostream>
using namespace std;

typedef struct node
{
struct node *pRt,*pLf;
string sWord,sMeaning;
}NODE;

class cQueue
{
 NODE *pQ[20];
 int iF,iR;
public:
 cQueue()
    {
  iF=iR=-1;
    }
 void fInsert(NODE*);
 NODE* fDelete();
 int fIsempty();

};

void cQueue::fInsert(NODE *pT)
{
 pQ[iR++]=pT;
}

NODE* cQueue::fDelete()
{
 return(pQ[iF++]);
}

int cQueue::fIsempty()
{
 if(iF==iR)
 return 1;
 return 0;
}

class cDictionary
{
public:
    NODE* fCreate();
    void fAdd(NODE*);
    void fDelete(NODE*,string);
    void fUpdate(NODE*);
    void fDisplay(NODE*,NODE*,int);
    void fDisplayIna(NODE*);
    void fDisplayPre(NODE*);
    void fDisplayPos(NODE*);
    void fDisplayLev(NODE*);

};

NODE* cDictionary::fCreate()
{
    NODE *pRoot,*pNn,*pCn,*pParent;
    char cCh;
    pRoot=NULL;
    do
    {
        pNn=new NODE;
        pNn->pLf=pNn->pRt=NULL;
        cout<<"Enter word: ";
        cin>>pNn->sWord;
        cout<<"Enter meaning: ";
        cin>>pNn->sMeaning;

        if(pRoot==NULL)
        pRoot=pNn;
        else
        {
            pCn=pRoot;
            while(pCn)
            {
                pParent=pCn;
                if(pCn->sWord<pNn->sWord)
                pCn=pCn->pRt;
                else
                pCn=pCn->pLf;

            }
            if(pParent->sWord<pNn->sWord)
            pParent->pRt=pNn;
            else
            pParent->pLf=pNn;

        }
        cout<<"do you want to continue(y/n) : ";
         cin>>cCh;

    }while(cCh=='y'||cCh=='Y');
return pRoot;
}

void cDictionary::fAdd(NODE *pRoot)
{
    NODE *pCn,*pNn,*pParent;
    pNn=new NODE;
    pNn->pLf=pNn->pRt=NULL;
    cout<<"Enter word: ";
    cin>>pNn->sWord;
    cout<<"enter Meaning";
    cin>>pNn->sMeaning;
    pCn=pRoot;
    while(pCn)
    {
        pParent=pCn;
        if(pCn->sWord<pNn->sWord)
            pCn=pCn->pRt;
        else
            pCn=pCn->pLf;
    }
    if(pParent->sWord<pNn->sWord)
    pParent->pRt=pNn;
    else
    pParent->pLf=pNn;
    cout<<"Word is added Succesfully to the Dictionary\n";


}


void cDictionary::fDelete(NODE *pPtr,string sData)
{
    NODE *pParent;
    while(pPtr)
    {
    if(pPtr->sWord==sData)
    break;
    pParent=pPtr;
    if(pPtr->sWord<sData)
    pPtr=pPtr->pRt;
    else
    pPtr=pPtr->pLf;

    }
        //case 1 leaf node
        if(pPtr->pLf==NULL&&pPtr->pRt==NULL)
        {
            if(pParent->pRt==pPtr)
            pParent->pRt=NULL;
            else
            pParent->pLf=NULL;
            delete(pPtr);
            cout<<"Node is deleted !\n";

        }

        //case 2 only 1 child
        else if(pPtr->pLf==NULL)
        {
            if(pParent->pRt==pPtr)
            pParent->pRt=pPtr->pRt;
            else
            pParent->pLf=pPtr->pRt;
            delete(pPtr);
            cout<<"Node is deleted !\n";

        }

        else if(pPtr->pRt==NULL)
        {
            if(pParent->pRt==pPtr)
            pParent->pRt=pPtr->pLf;
            else
            pParent->pLf=pPtr->pLf;
            delete(pPtr);
            cout<<"Node is deleted !\n";

        }

        //case 3 two childs
        else
        {
         pParent=pPtr;
         NODE *pTemp;
         pTemp=pPtr->pRt;
         while(pTemp->pLf)
         {
          pParent=pTemp;
          pTemp=pTemp->pLf;
         }
         pPtr->sWord=pTemp->sWord;
         pPtr->sMeaning=pTemp->sMeaning;
         if(pParent==pPtr)
         pPtr->pRt=pTemp->pRt;
         else
         pParent->pLf=NULL;
         delete(pTemp);
         cout<<"Node is deleted !\n";

        }

}


void cDictionary::fUpdate(NODE *pRoot)
{
    NODE *pCn;
    string sW;
    cout<<"Enter word to Update : ";
    cin>>sW;
    pCn=pRoot;
    while(pCn)
    {
        if(pCn->sWord==sW)
        {
            cout<<"Enter New Meaning : ";
            cin>>pCn->sMeaning;
            cout<<"Meaning Updated succesfully\n";
            return;

        }
        else
        {
        if(pCn->sWord<sW)
        pCn=pCn->pRt;
        else
        pCn=pCn->pLf;
        }

    }
cout<<"Word not found!\n";
}

void cDictionary::fDisplay(NODE *pRoot,NODE *pPtr, int level)

{
int i;
if(pPtr!=NULL)
{
fDisplay(pRoot,pPtr->pRt, level+1);
cout<<endl;
if (pPtr == pRoot)
cout<<"Root->:  ";
else
{
for (i = 0;i < level;i++)
cout<<"       ";
}
cout<<pPtr->sWord<<"->"<<pPtr->sMeaning;
fDisplay(pRoot,pPtr->pLf, level+1);
}
}


void cDictionary::fDisplayIna(NODE *pPtr)
{
    if(pPtr)
    {
        fDisplayIna(pPtr->pLf);
        cout<<pPtr->sWord<<"->"<<pPtr->sMeaning<<"\n";
        fDisplayIna(pPtr->pRt);

    }

}

void cDictionary::fDisplayPre(NODE *pPtr)
{
if(pPtr!=NULL)
{
 cout<<pPtr->sWord<<"->"<<pPtr->sMeaning<<" ";
 fDisplayPre(pPtr->pLf);
 fDisplayPos(pPtr->pRt);
}
}

void cDictionary::fDisplayPos(NODE *pPtr)
{
if(pPtr!=NULL)
{
     fDisplayPos(pPtr->pLf);
  fDisplayPos(pPtr->pRt);
  cout<<pPtr->sWord<<"->"<<pPtr->sMeaning<<" ";
}
}

void cDictionary::fDisplayLev(NODE *pPtr)
{
 cQueue oObj;
 NODE *pT;
 oObj.fInsert(pPtr);
 while(oObj.fIsempty()==0)
 {
  pT=oObj.fDelete();
  cout<<pT->sWord<<"->"<<pT->sMeaning<<"\n";
  if(pT->pLf)
  oObj.fInsert(pT->pLf);
  if(pT->pRt)
  oObj.fInsert(pT->pRt);
 }

}

int main()
{
    NODE *pRoot;
    string sW;
    cDictionary oObj;
    char cCh;
    int iCh;
    do
    {
     cout<<"\n\n";
        cout<<"1]Create dictionary\n";
        cout<<"2]Add new Word to the Dictionary\n";
        cout<<"3]Update Meaning of a Word\n";
        cout<<"4]Delete a word from Dictionary\n";
        cout<<"5]Display Dictionary Inorder\n";
        cout<<"6]Display Dictionary Preorder\n";
        cout<<"7]Display Dictionary Postorder\n";
        cout<<"8]Display Dictionary Levelorder\n";
        cout<<"9]Display Tree like structure\n";
        cout<<"\n\nEnter your Choice : ";
        cin>>iCh;
        switch(iCh)
        {
        case 1:
            pRoot=oObj.fCreate();
            break;

        case 2:
            oObj.fAdd(pRoot);
            break;

        case 3:
            oObj.fUpdate(pRoot);
            break;

        case 4:
            cout<<"enter word to delete : ";
            cin>>sW;
            oObj.fDelete(pRoot,sW);
            break;
        case 5:
            oObj.fDisplayIna(pRoot);
            break;

        case 6:
         oObj.fDisplayPre(pRoot);
            break;
        case 7:
            oObj.fDisplayPos(pRoot);
            break;
        case 8:
         oObj.fDisplayLev(pRoot);
      break;
        case 9:
          oObj.fDisplay(pRoot,pRoot,1);
            break;
        }
        cout<<"\npress 1 for main and 2 to exit ";
        cin>>cCh;
    }while(cCh=='1');

return 0;
}

Sunday 23 October 2016

Generic Vector Using Template

/* AIM : Create a class template to represent a generic vector. Include following
member functions:
1]To create the vector.
2]To modify the value of a given element
3]To multiply by a scalar value
4]To display the vector in the form (10,20,30)
*/

#include<iostream>
using namespace std;

template<class T>
class vector
{
T *v;
int size;
public:
vector(int m) // parameterized constructor to create NULL vector
{
v=new T[size=m];
for(int i=0;i<size;i++)
v[i]=0;
}

void create()
{
for(int i=0;i<size;i++)
{
cout<<"v["<<i<<"] = ";
cin>>v[i];
}
}

void modify()
{
int pos;
cout<<"enter position to make changes :";
cin>>pos;
cout<<"Enter new Value :";
cin>>v[pos];
}

void multiply()
{
T sc;
cout<<"Enter scaler Number to multiply with vector : ";
cin>>sc;
for(int i=0;i<size;i++)
v[i]=v[i]*sc;
}

void display()
{
int i;
cout<<"(";
for(i=0;i<size-1;i++)
{
cout<<v[i]<<",";
}
cout<<v[i]<<")\n";
}


};

int main()
{
int size;
cout<<"enter size of vector: ";
cin>>size;
vector<int> vi(size); //creates int vector
vi.create();
vi.display();
vi.modify();
vi.display();
vi.multiply();
vi.display();

}

Selection Sort Function Template

/*
TITLE:
Write a function template selection Sort. Write a program that inputs, sorts and outputs an integer array and a float array.
*/
#include<iostream>
using namespace std;
template<class T>
class sort
{
public:
T a[50];
int n;
void accept()
{
cout<<"Enter no. of elements:\n";
cin>>n;
cout<<"enter a elements\n";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
}
void selection_sort()
{
T temp;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
void display()
{
for(int i=0;i<n;i++)
{cout<<a[i]<<"\n";
}
}
};

int main()
{
int v;char ch;
sort<int>s1;
sort<float>s2;

cout<<"*****SELECTION SORT*******\n";
do
{
cout<<"sorting of integer and float array"<<"\n";
cout<<"1.for int array\n";
cout<<"2.for float array\n";
cout<<"enter your choice\n";
cin>>v;
switch(v)
{
case 1:
s1.accept();
cout<<"\nElements are:\n";
s1.display();
s1.selection_sort();
cout<<"\nSorted elements are:\n";
s1.display();
break;
case 2:
s2.accept();
cout<<"\nElements are:\n";
s2.display();
s2.selection_sort();
cout<<"\nSorted elements are:\n";
s2.display();
break;
}
cout<<"\n do you want to continue";
cin>>ch;
}while(ch=='y'||ch=='Y');
return 0;
}

Addition of Binary numbers using Standard Template Library

/*
TITLE:
Write C++ program using STL to add binary numbers ; use STL stack.
*/
#include<iostream>
#include<stack>
using namespace std;
stack<int> read()
{
stack<int> s;
int x,n,i;
n=4;
cout<<"\nEnter 4 bit binary number : ";
for(i=0;i<n;i++)
{
cin>>x;
s.push(x);
}
return s;
}

void display(stack<int> &s)
{
cout<<" ";
while(!s.empty())
{
cout<<s.top()<<" ";
s.pop();
}
}

stack<int> add(stack<int> &s1,stack<int> &s2)
{
stack<int> s;
int sum,carry=0,b1,b2;
while(!s1.empty()||!s2.empty())
{
b1=b2=0;
if(!s1.empty())
{
b1=s1.top();
s1.pop();
}
if(!s2.empty())
{
b2=s2.top();
s2.pop();
}
sum=(b1+b2+carry)%2;
carry=(b1+b2+carry)/2;
s.push(sum);
}
if(carry==1)
s.push(1);
return s;
}

int main()
{
stack<int> s1,s2,s3;
int c;
char ch;
do
{
cout<<"Binary Addition\n";
cout<<"1.accept a numbers(give space after each bit)\n";
cout<<"2.Display addtion of two numbers\n";
cout<<"Enter your choice..:\n";
cin>>c;
switch(c)
{
case 1:
s1=read();
s2=read();
break;
case 2:
cout<<"\nThe result of addition is : ";
s3=add(s1,s2);
display(s3);
break;
}
cout<<"\ndo you want to continue?\n";
cin>>ch;
}while(ch=='y'||ch=='Y');
return 0;
}

Dequeue Using Standard Template Library

/*
TITLE:Write C++ program using STL for Dequeue (Double ended queue)
*/

#include<iostream>
#include<deque>
using namespace std;

int main()
{
int v,a;
deque<int>dq;
deque<int>::iterator it;
cout<<"1.insert from front\n";
cout<<"2.insert from back\n";
cout<<"3.delete from front\n";
cout<<"4.delete from back\n";
cout<<"5.front element\n";
cout<<"6.last element\n";
cout<<"7.size of dequeue\n";
cout<<"8.display\n";
cout<<"9.exit\n";
while(1)
{
cout<<"\nenter choice\n";
cin>>v;
switch(v)
{
case 1: cout<<"enter element\n";
cin>>a;
dq.push_front(a);
break;
case 2: cout<<"enter element\n";
cin>>a;
dq.push_back(a);
break;
case 3: a=dq.front();
dq.pop_front();
cout<<"\n"<<a<<" is deleted";
break;
case 4: a=dq.back();
dq.pop_back();
cout<<"\n"<<a<<" is deleted";
break;
case 5: a=dq.front();
cout<<"front element is "<<a<<"\n";
break;
case 6: a=dq.back();
cout<<"last element is "<<a<<"\n";
break;
case 7: cout<<"size of deque is "<<dq.size();
break;
case 8:
for(it=dq.begin();it!=dq.end();it++)
{
cout<<*it<<"\t";
}
break;
case 9:
return 0;
}
}
}

Phonebook using File Handling

****To run this code Succesfully****
create phone.txt file in home directory of ubuntu  and then run this code

#include <iostream>
#include <fstream>
#include <cstring>
#include <iomanip>
using namespace std;

class phoneBook
{
char name[20],phno[15];
public:
void getdata();
void showdata();
 char *getname(){ return name; }
    char *getphno(){ return phno; }
    void update(char *nm,char *telno){
        strcpy(name,nm);
        strcpy(phno,telno);
    }
};

void phoneBook :: getdata(){
    cout<<"\nEnter Name : ";
    cin>>name;
    cout<<"Enter Phone No. : ";
    cin>>phno;
}

void phoneBook :: showdata(){
    cout<<"\n";
    cout<<setw(20)<<name;
    cout<<setw(15)<<phno;
}


int main(){
    phoneBook rec;
    fstream file;
    file.open("phone.txt", ios::ate | ios::in | ios::out | ios::binary );
    char c,ch,nm[20],telno[6];
    int choice,cnt,found=0;
    do{
        cout<<"\n*****Phone Book*****\n";
        cout<<"1) Add New Record\n";
        cout<<"2) Display All Records\n";
        cout<<"3) Search Telephone No.\n";
        cout<<"4) Search Person Name\n";
        cout<<"5) Update Telephone No.\n";
        cout<<"6) Exit\n";
        cout<<"Choose your choice : ";
        cin>>choice;
        switch(choice){
            case 1 : //New Record
                 rec.getdata();
                 file.write((char *) &rec, sizeof(rec));
cout<<"Record Added Succesfully\n";
                 break;

            case 2 : //Display All Records
                 file.seekg(0,ios::beg);
                 cout<<"\n\nRecords in Phone Book\n";
                 while(file){
                    file.read((char *) &rec, sizeof(rec));
                    if(!file.eof())
                        rec.showdata();
                 }
                 file.clear();
break;

            case 3 : //Search Tel. no. when person name is known.
                 cout<<"\n\nEnter Name : ";
                 cin>>nm;
                 file.seekg(0,ios::beg);
                 found=0;
                 while(file.read((char *) &rec, sizeof(rec)))
                 {
                    if(strcmp(nm,rec.getname())==0)
                    {
                        found=1;
                        rec.showdata();
                    }
                 }
                 file.clear();
                 if(found==0)
                    cout<<"\n\n---Record Not found---\n";
                    break;

            case 4 : //Search name on basis of tel. no
                 cout<<"\n\nEnter Telephone No : ";
                 cin>>telno;
                 file.seekg(0,ios::beg);
                 found=0;
                 while(file.read((char *) &rec, sizeof(rec)))
                 {
                    if(strcmp(telno,rec.getphno())==0)
                    {
                        found=1;
                        rec.showdata();
                    }
                 }
                 file.clear();
                 if(found==0)
                    cout<<"\n\n---Record Not found---\n";
                    break;

            case 5 : //Update Telephone No.
                 cout<<"\n\nEnter Name : ";
                 cin>>nm;
                 file.seekg(0,ios::beg);
                 found=0;
                 cnt=0;
                 while(file.read((char *) &rec, sizeof(rec)))
                 {
                    cnt++;
                    if(strcmp(nm,rec.getname())==0)
                    {
                        found=1;
                        break;
                    }
                 }
                 file.clear();
                 if(found==0)
                    cout<<"\n\n---Record Not found---\n";
                 else
                 {
                    int location = (cnt-1) * sizeof(rec);
                    cin.get(ch);
                    if(file.eof())
                        file.clear();

                    cout<<"Enter New Telephone No : ";
                    cin>>telno;
                    file.seekp(location);
                    rec.update(nm,telno);
                    file.write((char *) &rec, sizeof(rec));
                    file.flush();
                 }
                 break;
case 6:
break;
              }
cout<<"do you want to exit(y/n): ";
cin>>c;
    }while(c=='n'||c=='N');

file.close();
}