Sunday, 14 February 2016

Java Program Reads an Infix Expression, Converts the Expression to Postfix form and then Evaluates the Postfix Expression

import java.util.Scanner;

class CharacterStack {

    int size, top;
    char stack[];
   
    CharacterStack (int num) {
        size = num;
        top = -1;
        stack = new char[num];
    }
   
    public void push(char n) {
        stack[++top] = n;
    }
   
    public char pop() {
        return stack[top--];
    }
   
    public char peek() {
        return stack[top];
    }
   
    public boolean isEmpty() {
        return top == -1;
    }
   
    public boolean isFull() {
        return top == size;
    }
}

public class InfixToPostfix {  
   
    public static String infixToPostfix(String infix) {
       
        char symbol;
        String postfix = "";
        CharacterStack operator = new CharacterStack(infix.length());
       
        for(int i=0; i < infix.length(); ++i) {
           
            symbol = infix.charAt(i);
           
            if(Character.isLetter(symbol))
                postfix += symbol;
           
            else if( symbol ==  '(' || symbol == '{' || symbol == '[' )
                operator.push(symbol);
           
            else if( symbol ==  ')' || symbol == '}' || symbol == ']' ) {
                while( !( operator.peek() == '(' ||operator.peek() == '{' ||operator.peek() == '[') )
                    postfix += operator.pop();
                operator.pop();
            } else {
                while(!operator.isEmpty() && !(operator.peek()=='(') && isPref(symbol) <= isPref(operator.peek()))
                    postfix += operator.pop();
                operator.push(symbol);
            }
        }
        while(!operator.isEmpty())
            postfix += operator.pop();
        return postfix;
    }
   
    private static int isPref(char c) {
        if(c == '+' || c == '-') 
            return 1;
        if(c == '*' || c == '/' || c == '%')
            return 2;
        if(c == '^')
            return 3;
        return 0;
    }
   
    private static int postfixEvaluation(String infixToPostfix) {
        String alphabet = "abcdefghijklmnopqrstuvwxyz";
        int[] counts = new int[26];
        Scanner input = new Scanner(System.in);
       
          for(int i=0; i < infixToPostfix.length(); i++) {
              char ch = Character.toLowerCase(infixToPostfix.charAt(i));
              int index = alphabet.indexOf(ch);
              if(index != -1)
                   counts[index] += 1;
        }
       
        for(int i=0; i<26; i++) {
            if(counts[i] > 0) {
                System.out.print(" Enter value of " + alphabet.charAt(i) + " : ");
                counts[i] = input.nextInt();
            }  
        }
       
        CharacterStack token = new CharacterStack(infixToPostfix.length());
       
        for(int i=0; i < infixToPostfix.length(); i++) {           
            char c = infixToPostfix.charAt(i);
           
            if(Character.isLetter(c)) {               
                int index = alphabet.indexOf(c);
                token.push((char)counts[index]);
            }
            else {
                int x = token.pop();
                int y = token.pop();
                int calculation = calculation(y, x, c);
                token.push((char)calculation);
            }
        }
        return (int)token.pop();
    }
   
    private static int calculation(int a, int b, char c) {
        switch(c) {
            case '+' : return a+b;
            case '-' : return a-b;
            case '*' : return a*b;
            case '/' : return a/b;
            case '%' : return a%b;
            case '^' : return (int) Math.pow(a, b);
        }
        return 1;
    }
   
    public static void main(String[] ar) {
       
        Scanner input = new Scanner(System.in);
       
        System.out.print(" Enter Infix expression : ");
        String str = input.nextLine();
       
        String infixToPostfix = infixToPostfix(str);
        System.out.println(" Postfix Expression : " + infixToPostfix);
       
        int postfixEvaluation = postfixEvaluation(infixToPostfix);
        System.out.println("\n Evaluation of Postfix: " + postfixEvaluation);
    }
}
Posted by at No comments:

Circular Queue Program Using Array

import java.util.Scanner;

class CircularQueueImplement {

    int cQueue[], front, rear, size;

    public CircularQueueImplement(int n) {
          size = n;
          cQueue= new int[size];
          front = rear = -1;
    }

    public int enqueue(int item) {
        if(front == -1)
            front++;
          return cQueue[++rear] = item;
    }

    public int dequeue() {
        int item = cQueue[front];
          if(front == rear)
              front = rear = -1;
          else
              front = (front + 1) % size;
        return item;
    }

    public int peek() {
          return  cQueue[front];
    }

    public void display() {
        for(int i=front; i<=rear; i++) {
            if( (rear == size) && (front != 0) )
                i = 0;
              System.out.printf("%5d", cQueue[i]);
          }
    }

    public boolean isEmpty() {
          return (rear==-1)||(front == rear+1);
    }

    public boolean isFull() {
        return front == rear + 1 || (front == 0 && rear == size-1);
    }
}

public class CircularQueue {

    public static void main(String[] ar) {

          Scanner input = new Scanner(System.in);
         boolean empty;
          System.out.print(" Enter size of Queue : ");
          int size = input.nextInt();
          CircularQueueImplement circularQueue = new CircularQueueImplement(size);
         
           while(true) {
              System.out.println("\n 1. Enqueue \n 2. Dequeue \n 3. Peek \n 4. Display \n Press 0 for exit ");
              System.out.print(" Enter your choice : ");
              int choice = input.nextInt();

              switch(choice) {
                   case 0:
                       return;

                   case 1:
                    boolean full = circularQueue.isFull();
                    if(full) {
                        System.out.println(" Queue is Full.");
                        break;
                    }
                    System.out.print("\n Enter item to be insert : ");
                    System.out.println(" Enqueue Item : " + circularQueue.enqueue(input.nextInt()));
                       break;

                   case 2:
                    empty = circularQueue.isEmpty();
                    if(empty) {
                        System.out.println(" Queue is Empty.");
                        break;
                    }
                    System.out.println(" Dequeue Item : " + circularQueue.dequeue());
                       break;

                   case 3:
                    empty = circularQueue.isEmpty();
                    if(empty) {
                        System.out.println(" Queue is Empty.");
                        break;
                    }
                    System.out.println(" Front Element : " + circularQueue.peek());
                       break;

                   case 4:
                    empty = circularQueue.isEmpty();
                    if(empty) {
                        System.out.println(" Queue is Empty.");
                        break;
                    }
                       circularQueue.display();
                       break;
                   default:
                       System.out.println("\n Please enter valid choice ...!");
              }
          }
    }
}


Posted by at No comments:

Linear Queue Program Using Array

import java.util.Scanner;

class LinearQueueArray {

    int queue[], size, front, rear;

    public LinearQueueArray(int n) {
          size = n;
          queue = new int[size];
          front = rear = -1;
    }

    public int enqueue(int item) {
        if(front == -1)
              ++front;
          return queue[++rear] = item;
    }

    public int dequeue() {
        return queue[front++];
    }

    public int peek() {
          return queue[front];
    }

    public void display() {
          for(int i=front; i<=rear; i++)
              System.out.printf("%5d", queue[i]);
          System.out.println();
    }

    public boolean isEmpty() {
        return (front == rear + 1 || (front == -1 && rear == -1));
    }

    public boolean isFull() {
        return rear == size - 1;
    }
}

public class LinearQueue {

    public static void main(String[] ar) {
         
          Scanner input = new Scanner(System.in);
         
          System.out.print("\n Enter the length of queue : ");
          int size = input.nextInt();

          LinearQueueArray linearQueueArray = new LinearQueueArray(size);
         
          while(true) {
              System.out.println("\n 1. Enqueue \n 2. Dequeue \n 3. Peek \n 4. display \n Press 0 for exit.");
              System.out.print("\n Enter Your Choice : ");
              int ch = input.nextInt();
              switch(ch) {
                   case 0:                     
                       return;

                   case 1:
                    boolean full = linearQueueArray.isFull();
                    if(full) {
                        System.out.println(" Queue is Full.");
                        break;
                    }
                    System.out.print(" Enter the Element to Enqueue : ");
                    int enqueue = linearQueueArray.enqueue(input.nextInt());
                    System.out.println(" Enqueue Item : " + enqueue);
                       break;

                   case 2:
                    boolean empty = linearQueueArray.isEmpty();
                    if(empty) {
                        System.out.println(" Queue is Empty.");
                        break;
                    }
                    int dequeue = linearQueueArray.dequeue();
                    System.out.println(" Dequeue Item : " + dequeue);
                       break;

                   case 3:
                    boolean emp = linearQueueArray.isEmpty();
                    if(emp) {
                        System.out.println(" Queue is Empty.");
                        break;
                    }
                    int peek = linearQueueArray.peek();
                    System.out.println(" Front Element : " + peek);
                       break;

                   case 4:
                    boolean e = linearQueueArray.isEmpty();
                    if(e) {
                        System.out.println(" Queue is Empty.");
                        break;
                    }
                       linearQueueArray.display();
                       break;

                   default:
                       System.out.println("\n Wrong Choice Entered. ");
              }
          }
    }
}
Posted by at No comments:

Stack Program Using Array

import java.util.Scanner;

class StackArray {

    private static int maxSize;
    private static int[] stackArray;
    private int top;

    public StackArray(int s) {
          maxSize = s;
          stackArray = new int[maxSize];
          top = -1;
    } // End of constructor
   
    public boolean isEmpty() {
        return top == -1;
    }
   
    public boolean isFull() {
        return top == maxSize-1;
    }
   
    public int push(int item) {       
          return stackArray[++top] = item;
    } // End of push()

    public int pop() {
          return stackArray[top--];
    } // End of pop()

    public int peek() {
          return stackArray[top];
    } // End of peek()

    public void display() {
        System.out.println(" inside disp " + stackArray[top]);      
          for(int i=0; i<=top; i++)
              System.out.printf(" %5d", stackArray[i]);
          System.out.println();
    } // End of display()
} // End of class StackArray

public class Stack {

    public static void main(String[] ar) {

          Scanner input = new Scanner(System.in);
          System.out.print("\n Enter the size of Stack : ");
          StackArray stackArray = new StackArray(input.nextInt());
          int ch;

          while(true) {
              System.out.printf("\n 1. Push \n 2. Pop \n 3. Peek \n 4. Display \n Press 0 for exit. \n");
              System.out.print("\n Enter your choice : ");
              ch = input.nextInt();
              switch(ch) {
                   case 0:
                       return;
                   
                   case 1:
                    boolean full = stackArray.isFull();
                    if(full) {
                        System.out.println(" Stack is Full. ");
                        break;
                    }           
                    System.out.print("\n Enter the element to push : ");                   
                    int push = stackArray.push(input.nextInt());                               
                    System.out.println(" Pushed Item : " + push);
                    break;
               
                   case 2:
                    boolean empty = stackArray.isEmpty();
                    if(empty) {
                        System.out.println(" Stack is Empty. ");
                        break;
                    }
                    System.out.println(" Poped Element : " + stackArray.pop());
                    break;
                   
                   case 3:
                    boolean emp = stackArray.isEmpty();
                    if(emp) {
                        System.out.println(" Stack is Empty. ");
                        break;
                    }
                    System.out.println(" Top Element : " + stackArray.peek());
                       break;
                   
                   case 4:
                    boolean e = stackArray.isEmpty();
                    if(e) {
                        System.out.println(" Stack is Empty. ");
                        break;
                    }                   
                       stackArray.display();
                       break;
                    
                   default :
                       System.out.println(" \n Wrong choice entered...! \n");
              } // End of switch
          }  // End of do while loop
    } // End of main()

} // End of class Stack
Posted by at No comments:

Saturday, 13 February 2016

List ADT Using Linked List

import java.util.Scanner;

class ListNode {
    private int data;
    private ListNode link;

    ListNode() {
          data = 0;
          link = null;
    }

    ListNode(int d, ListNode n) {
          data = d;
          link = n;
    }

    public void setLink(ListNode n) {
          link = n;
    }

    public ListNode getLink() {
          return link;
    }

    public int getData() {
          return data;
    }
}

public class ListADT {

    ListNode start;

    ListADT() {
          start = null;
    }

    public void insert(int data) {
          ListNode listNode = new ListNode(data, null);
          listNode.setLink(null);
         
          if(start == null) {
              start = listNode;
              return;
          }

          ListNode ptr = start;

          while(ptr.getLink() != null)
              ptr = ptr.getLink();
          ptr.setLink(listNode);
        listNode.setLink(null);
    }

    public void display() {
          ListNode ptr = start;
          if(start == null) {
              System.out.println(" No Element ");
              return;
          }
          while(ptr != null) {
              System.out.print(" -> " + ptr.getData());
              ptr = ptr.getLink();
        }
    }
   
    public static void main(String[] ar) {

          Scanner input = new Scanner(System.in);

          ListADT listADT = new ListADT();
          System.out.print(" Enter length : ");
          int len = input.nextInt();
         
          for(int i=1; i<=len; i++) {
              System.out.print(" Enter " + i + " element : ");
              int data = input.nextInt();
              listADT.insert(data);
          }
         
          System.out.println("\n List Element : ");
          listADT.display();
    }

}

Output:


Posted by at No comments:

Binary search program using array

Non-Recursive :
import java.util.Scanner;

public class BinarySearch {

    public static int search(int[] a, int searchKey) {
          int start = 0, end = a.length-1;

          while(start <= end) {
              int mid = (start + end)/2;

              if(searchKey == a[mid])
                   return mid;
              if(searchKey < a[mid])
                   end = mid-1;
              else
                   start = mid+1;
          }
          return -1;
    }

    public static void main(String[] args) {
          Scanner input = new Scanner(System.in);

          System.out.print("\n Enter the length of array : ");
          int size = input.nextInt();

          int[] ar = new int[size];
          System.out.println("\n Enter " + size + " integer (sorted order) : ");

          for(int i=0; i<size; i++)
              ar[i] = input.nextInt();

          System.out.print(" Enter Search Item : ");
          int searchKey = input.nextInt();

          int temp = search(ar, searchKey);

          if(temp == -1)
              System.out.println("\n Item not found ");
          else
              System.out.println("\n Item found at position : " + (temp+1));
    }//End of main()
}//End of BinarySearch class

Output:



Recursive :
import java.util.Scanner;

public class BinarySearchRecursive {

    static int search(int[] a, int low, int high, int searchKey) {

        if(low>high)
            return -1;

        int mid = (low + high)/2;

        if(searchKey == a[mid])
            return mid;

        if(searchKey < a[mid])
            return search(a, low, mid-1, searchKey);
        else
            return search(a, mid+1, low, searchKey);
    }

    public static void main(String[] args) {
          Scanner input = new Scanner(System.in);

          System.out.print("\n Enter the length of array : ");
          int size = input.nextInt();
          int[] ar = new int[size];

          System.out.println("\n Enter " + size + " integer (sorted order) : ");

          for(int i=0; i<size; i++)
              ar[i] = input.nextInt();

          System.out.print(" Enter Search Item : ");
          int searchKey = input.nextInt();
         
          int temp = search(ar, 0, ar.length, searchKey);

          if(temp == -1)
              System.out.println("\n Item not found ");
          else
              System.out.println("\n Item found at position : " + (temp+1));
    }//End of main()
}//End of BinarySearchRecursive class

Output:



Posted by at No comments:
Subscribe to: Posts (Atom)