Computer Science and Information Technology: Data structure

Showing posts with label Data structure. Show all posts

Hello here is java code to change Infix expression to PostFix expression. infix expression is the expression we understand and do algebraic manipulation using BODMAS rule. Compilers uses PostFix expression to do calculation. Here we would make use of the stack we discussed in the previous articles.

If you are beginner in Java. The block at 10 - 13 is a initialization block.
Using constructor we set the max Size and the size of array to of that maxSize.
The core of this code is the method inToPostFix() Here we could explain the Algorithm in words

Initialize the empty stack.(astack[])
Scan each character of the given infix expression from left to right. (theExpression.charAt(i))
If the scanner Character is an Operand then add it to post fix string (theFinalExpression)
If the scanned character is an operator then

If the stack is empty, push the scanner operator int the stack.
If the stack is not empty then compare the precedence of the operator at the top of the stack. If the precedence of scanned is less then or equal to the precedence of operator at TOS, then pop TOS and add it to postfix string and push the scanned operator into the TOS. If the precedence of the scanned operator is higher then the operator at TOS then push operator to the stack.

If the scanned character is opening parenthesis then push it on to the stack and continue the above process steps until closing parenthesis is not scanned. When we get closed parenthesis then pop the operators from the stack until we reach opening parenthesis and then pop opening parenthesis from stack.
The process is continued until all the characters of infix expression are scanned. and pop all the remaining operators from stack and add them in to the postfix string in the way they pop out.

Here is the code:

import java.util.Scanner;

class InToPostFix
{
 int maxSize;
 char astack[];
 int TOS;
 String theFinalExpression;
 String theExpression;
 
 {
  TOS = -1;
  theFinalExpression = "";
 }
 
 InToPostFix(int maxSize, String theExpression)
 {
  this.maxSize = maxSize;
  this.astack = new char [maxSize];
  this.theExpression = theExpression;
 }

 void inToPostFix()
 {
  for(int i = 0; i< maxSize ;i++)
  {
   char element = theExpression.charAt(i);
   if(isOperand(element))
    theFinalExpression = theFinalExpression + element;
   else if(isOperator(element))
   {
    if(stackIsEmpty())
     push(element);
    else
    {
     int a;
     a = checkThePrecedence(element);
     if(a == 3) // element is of higher precedence:w
      push(element);
     else if(astack[TOS] != '(')
     {
      char operator = pop();
      theFinalExpression = theFinalExpression + operator;
      push (element);
     }
    }
   }
   else if(element == '(')
    push(element);
   else if(element == ')')
   {
    char temp;
    while(astack[TOS] != '(')
    {
     temp = pop();
     theFinalExpression = theFinalExpression + temp;
    }
    pop();// Remove the '(' from stack
   }
  }
  //while(!(stackisEmpty())):q
  while(TOS != -1)
  {
   char temp = pop();
   theFinalExpression = theFinalExpression + temp;
  }
 }

 char pop()
 {
  char item = astack[TOS];
  TOS -= 1;
  return item;
 }
 
 int checkThePrecedence(char element)
 {
  char item = astack[TOS];
  int assign, assign2;
  if (item == '$')
   assign = 3;
  else if (item == '*' || item == '/')
   assign = 2;
  else //(item == '+' || item == '-')
   assign = 1;
  if (element == '$')
   assign2 = 3;
  else if(element == '*' || element == '/')
   assign2 = 2;
  else //(element == '+' || element == '-')
   assign2 = 1;
  if(assign2 > assign)
   return 3; // element is of higher precedence
  else if(assign2 == assign)
   return 2; // element is in same as in stack
  else //(assign2 < assign)
   return 1; // element is of lower precedence
 }

 boolean stackIsFull()
 {
  if(TOS == maxSize - 1)
   return true;
  else
   return false;
 }

 boolean stackIsEmpty()
 {
  if(TOS == - 1)
   return true;
  else
   return false;
 }
 
 void push(char element)
 {
  TOS += 1;
  astack[TOS] = element;
 }
 
 static boolean isOperand(char element)
 {
  if((element >='a' && element <='z') || (element >='A' && element <='Z'))
   return true;
  else
   return false;
 }
 
        static boolean isOperator(char element)
        {
                if(element == '+' || element == '-' || element == '*' || element == '/' || element == '$')
                        return true;
                else
                        return false;
        }

 void displayFinal()
 {
  System.out.println("The Final Exptession is:-\n" + theFinalExpression);
 }

 public static void main(String []args)
 {
  Scanner input = new Scanner(System.in);
  Scanner input2 = new Scanner(System.in);
  System.out.println("Enter the InFix expression");
  String theExpression = input.nextLine();
  int maxSize = theExpression.length();
  InToPostFix inToPostFix = new InToPostFix(maxSize, theExpression);
  inToPostFix.inToPostFix();
  inToPostFix.displayFinal();
  int option;
  int next = 1;
  while(next == 1)
  {
   System.out.println("Option:- \tTo do:\n1\tConvert another expression\n2\tExit this program");
   option = input2.nextInt();
   switch(option)
   {
    case 1:
    {
     System.out.println("Enter the InFix expression");
     theExpression = input.nextLine();
     maxSize = theExpression.length();
     InToPostFix inToPostFixOb = new InToPostFix(maxSize, theExpression);
     inToPostFixOb.inToPostFix();
     inToPostFixOb.displayFinal();
     break;
    }
    case 2:
    {
     next = 0;
     System.out.println("Thank you:)");
     break;
    }
    default:
     System.out.println("Please Enter a valid option");
   }
  }
 }
}

Here we use $ for power operation. Power has the highest precedence. We use while loop in the main function and switch case to match the options you selected and call the selected methods. If I need to explain any of the code above I will always be available in the comment section. Thank you!

Hello here is Circular Queue. Here we create two separate file for the class and the main method. Everything is simple and common code here. I would like to introduce a new style to initialize a instance variables. The code block from line no 7 to line no 10 on CircularQueue.java is a Initialization Block. The benefit of creating any initializing block is that every constructors on the class would use the block to initialize variables. To initialize the static variables we just use static keyword before the block.

Here is CircularQueue.java file.

class CircularQueue
{
 int maxSize;
 int rear;
 int front;
 int aQueue[];
 {
  rear = -1;
  front = -1;
 }
 CircularQueue(int maxSize)
 {
  this.maxSize = maxSize;
  this.aQueue = new int[maxSize];
 }
 void enQueue(int item)
 {
  if(((rear+1) % maxSize) == front)
  {
   System.out.println("Queue is Full");
  }
  else
  {
   if (rear == front && front == -1)
   {
    front += 1;
   }
   rear = (rear+1) % maxSize;
   aQueue[rear] = item;
  }
 }
 void deQueue()
 {
  if(rear == front && rear == -1)
  {
   System.out.println("Queue is Empty.");
  }
  else
  {
   int item = aQueue[front];
   if(rear == front)
   {
    rear = -1;
    front = -1;
   }
   else
   {
    front = (front + 1) % maxSize;
   }
   System.out.println(item + " is deQueued from the Queue");
  }
 }
 
 String elementOrElements()
 {
  String send = (rear == front)? (" ") :("s ");
  return send;
 }
  
 void display()
 {
  int tmpfront = front;
  if(rear == front && rear == -1)
                {
                        System.out.println("Queue is Empty.");
                }
                else
  {
   System.out.println("The element"+ elementOrElements() + "on the Queue are:- ");
   for(int i=0; i<maxSize ; i++)
   {
    if(tmpfront != rear)
    {
     System.out.println(aQueue[tmpfront]);
     tmpfront = (tmpfront + 1) % maxSize;
    }
    else
    {
     System.out.println(aQueue[rear]);
     break;
    }
   }
  }
 }
}

And Here is CircularQueueTest.java file.

import java.util.Scanner;
public class CircularQueueTest
{
 public static void main(String []args)
 {
  Scanner input = new Scanner(System.in);
  System.out.print("Enter total no of elements to be in the queue:- ");
  int maxSize = input.nextInt();
  CircularQueue queue = new CircularQueue(maxSize);
  int select;
  int term = 0;
  while (term == 0)
  {
   System.out.print("\nOption:\tTo Do:\n1\tTo push element.\n2\tTo POP element.\n3\tTo Display the Queue elements.\n4\tTo Exit the Program.\nEnter your option:- ");
                 select = input.nextInt(); 
   switch(select)
   {
    case 1:
    {
     System.out.print("Enter element to insert in the Queue:- ");
     int ele = input.nextInt();
     queue.enQueue(ele); 
     break;
    }
    case 2:
    {
     queue.deQueue();
     break;
    }
    case 3:
    {
     queue.display();
     break;
    }
    case 4:
    {
     term = 1;
     System.out.println("Thank you!");
     break;
    }
    default:
     System.out.println("Enter a valid options");
   }
  }
 }
}

To fully understand this code you need to figure out what actually (front + 1) % maxSize do. Take your time and do some calculation. It would be better if calculate it and figure out it by yourself.

Hint:- (front + 1) % maxSize and (rear+1) % maxSize will always return 0 or < maxSize.

Hello Today we are here with a code of Stack Implementation using Array. We had already discussed about stack. Here we use 3 methods
1. To Push the elements
2. To POP the element
3. To display the elements on the stack.

This is no complex code. What we need to remember is that we should initialize TOS as -1 initially. Most beginner users could face error on the 6th and 11th line of code. Here at first we first create a reference variable at line 6 and create required length array in line 11.
If we use int aarray = new int[MaxSize]; in the class, it will create a zero-length array. as int MaxSize; means int MaxSize = 0;

Other are really simple algorithms. we need to check if Stack is full while pushing and need to check if stack is empty while using pop.

We need to increment TOS everytime we push a element and decrement whenever we pop a element.

import java.util.Scanner;
class Stack
{
 int TOS = -1;
 int MaxSize;
 int aarray[];
 
 Stack(int Max1Size)
 {
  this.MaxSize = MaxSize;
  this.aarray = new int[MaxSize];
 }
 void push(int a)
 {
  if(TOS == MaxSize - 1)
  {
   System.out.println("Stack is Full");
  }
  else
  {
   TOS += 1;
   aarray[TOS] = a;
   System.out.println(a +" is inserted in the Stack");
  }
  return;
  
 }
 void pop()
 {
  if (TOS == -1)
  {
   System.out.println("Stack is Empty.");
  }
  else
  {
   int item = aarray[TOS];
   TOS -= 1;
   System.out.println(item +" is poped Out from the Stack");
  }
  return;
 }
 void display()
 {
  if (TOS == -1)
  {
   System.out.println("Stack is Empty.");
  }
  else
  {
   System.out.println("Elements in Stack are:- ");
   for(int i = TOS; i >= 0; i--)
   {
    System.out.println(aarray[i]);
   }
  }
  return;
 }
}
public class StackTest
{
 public static void main(String args[])
 {
  Scanner input = new Scanner(System.in);
  System.out.println("Enter Maximum size of array");
  int MaxSize = input.nextInt();
  Stack astack = new Stack(MaxSize);
  int next = 0;
  while( next == 0)
  {
   System.out.println("\nOption:- \t To Do\n1 \t Push to stack. \n2 \t Pop from stack\n3 \t Display stack \n4 \t Exit the program");
   int select = input.nextInt();
   switch(select)
   {
    case 1:
     {
      System.out.println("Enter the element to push in the stack");
      int element = input.nextInt();
      astack.push(element);
      break;
     }
    case 2:
     {
      astack.pop();
      break;
     }
    case 3:
     {
      astack.display();
      break;
     }
    case 4:
     {
      next = 1;
      System.out.println("Thank You! :)");
      break;
     }
    default:
     {
      System.out.println("Please Enter a valid OPtion.");
      break;
     }
   }
  }
 }
}

This one of the code I had written at college in practical of DSA. Thank you :)

Stack is a data structure, which is not provided by any programming language as fundamentals data type. The last element inserted will be on top of the stack. Since deletion is done from same end, last element inserted will be the first element to be removed out from the stack and so on.

A stack is ordered collection of homogeneous data elements where the insertion and deletion operations only occurs at one end. The end is often known as Top Of the Stack (TOS).

As stack is not provided by any programming language we need to create our own stak. Use of control + Z (undo) is done through the use of Stack, Reversing of the string and checking the validation and matching the parentheses in programming language in compiler are done using programming language.

How Stack Works?

Stack is a one ended operation system. There are only two operations permitted in stack, Push and pop. Push to insert in the stack where as pop to delete the element form the stack. The TOS (Top Of the Stack) always point to the top position where the next can be popped off. We can add another element on the (TOS + 1).

When ever we try to push to the stack when the stack is full then we get the error which is known as Stack Overflow. Whenever we try to pop out from the empty stack then we get an error which is known as stack underflow.

When the stack is empty TOS = -1 When we insert the first element the TOS will be on 0. When we add another element again the TOS will be 1 and so on. So when new element is inserted the TOS will be incremented. When we pop the element the TOS will reduced by one. Let say TOS is on 5 now. when we pop a element, New TOS will be 4 then when we pop again the TOS will be 3 and so on. As we will get an error when we try push to the stack which is full and try to pop from the empty stack so we should always check whether we can pop and push or not.

Stack Implementation

we can implement stack using these two ways:
Static implementation: Using array
Dynamic Implementation: Using linked list

Static Implementation

Here we use array to realize the principle of stack. In array we can insert the data and access the data. Here we use the array in a such a way that we will insert the element in the TOS and access the element from TOS. So by default when the stack is empty TOS is -1. (As array begins with 0, we make TOS to -1 for easiness). Then we insert the element in the TOS+1 location of the array. So we pass element to be added, array and the TOS when ever we want to insert data in the Stack. And in the same way we will remove a data from the stack and reduce the TOS by one, thus we pass array and TOS during pop.

Algorithm:
#define MAX=5
push(s[MAX],element,TOS)
if TOS == MAX - 1
display "Stack is full"
else
TOS = TOS+1
s[TOS] = element
return;

pop(s[MAX],TOS)
if TOS == -1
display "Stack is Empty"
return 0
else
element = s[TOS]
TOS = TOS -1
return element

Application of Stack

It is used in recursive function calling. Function calling and returing process are in reverse order.
It is used to reverse a string.
It is used to evalutate and check the correction ness of the mathematical operation.
Implementation by word processors to perform UNDO REDO operations.
Used in parenthesis matching by compilers.

Details of the examples

How Parenthesis matching by compiler using Stack?

In every programming language there must be even numbers of parenthesis in the program. Here we will discuss how stack helps on parenthesis matching. So when we open a parenthesis the program will save that on the stack and search for next parenthesis. If it find another opening parenthesis it will add that on the stack again. And again keep looking for the parenthesis. When a closing parenthesis is found it will remove the pair (Opening and Closing) together and keep looking for parenthesis. If at the end The stack is empty there is not error in parenthesis else of the stack is not empty, there must error in parenthesis.

Stack for UNDO and REDO

Every actions will be stored in stack. so when we undo it the last command will be removed. if undo again the second last command and third last and going on..... In the same way the poped commands will be stored in another stack in case of REDO. so when we press redo we will get the last undo and the undo then after and then after.

We will be discussing about data structure. You should have knowledge in basic programming. We will be using C and Java for some example programming. Here we would discuss about Array, Structure, Pointer and Class. These are the topics we will be using throughout this article series in Data Structures.

Array

Array is primitive data member provided by C programming. Array is the collection of similar data types. Memory allocation of the array is sequential. ie. Array are stored in contiguous block of memory. Array only supports similar data type. Strings are the array of character with \0 at the end. \0 = NULL

Structure

Structure is the collection of different type of data type. In C programming Structure is the only way to create complex data type. Structure is the heterogeneous collection of data. Theoretically it will not occupy any memory unless we create the variable of that Structure. Memory allocation of structure is sequential. We can access members of array with dot operation(.) and Arrow operation(->). Dot operation is used to access memory of structure variables. and Arrow operation is used to access members from Pointer of the structure.

struct Person
{
    char name[30];
    int age;
    char address[40];
}

Self Referencial Structure

The structure that is pointing to self is called self referential structure. Ie a member of structure is pointer to that structure
struct list

struct List
{
    int age;
    struct List *next;
}

Union

It is similar as of the structure. The only difference is that union only occupy the memory of the largest member data. So we car use only one data of the union at a time. Can there be pointer to union? yes they can be :)

Courses to Complete During Software Engineering

Pointer

What is pointer in a word? A pointer is a variable. A pointer is a reference variable which store memory location. All the pointer occupy same memory bits. The pointer of the floating point data and the integer data. will occupy only 2 bits of memory. What is Void Pointer and null pointer? Void pointer is the pointer that can point to any kind of data type. This make use of type casting to to this job. Null pointer os the pointer which points to non or invalid address. Remember Structure pointer can only point to structure.

float data type is of 4 bit of memory, so when pointer points to the floating point it will point the base address of the variable. Points to the starting block of the memory for that variable.

Class

A class is data type. class is user defined variable that can be used to create objects. The difference between the structure and the class is that class have methods (Behaviour) which structure does not have. When ever the object are created the members are copied to the variables but not the methods. All the objects share the same methods. What is Abstract class? The class which have pure virtual function and cannot make any object.

Abstract means hiding the implementation details. We Drive the car but it is no concern to use how all the functions in the car works.

Computer Science and Information Technology

Search