Monday, October 20, 2014

Circular Dubly Linked List in C++

#include <iostream>
using namespace std;

class node 
{
   int value;
   node *head;
   node *tail;
   node *next;
   node *previous;
   node *current;
public:
  
   node()
   {
       value =0;
       head=NULL;
       tail=NULL;
       next=NULL;
   }
  
   bool isEmpty ()
   {
      if (head==NULL) return true;
   else
      return false ;
   }

   void SetFirstElement (int value)
   {
       if (isEmpty () )
        {
           node *n = new node ;
           n->next=NULL;
           n->value=value;
           n->previous=NULL;
           head=tail=current=n;
        }

   }

   void AddItem (int value)
   {
       if (isEmpty () ) SetFirstElement (value);
  
       else
        {
          node *n= new node;
          n->value=value;
          n->previous=current;
          n->next=NULL;
          tail->next=n;
          current=tail=n;
      
        }
    }
  
   void Remove () 
   {
      if (head!=NULL)
      {
         node *temp;
         temp=head;
         head=head->next;
         delete temp;
      }
      else
         cout <<"EMPTY"<<endl;
   }

  
   void print ()
  {
           if(isEmpty ())
           {
               cout<<"List is empty"<<endl;
           }
          
           else
               cout<<"The list is"<<endl;
  
           current=head;
          
           while(current!=NULL)
           {
               cout<<current->value<<endl;
               current=current->next;
           }
   }
   void add_at_begining (int value)
   {
      node *temp= new node ;
      temp->value=value;
      temp->previous=NULL;
      temp->next=head;
      head=temp;
   }

   bool search (int value)
   {
    current=head;
   
    while (current!=NULL)
      {
          if(current->value==value) return true;
          current=current->next;
      }
   }

   void AddItem(int back, int value)
   {
    current=head;
   
    if(search(back))
    {
      while(current!=NULL)
         {
            if(current->value==back)
               {
                  node *temp=new node;
                  temp=current->next;
                  node *temp1=new node;
                  temp1->value=value;
                  temp1->next=temp;
                  temp1->previous=current;
                  current->next=temp1;
               }
            current=current->next;
         }
      }
   }

   void sort ()
   {
       for(int i=0;i<10;i++)
       {
           current=head;
           while(current!=NULL)
           {  
               if(current->next==NULL) break;
               if(current->value>current->next->value)
               {
                      swap(current,current->next);
               }
      current=current->next;
           }
       }
   }
  
   void Remove (int value)
   {
    current=head;
   
    while(current!=NULL)
    {
      if(current->value==value)
      {
         node *temp=new node;
         temp=current;
         node *temp1=new node;
         temp1->previous=temp->previous;
         temp1->value=current->next->value;
         temp1->next=current->next->next;
         current=temp1;
         delete temp;
      }
     
      current=current->next;
    }
  }

  void print_previous (int value)
  {
    if(search(value))
    {
      current=head;
      while (current!=NULL)
         {
            if(current->value==value)
            {
                cout<<"CURRENT"<<current->value<<endl<<"Previous:"<<current->previous->value<<endl;
            }
           
            current=current->next;  
         }
     }
   }

   int check_elements();

   void swap(node *element1,node *element2 )
   {
      node *temp1,*temp2= new node;
      int temp=element1->value;

      temp1=element1;
      temp1->value=element2->value;
      element1=temp1;

      temp2=element2;
      temp2->value=temp;

      element2=temp2;
   }

  void check (int value)
  {
     current=head;
     while(current!=NULL)
     {
         if(current->value==value){ swap(current,current->next);break;}
     
         current=current->next;
     }
  }

  int max_value ()
  {
      current=head;
  
      int temp=0;
      while(current!=NULL)
        {
           if(temp<current->value) temp=current->value;
           current=current->next;
        }
     return temp;
  }

};

int main()
{
    return 0;
}

Checking Parenthesis code - in C++

#include<iostream>
#include<string>
#include<cassert>

using namespace std;

template<class T> class StackADT
{
public:

    virtual void initialstack() = 0;
    virtual bool isEmpty() const = 0;
    virtual bool isFull() const = 0;
    virtual void push(const T& otheritem) = 0;
    virtual T top() const = 0;
    virtual void pop() = 0;
};

template <class T> class Stack : public StackADT<T>{
    int size, tos;
    T *list;

public:
    Stack(int size)
    {
        if(size <= 0)
        {
            cout << "Size of the array must be positive" << endl;
            cout << "By default it is set to 100" << endl;
            this->size = 100;
        }
        else
        {
            this->size = size;
        }

        tos = 0;
        list = new T[this->size];
    }
    void initialstack()
    {
        tos = 0;
    }
    bool isFull() const
    {
        return(tos == size);
    }
    bool isEmpty() const
    {
        return(tos == 0);
    }
    void push(const T& otheritem)
    {
        if(!isFull())
        {
            list[tos] = otheritem;
            tos++;
        }
        else
        {
            cout << "Can not add t a full stack" << endl;
        }
    }
    void pop()
    {
        if(!isEmpty())
        {
            tos--;
        }
        else
        {
            cout << "Canno remove from a empty stack" << endl;
        }
    }
    T top() const
    {
        assert( tos != 0);
        return list[tos-1];
    }
    void copystack(const Stack<T>& otherstack)
    {
        delete[] list;
        size = otherstack.size;
        tos = otherstack.tos;

        list = new T[size];
        for(int j=0; j<tosl j++)
        {
            list[j] = otherstack.list[j];
        }
    }
    ~Stack()
    {
        delete []list;
    }

};


int main()
{

   int i, l;
   Stack<char> stack(100);
   char str[100] = {"{(A+B-C}"};
  
   l=strlen(str);
   for(i=0; i<l; i++)
   {
      
       if((str[i] == '(') ||  (str[i] == '{') || (str[i] == '['))
       {
            stack.push(str[i]);
       }
       else if((str[i] == ')') ||  (str[i] == '}') || (str[i] == ']'))
       {
             if(str[i] == ')')
           {
             if(stack.top() == '(')
                    {
                         stack.pop();
                    }
                    else
                    {
                          cout << "The parenthesis are not balanced "<< endl;
                    }
             }
             else if(str[i] == '}')
             {
                 if(stack.top() == '{')
                 {
                     stack.pop();
                 }
                 else
                 {
                     cout << "The parenthesis are not balanced "<< endl;
                 }
             }
             if(str[i] == ']')
             {
                 if(stack.top() == '[')
                 {
                     stack.pop();
                 }
                 else
                 {
                     cout << "The parenthesis are not balanced "<< endl;
                 }
             }
         }
     }
   
   if(stack.isEmpty())
   {
       cout << "The parenthesis are balanced " << endl;
   }
  

 
   return 0;
}

Convertiong Infix to Postfix code - in C++

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;

class infix_to_postfix
{

protected:
    string exp;
    string infixexp;
    stack<char> charstack;

    bool prcd(char a, char b)
    {
        return a > b;
    }

   public:
            infix_to_postfix(string str)
            {
                 exp = str;
            }

            void push_to_stack()
            {
                  for(int i = 0; exp[i]; ++i)
                  {
                         if(exp[i] == ' ')
                             continue;

                   if(isalnum(exp[i]))
                   {
                         infixexp += exp[i];
                   }

             else
             {
                      while(!charstack.empty() && prcd(exp[i], charstack.top()))
                      {
                              infixexp += charstack.top();
                               charstack.pop();
                      }

                              charstack.push(exp[i]);
             }
        }

        while(!charstack.empty())
        {
            infixexp += charstack.top();
            charstack.pop();
        }
    }

    string print()
    {
        return infixexp;
    }


   
};

class evaluate {
public:
    evaluate(string str)
    {
        exp = str;
    }

    void peform()
    {
        int res;

        for(int i = 0; i < exp.length(); i++)
        {
            if(isalnum(exp[i]))
            {
                nums.push(exp[i] - '0');
            }
            else
            {
                if(!nums.empty())
                {
                    int a = nums.top();
                    nums.pop();
                    int b = nums.top();
                    nums.pop();

                    res = doit(b, exp[i], a);
                }
                nums.push(res);
            }
        }
    }

    int retres()
    {
        return nums.top();
    }

protected:
    string exp;
    stack<int> nums;

private:
    int doit(int a, char c, int b)
    {
        switch(c)
        {
        case '+':
            return a + b;
            break;

        case '-':
            return a - b;
            break;

        case '*':
            return a * b;
            break;

        case '/':
            return a / b;
            break;
        }
    }
};

int main()
{
    string infixstr;
    infix_to_postfix itop("5 * 2 + 3 * 1 - 9");

    itop.push_to_stack();
    infixstr = itop.print();

    cout << infixstr << endl;

    evaluate ev(infixstr);
    ev.peform();

    int res = ev.retres();

    cout << res << endl;

    return 0;
}

Josephus Problem Solvation code in C++

#include<iostream>
using namespace std;

struct node{

    int val;
    node *next;
};

void insert_node(int);
void print();
void josephus(int);
node *head,*nptr,*tptr;

int main(){

    head = NULL;
    int start,n;
    cout << "Enter node number: " << endl;
    cin >> n;
    insert_node(n);
    cout << "The persons are:" << endl;
    print();
    cout << "Enter start number: " << endl;
    cin >> start;
    josephus(start);
    return 0;
}

void josephus(int start){

    node *ptr,*qptr;
    qptr = ptr = head;
    for (int i = 1; i < start; i++){

            ptr = ptr->next;
            qptr = ptr;
    }
    while (ptr->next != ptr){

        qptr->next = ptr->next->next;
        ptr = qptr->next;
        qptr = ptr;
    }
    head =  ptr;
    cout << "The person survived is :" << ptr->val << endl;
}
void insert_node (int n){

    for(int i = 0; i < n; i++){

        nptr = new node;
        nptr->val = i+1;
        nptr->next = NULL;
        if (head == NULL){

            head = nptr;
            tptr = nptr;
        }
        else{

            tptr->next = nptr;
            tptr = nptr;
        }
    }
    tptr->next = head;
}
void print(){

    tptr = head;
    cout << tptr->val << "->";
    tptr = tptr->next;
    while (head != tptr){

        cout << tptr->val << "->";
        tptr = tptr->next;
    }
    cout<< endl;
}