Consider telephone book database of N clients. Make use of a hash table implementation to quickly look up client‘s telephone number.

#include<iostream>
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : Hashing with sll //
// //
// //
//////////////////////////////////////////////////////////////
using namespace std;
 struct node{
int value;
node* next;
}*HashTable[10];
class hashing{
public:

hashing(){

for(int i=0 ; i<10 ; i++){
HashTable[i]=NULL;
}
}


int HashFunction(int value){
return (value%10);
}

node* create_node(int x){
node* temp=new node;
temp->next=NULL;
temp->value=x;
return temp;
}

void display(){
for(int i=0 ; i< 10; i++){
node * temp=new node;
temp=HashTable[i];
cout<<"a["<<i<<"] : ";
while(temp !=NULL){
cout<<" ->"<<temp->value;
temp=temp->next;
}
cout<<"\n";
}
}


int searchElement(int value){
bool flag = false;
            int hash_val = HashFunction(value);
            node* entry = HashTable[hash_val];
            cout<<"\nElement found at : ";
            while (entry != NULL)
    {
                if (entry->value==value)
        {
                    cout<<hash_val<<" : "<<entry->value<<endl;
                    flag = true;
                }
                entry = entry->next;
            }
            if (!flag)
                return -1;
}

void deleteElement(int value){
int hash_val = HashFunction(value);
            node* entry = HashTable[hash_val];

            if (entry == NULL )
            {
            cout<<"No Element found ";
                return;
            }

            if(entry->value==value){
            HashTable[hash_val]=entry->next;
            return;
            }
            while ((entry->next)->value != value)
    {
                entry = entry->next;
            }
            entry->next=(entry->next)->next;


}

void insertElement(int value){
int hash_val = HashFunction(value);
           // node* prev = NULL;
            //node* entry = HashTable[hash_val];
            node* temp=new node;
            node* head=new node;
            head = create_node(value);
            temp=HashTable[hash_val];
            if (temp == NULL)
                        {

                           HashTable[hash_val] =head;
                            }
            else{
            while (temp->next != NULL)

            {
                temp = temp->next;
            }

                    temp->next =head;

            }


}
};

int main(){
int ch;
int data,search,del;
hashing h;
do{
cout<<"\nTelephone : \n1.Insert \n2.Display \n3.Search \n4.Delete \n5.Exit";
cin>>ch;
switch(ch){
case 1:cout<<"\nEnter phone no. to be inserted : ";
cin>>data;
h.insertElement(data);
break;
case 2:h.display();
break;
case 3:cout<<"\nEnter the no to be searched : ";
cin>>search;

if (h.searchElement(search) == -1)
            {
        cout<<"No element found at key ";
        continue;
            }
break;
case 4:cout<<"\nEnter the phno. to be deleted : ";
cin>>del;
h.deleteElement(del);
cout<<"Phno. Deleted"<<endl;
break;
}
}while(ch!=5);
return 0;
}

Implement all the functions of a dictionary (ADT) using hashing. Data: Set of (key, value) pairs, Keys are mapped to values, Keys must be comparable, Keys must be unique Standard Operations: Insert(key, value), Find(key), Delete(key)

#include<iostream>
#include<string.h>
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : Hashing with probing //
// //
// //
//////////////////////////////////////////////////////////////
using namespace std;

class HashFunction
  {
     typedef struct hash
{
long key;
char name[10];
}hash;
hash h[10];
   public:
HashFunction();
void insert();
void display();
int find(long);
void Delete(long);


  };

HashFunction::HashFunction()
  {
int i;
for(i=0;i<10;i++)
  {
h[i].key=-1;
strcpy(h[i].name,"NULL");
  }
  }
void HashFunction::Delete(long k)
  {
int index=find(k);
if(index==-1)
  {
cout<<"\n\tKey Not Found";
  }
else
  {
h[index].key=-1;
strcpy(h[index].name,"NULL");
cout<<"\n\tKey is Deleted";
  }


  }
int HashFunction::find(long k)
  {
int i;
for(i=0;i<10;i++)
  {
if(h[i].key==k)
  {
cout<<"\n\t"<<h[i].key<<" is Found at "<<i<<" Location With Name "<<h[i].name;
return i;
  }
  }
if(i==10)
      {
return -1;
  }

  }


void HashFunction::display()
  {
int i;
cout<<"\n\t\tKey\t\tName";
for(i=0;i<10;i++)
    {
cout<<"\n\th["<<i<<"]\t"<<h[i].key<<"\t\t"<<h[i].name;
  }
  }

void HashFunction::insert()
  {
char ans,n[10],ntemp[10];
long k,temp;
int v,hi,cnt=0,flag=0,i;

do
  {
if(cnt>=10)
  {
cout<<"\n\tHash Table is FULL";
break;
  }
cout<<"\n\tEnter a Telephone No: ";
cin>>k;
cout<<"\n\tEnter a Client Name: ";
cin>>n;
hi=k%10;// hash function
if(h[hi].key==-1)
  {
h[hi].key=k;
strcpy(h[hi].name,n);
  }
     else
    {

if(h[hi].key%10!=hi)
  {
temp=h[hi].key;
strcpy(ntemp,h[hi].name);
h[hi].key=k;
strcpy(h[hi].name,n);
for(i=hi+1;i<10;i++)
    {
if(h[i].key==-1)
    {
h[i].key=temp;
strcpy(h[i].name,ntemp);
flag=1;
break;
      }
    }
for(i=0;i<hi && flag==0;i++)
    {
if(h[i].key==-1)
    {
h[i].key=temp;
strcpy(h[i].name,ntemp);
break;
      }
         }
    }
else
  {
for(i=hi+1;i<10;i++)
    {
if(h[i].key==-1)
    {
h[i].key=k;
strcpy(h[i].name,n);
flag=1;
break;
      }
    }
for(i=0;i<hi && flag==0;i++)
    {
if(h[i].key==-1)
    {
h[i].key=k;
strcpy(h[i].name,n);
break;
      }
       }
  }

  }
    flag=0;
     cnt++;
     cout<<"\n\t..... Do You Want to Insert More Key: y/n";
     cin>>ans;
  }while(ans=='y'||ans=='Y');

  }



int main()
  {
long k;
int ch,index;
char ans;
HashFunction obj;
do
  {
cout<<"\n\t***** Telephone (ADT) *****";
cout<<"\n\t1. Insert\n\t2. Display\n\t3. Find\n\t4. Delete\n\t5. Exit";
cout<<"\n\t..... Enter Your Choice: ";
cin>>ch;
switch(ch)
  {
case 1: obj.insert();
break;
case 2: obj.display();
break;
case 3: cout<<"\n\tEnter a Key Which You Want to Search: ";
cin>>k;
index=obj.find(k);
if(index==-1)
  {
cout<<"\n\tKey Not Found";
  }
break;
case 4: cout<<"\n\tEnter a Key Which You Want to Delete: ";
cin>>k;
obj.Delete(k);
break;
case 5:
break;
  }
cout<<"\n\t..... Do You Want to Continue in Main Menu:y/n ";
cin>>ans;
  }while(ans=='y'||ans=='Y');
  }

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"
#include<string.h>
using namespace std;
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : BST //
// //
// //
//////////////////////////////////////////////////////////////
typedef struct node
{

 char k[20];
 char m[20];
 class node  *left;
 class node * right;
}node;

class dict
{
public:
 node *root;
 void create();
 void disp(node *);
 void insert(node * root,node *temp);
 int search(node *,char []);
 int update(node *,char []);
 node* del(node *,char []);
 node * min(node *);
};

void dict :: create()
{
 class node *temp;
 int ch;

 do
 {
  temp = new node;
  cout<<"\nEnter Keyword:";
  cin>>temp->k;
  cout<<"\nEnter Meaning:";
  cin>>temp->m;

  temp->left = NULL;
  temp->right = NULL;

  if(root == NULL)
  {
   root = temp;
  }
  else
  {
   insert(root, temp);
  }
  cout<<"\nDo u want to add more (y=1/n=0):";
  cin>>ch;
 }
 while(ch == 1);

}

void dict ::  insert(node * root,node *temp)
{
 if(strcmp (temp->k, root->k) < 0 )
 {
  if(root->left == NULL)
   root->left = temp;
  else
   insert(root->left,temp);
 }
 else
 { if(root->right == NULL)
   root->right = temp;
  else
   insert(root->right,temp);
 }

}

void dict:: disp(node * root)
{
 if( root != NULL)
 {
  disp(root->left);
  cout<<"\n Key Word :"<<root->k;
  cout<<"\t Meaning :"<<root->m;
  disp(root->right);
 }
}

int dict :: search(node * root,char k[20])
{
 int c=0;
 while(root != NULL)
 {
  c++;
  if(strcmp (k,root->k) == 0)
  {
   cout<<"\nNo of Comparisons:"<<c;
   return 1;
  }
  if(strcmp (k, root->k) < 0)
   root = root->left;
  if(strcmp (k, root->k) > 0)
   root = root->right;
 }

 return -1;
}
int dict :: update(node * root,char k[20])
{
 while(root != NULL)
 {
  if(strcmp (k,root->k) == 0)
  {
   cout<<"\nEnter New Meaning ofKeyword"<<root->k;
   cin>>root->m;
   return 1;
  }
  if(strcmp (k, root->k) < 0)
   root = root->left;
  if(strcmp (k, root->k) > 0)
   root = root->right;
 }
 return -1;
}
node* dict :: del(node * root,char k[20])
{
 node *temp;

 if(root == NULL)
 {
  cout<<"\nElement No Found";
  return root;
 }

 if (strcmp(k,root->k) < 0)
 {
  root->left = del(root->left, k);
  return root;
 }
 if (strcmp(k,root->k) > 0)
 {
   root->right = del(root->right, k);
   return root;
 }

 if (root->right==NULL&&root->left==NULL)
 {
  temp = root;
  delete temp;
  return NULL;
  }
  if(root->right==NULL)
  {
  temp = root;
  root = root->left;
  delete temp;
  return root;
  }
  else if(root->left==NULL)
  {
  temp = root;
  root = root->right;
  delete temp;
  return root;
  }
  temp = min(root->right);
  strcpy(root->k,temp->k);
  root->right = del(root->right, temp->k);
  return root;

}

node * dict :: min(node *q)
{
 while(q->left != NULL)
 {
  q = q->left;
 }
 return q;
}



int main()
{
 int ch;
 dict d;
 d.root = NULL;


 do
 {
  cout<<"\nMenu\n1.Create\n2.Disp\n3.Search\n4.Update\n5.Delete\nEnter Ur CH:";
  cin>>ch;

  switch(ch)
  {
case 1: d.create();
  break;
case 2: if(d.root == NULL)
  {
  cout<<"\nNo any Keyword";
  }
  else
  {
  d.disp(d.root);
  }
  break;
case 3: if(d.root == NULL)
 {
  cout<<"\nDictionary is Empty. First add keywords then try again ";
 }
  else
 {

        cout<<"\nEnter Keyword which u want to search:";
  char k[20];
  cin>>k;

  if( d.search(d.root,k) == 1)
  cout<<"\nKeyword Found";
  else
  cout<<"\nKeyword Not Found";
 }
  break;
case 4:
  if(d.root == NULL)
  {
  cout<<"\nDictionary is Empty. First add keywords then try again ";
 }
  else
  {
  cout<<"\nEnter Keyword which meaning  want to update:";
  char k[20];
  cin>>k;
  if(d.update(d.root,k) == 1)
  cout<<"\nMeaning Updated";
  else
  cout<<"\nMeaning Not Found";
  }
  break;
case 5:
  if(d.root == NULL)
  {
  cout<<"\nDictionary is Empty. First add keywords then try again ";
  }
  else
  {
  cout<<"\nEnter Keyword which u want to delete:";
  char k[20];
  cin>>k;
  if(d.root == NULL)
  {
  cout<<"\nNo any Keyword";
  }
  else
  {
  d.root = d.del(d.root,k);
    }
   }
  }
 }
 while(ch<=5);
 return 0;

}

For given expression eg. a-b*c-d/e+f construct inorder sequence and traverse it using postorder traversal(non recursive).

#include<iostream>
#include<stack>
using namespace std;
//////////////////////////////////////////////////////////////
// //
//   Name : Vivek S. Sharma //
// Title : BST Expression Conversion //
// //
// //
//////////////////////////////////////////////////////////////
class Btree{
typedef struct node{
int data;
struct node * right ,*left;
}node;

public :
node * root,*temp;
Btree(){
root=new node;
root=NULL;
}
void create(){
temp=new node;

cout<<"\nEnter the data : ";
cin>>temp->data;
temp->left=temp->right=NULL;
if(root==NULL){
root=temp;
}
else{
insert(root,temp);
}
}

void insert(node * root, node * temp){
char ch;
cout<<"\nDo u want to enter "<<temp->data<<" as left or rright child of "<<root->data<<" : ";
cin>>ch;
if(ch=='l'){
if(root->left==NULL){
root->left=temp;
}
else
insert(root->left,temp);
}
else{
if(root->right==NULL)
root->right=temp;
else
insert(root->right,temp);
}

}
void postOrder_recursive(node * root){
if(root!=NULL){
postOrder_recursive(root->left);
postOrder_recursive(root->right);
cout<<"\t "<<root->data;
}
}
void postOrder_nonRecursive(node* root){
if(!root)
{
cout<<"\nEmpty";
return;
}
stack<node *> s;
stack<node*> p;
s.push(root);
while(!s.empty()){
node * cur=s.top();
p.push(cur);
s.pop();
if(cur->left)
s.push(cur->left);
if(cur->right)
s.push(cur->right);
}
while(!p.empty()){
cout<<"\t"<<p.top()->data;
p.pop(); }
}
//Extra Part : Inorder
void InOrder_nonRecursive(node* root){
if(!root)
{
cout<<"\nEmpty";
return;
}
stack<node *> s;
stack<node*> p;

while(true){
while(root!=NULL){
//cout<<"\t "<<root->data;
s.push(root);
root=root->left;
}
if(s.empty())
return;
root=s.top();
s.pop();

cout<<"\t "<<root->data;
root=root->right;
}
}
//Extra Part : PreOrder
void PreOrder_nonRecursive(node* root){
if(!root)
{
cout<<"\nEmpty";
return;
}
stack<node *> s;
stack<node*> p;

while(true){
while(root!=NULL){
cout<<"\t "<<root->data;
s.push(root);
root=root->left;
}
if(s.empty())
return;
root=s.top();
s.pop();

//cout<<"\t "<<root->data;
root=root->right;
}
}
void display(node* root, int space){

if(root==NULL)
return ;
space +=3;
display(root->right,space);
cout<<"\n";
for(int i=3; i<=space ; i++){
cout<<"  ";}
cout<<root->data<<"\n";
display(root->left,space);
}

};
int main(){
Btree b;
int ch;
do{
b.create();
cout<<"\nDo u wnat to insert more elements :1/0 ";
cin>>ch;

}while(ch!=0);
b.display(b.root,0);
cout<<"\nRecursive Post Order : ";
b.postOrder_recursive(b.root);
cout<<"\nNon Recursive Post Order : ";
b.postOrder_nonRecursive(b.root);
cout<<"\nNon Recursive In Order : ";
b.InOrder_nonRecursive(b.root);
cout<<"\nNon Recursive Pre Order : ";
b.PreOrder_nonRecursive(b.root);
return 0;
}

In any language program mostly syntax error occurs due to unbalancing delimiter such as (),{},[]. Write C++ program using stack to check whether given expression is well parenthesized or not.

#include<iostream>
using namespace std;
#define size 20
class stack{
char stk[size];
int top;
public:
stack(){
top=-1;
}
void push(char x){
stk[++top]=x;
}
char pop(){
char temp=stk[top];
top--;
return temp;
}
bool empty(){
if(top==-1)
return true;
else return false;
}
char tops(){
char ch;
ch=stk[top];
return ch;
}


};
int main(){
stack st;
string s;
char ch, temp;
int i=0;
cout<<"\nEnter the expression : ";
cin>>s;
if(s[0]==')' || s[0]==']' || s[0]=='}')
cout<<"\nInvalid";
else{
while(s[i]!='\0'){
ch=s[i];
switch(ch){
case '(' : st.push(ch);break;
case '{' : st.push(ch);break;
case '[' : st.push(ch);break;
case ')' : if(st.tops()=='(')temp=st.pop();break;
case '}' : if(st.tops()=='{')temp=st.pop();break;
case ']' : if(st.tops()=='[')temp=st.pop();break;
}
i++;
}
if(st.empty())
cout<<"\nValid ";
else
cout<<"\nInvalid";
}

return 0;
}

Implement C++ program for expression conversion-

a) infix to prefix, b)prefix to postfix,

c) prefix to infix, d) postfix to infix and e) postfix to prefix.

#include"iostream"

#include"string"

using namespace std;

class post

{

      char a[20];

      int top;

      string s[20];

public:

      post()

      {

            top = -1;

      }

      void push(string );

      string pop();

      void get();

      void post2infix();

      void post2prefix();

};

void post::get()

{

      cout << "Enter a postfix Equation : ";

      cin >> a;

}

void post::push(string s1)

{

      top++;

      s[top] = s1;

}

string post::pop()

{

      string s1;

      s1 = s[top];

      top--;

      return s1;

}

void post::post2infix()

{

      int i = 0;

      string s1, s2, s3, ch;

      while (a[i] != '\0')

      {

            ch = a[i];

            if (a[i] == '+' || a[i] == '-' || a[i] == '*' || a[i] == '/')

            {

                  s1 = pop();

                  s2 = pop();

                  s3 = s2 + a[i] + s1;

                  push(s3);

                  i++;

            }

            else

            {

                  push(ch);

                  i++;

            }

      }

      cout << "Infix Equation is : ";

      for (int m = 0; m <= top; m++)

      {

            cout << s[m];

      }

      cout << endl;

}

void post::post2prefix()

{

      int i = 0;

      string s1, s2, s3, ch;

      while (a[i] != '\0')

      {

            ch = a[i];

            if (a[i] == '+' || a[i] == '-' || a[i] == '*' || a[i] == '/')

            {

                  s1 = pop();

                  s2 = pop();

                  s3 = a[i] + s2 + s1;

                  push(s3);

                  i++;

            }

            else

            {

                  push(ch);

                  i++;

            }

      }

      cout << "Prefix Equation is : ";

      for (int m = 0; m <= top; m++)

      {

            cout << s[m];

      }

      cout << endl;

}

int main()

{

      int x, t;

      post s;

      do

      {

            cout << "\n 1.Insert Equation \n 2.Postfix2Infix \n 3.Postfix2Prefix : ";

            cin >> t;

            switch (t)

            {

            case 1:

                  s.get();

                  break;

            case 2:

                  s.post2infix();

                  break;

            case 3:

                  s.post2prefix();

                  break;

            default:

                  cout << "\n Invalid Input ";

            }

            cout << "\n Display Menu 1.Yes 2.No ";

            cin >> x;

      } while (x == 1);

}