Showing posts with label Stack. Show all posts
Showing posts with label Stack. Show all posts

Using a stack as your data structure implement a program that will perform various operation | own implementation of Stack

Below program has own implementation of Stack data structure.



import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class StackApplication {
      private static final char L_PAREN = '(';
      private static final char R_PAREN = ')';
      private static final char L_BRACE = '{';
      private static final char R_BRACE = '}';
      private static final char L_BRACKET = '[';
      private static final char R_BRACKET = ']';

      public static void parenthesis(String s) {
            boolean checkParen = true;
            Stack<Character> stack = new Stack<Character>();
            try {
                  for (int i = 0; i < s.length(); i++) {
                        if (s.charAt(i) == L_PAREN)
                              stack.push(L_PAREN);
                        else if (s.charAt(i) == L_BRACE)
                              stack.push(L_BRACE);
                        else if (s.charAt(i) == L_BRACKET)
                              stack.push(L_BRACKET);
                        else if (s.charAt(i) == R_PAREN) {
                              if (stack.isEmpty())
                                    checkParen = false;
                              if (stack.pop() != L_PAREN)
                                    checkParen = false;
                        } else if (s.charAt(i) == R_BRACE) {
                              if (stack.isEmpty())
                                    checkParen = false;
                              if (stack.pop() != L_BRACE)
                                    checkParen = false;
                        } else if (s.charAt(i) == R_BRACKET) {
                              if (stack.isEmpty())
                                    checkParen = false;
                              if (stack.pop() != L_BRACKET)
                                    checkParen = false;
                        }
                  }
            } catch (Exception ex) {
            }
            if (checkParen) {
                  System.out.println(s + " has balanced parenthesis");
            } else {
                  System.out.println(s + " has not balanced parenthesis");
            }
            // return stack.isEmpty();
      }

      static void palindrome(String str) {
            System.out.print(str);
            String test = str;
            String newstr = "";
            // char[] letters;
            char letters2;
            // Extract the letters.37.
            char[] letters = str.toCharArray();
            // iterate through all the char in the sentences40.
            int len = letters.length;
            for (int i = 0; i < len; i++) {
                  // checks if current char is a letter and adds each char to
                  // newstr43.
                  if (Character.isLetter(letters[i])) {
                        letters2 = letters[i];
                        newstr += letters2;
                  }
            } // Extract the letters.50.
            letters = newstr.toCharArray();
            // System.out.print(letters);
            // Create an empty stack.53.
            Stack<Character> stack = new Stack<Character>();
            // The letters must "balance" up to the middle.56.
            int mid = letters.length / 2;
            // Push the first half.59.
            for (int i = 0; i < mid; i++) {
                  stack.push(letters[i]);
            }
            if (letters.length % 2 > 0) {
                  // Odd number => swallow middle letter.65.
                  mid = mid + 1;
            }
            boolean palindrom = true;
            for (int i = mid; i < letters.length; i++) {
                  char ch = stack.pop();
                  if (ch != letters[i]) {
                        // Mismatch => not a palindrome.73.
                        // return "is not a palindrome";
                        palindrom = false;
                  }
            }

            if (!(palindrom))
                  System.out.println(" is not a palindrome");
            else
                  System.out.println(" is a palindrome");
      }

      public static void main(String[] args) throws IOException {
            EquationEvaluator eq = new EquationEvaluator();
            // Prefix Notation
            System.out
                        .println("\n--------Postfix Notation using Stack------------");
            Scanner in = new Scanner(new FileReader("C:\\FileTest\\postfix.txt"));
            while (in.hasNextLine()) {
                  postfix(in.nextLine());
                  // eq.convertToPostfix(in.nextLine());
            }
            in.close();
            // Palindrome
            System.out.println("\n--------Palindromes using Stack------------");
            FileReader fob = new FileReader("C:\\FileTest\\palindrome.txt");
            in = new Scanner(fob);
            while (in.hasNextLine()) {
                  String line = in.nextLine();
                  palindrome(line);
            }
            in.close();

            fob = new FileReader("C:\\FileTest\\paren.txt");
            in = new Scanner(fob);
            // Parenthesis
            System.out
                        .println("\n------Balanced Parenthesis check using Stack-----");
            while (in.hasNextLine()) {
                  String line = in.nextLine();
                  parenthesis(line);
            }
            in.close();

            fob = new FileReader("C:\\FileTest\\reverse.txt");
            in = new Scanner(fob);
            // Parenthesis
            System.out
                        .println("\n--------Reverse a string using Stack------------");
            while (in.hasNextLine()) {
                  String line = in.nextLine();
                  Reverse(line);
            }
            in.close();
      }

      public static void Reverse(String line) {
            // Scanner scanner = new Scanner(System.in);
            String str = line;
            Stack<String> stack = new Stack<String>();
            // System.out.println("Enter a string to be reversed: ");
            // str = scanner.nextLine();
            if (str == null || str.equals("")) {
                  System.out
                              .println("It seems you aren't ready as yet to enter the string, ok buhbye !!");

                  System.exit(0);
            }
            for (int i = 0; i < str.length(); i++) {
                  // Here we push all the characters in the string one by one into the
                  // Stack29.
                  stack.push(str.substring(i, i + 1));
            }
            String strrev = "";
            while (!stack.isEmpty()) {
                  // Here we pop all the elements from the Stack one by one which is
                  // essentially reversing.36.
                  strrev += stack.pop();
            }
            System.out.println("Original string \"" + str);
            System.out.println("Reverse string \"" + strrev);
      }

      public static StringBuilder postfix(String infix_str) {
            Stack<Character> infix = null;
            StringBuilder postfix;
            Stack<String> postfix_str = null;
            infix = new Stack<Character>();
            postfix = new StringBuilder();
            postfix_str = new Stack<String>();
            int i = 0;
            boolean flag = true;
            int cheakOperatorExists = 0;
            while (!infix_str.isEmpty()) {
                  if (infix_str.charAt(i) == '(') {
                        infix.push(infix_str.charAt(i));
                        infix_str = infix_str.substring(i + 1, infix_str.length());
                  } else {
                        if (Character.getNumericValue(infix_str.charAt(i)) >= 0
                                    && Character.getNumericValue(infix_str.charAt(i)) <= 9) {
                              postfix.append(infix_str.charAt(i));
                              postfix_str.push(String.valueOf(infix_str.charAt(i)));// added
                              infix_str = infix_str.substring(i + 1, infix_str.length());
                        } else // operator
                        {
                              cheakOperatorExists = 1;
                              if (!(infix_str.charAt(i) == ')')) {
                                    int checkOperator = checkOperator(infix_str.charAt(i));

                                    if (checkOperator == 0) {

                                          // postfix= new StringBuilder();
                                          // return postfix;
                                    }
                                    if (infix.isEmpty()
                                                || infix.peek() == '('
                                                || !(hasPrecedence(infix_str.charAt(i), infix
                                                            .peek()))) {
                                          infix.push(infix_str.charAt(i));
                                          infix_str = infix_str.substring(i + 1, infix_str
                                                      .length());
                                    } else {
                                          postfix_str.push(String.valueOf(infix.peek()));// added
                                          postfix.append(infix.pop());
                                    }
                              } else {
                                    try {
                                          while (infix.peek() != '(') {
                                                postfix_str.push(String.valueOf(infix.peek()));// added
                                                postfix.append(infix.pop());
                                          }
                                          infix.pop();
                                          infix_str = infix_str.substring(i + 1, infix_str
                                                      .length());
                                    } catch (Exception EmptyStackException) {
                                          System.out.println("Unbalanced Parathesis");
                                          break;
                                    }
                              }
                        }
                  }
            }
            while (!infix.isEmpty()) {
                  postfix_str.push(String.valueOf(infix.peek()));// added
                  postfix.append(infix.pop());
            }
            System.out.println("Your expression in postfix notation is:" + postfix);

            return postfix;
      }

      static boolean hasPrecedence(char arg1, char arg2)// when to pop (true -
                                                                                    // pop)
      {
            String firstPreced = "^";
            String secondPreced = "*/";
            String thirdPreced = "+-";

            // EQUALS TO
            if ((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
                        && (thirdPreced.charAt(0) == arg2 || thirdPreced.charAt(1) == arg2)) {
                  return true;
            }
            if ((secondPreced.charAt(0) == arg1 || secondPreced.charAt(1) == arg1)
                        && (secondPreced.charAt(0) == arg2 || secondPreced.charAt(1) == arg2)) {
                  return true;
            }
            if (firstPreced.charAt(0) == arg1 && firstPreced.charAt(0) == arg2) {
                  return true;
            }

            if ((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
                        && (secondPreced.charAt(0) == arg2 || secondPreced.charAt(1) == arg2)) {
                  return true;
            }

            if ((thirdPreced.charAt(0) == arg1 || thirdPreced.charAt(1) == arg1)
                        && (firstPreced.charAt(0) == arg2)) {
                  return true;
            }

            return false;
      }

      public static int checkOperator(char operator) {
            if (operator == '^')
                  return 3;
            if (operator == '/' || operator == '*')
                  return 2;
            if (operator == '+' || operator == '-')
                  return 1;
            return 0;
      }

}


Stack.java


public class Stack<E> {
      private LinkedList<E> list; // LinkedList declaration

      /*
       * This constructor initiates a generic "stack" LinkedList.
       */

      public Stack() {
            list = new LinkedList<E>("stack");
      }

      /*
       * This constructor initiates a specific LinkedList "name."
       *
       * @param name passed String which the Stack will be referenced
       */

      public Stack(String name) {
            list = new LinkedList<E>(name);
      }

      /*
       * This method inserts an item on the front of the Stack.
       */

      public void push(E item) {
            list.insertAtFront(item);
      }

      /*
       * This method returns the length of the Stack.
       */

      public int lengthIs() {
            return list.lengthIs();
      }

      /*
       * This method returns the item at the front of the Stack.
       */

      public E peek() {
            E item;

            item = list.removeFromFront();
            list.insertAtFront(item);
            return item;
            // LinkedList<E> item = list.insertAtFront(list.removeFromFront ());
      }

      /*
       * This method prints the contents of the Stack.
       */

      public void print() {
            list.print();
      }

      /*
       * This method returns a Boolean relaying whether the Stack is empty or
       * full.
       */

      public boolean isEmpty() {
            return list.isEmpty();
      }

      public E pop() {
            E obj;
            int len = list.lengthIs();

            obj = peek();
            list.removeFromFront();
            // list.remove(len-1);

            return obj;
      }
}
LinkedList.java

//importing given exception package
public class LinkedList<T>
{
    private ListNode<T> firstNode; // first ListNode in list
    private ListNode<T> lastNode; // last ListNode in list
    int numElements; // total number of elements stored in list
    String name; // string representing LinkedList printed
   
    /*
     * This constructor sets name to "list," firstNode and lastNode to
     * null, and numElements to zero.
     */
   
    public LinkedList()
    {
        name = "list";
        firstNode = null;
        lastNode = null;
        numElements = 0;
    }
   
    /*
     * This constructor sets name to a passed String, firstNode and
     * lastNode to null, and numElements to zero.
     *
     * @param listName passed String to which name is set
     */
   
    public LinkedList( String listName )
    {
        name = listName;
        firstNode = null;
        lastNode = null;
        numElements = 0;
    }
   
    /*
     * This method inserts an item on the front of the list.
     *
     * @param item passed T to be added to the front of list
     */
   
    public void insertAtFront( T item )
    {
      // selection structure checks to see if firstNode and lastNode
      // are equal
        if( isEmpty() )
        {
            firstNode = lastNode = new ListNode<T>( item );
            numElements++;
        }
        else
        {
            firstNode = new ListNode<T>( item, firstNode );
            numElements++;
        }
    }
   
    /*
     * This method inserts an item on the back of the list.
     */
   
    public void insertAtBack( T item )
    {
      // selection structure checks to see if firstNode and lastNode
      // are equal
        if( isEmpty() )
        {
            firstNode = lastNode = new ListNode<T>( item );
            numElements++; // adding counter to numElements
        }
        else
        {
            ListNode<T> temp = new ListNode<T>(item);
            lastNode.setNext(temp);
            lastNode = temp;
            numElements++; // adding counter to numElements
        }
    }
   
    /*
     * This method removes the first item in the list and returns
     * the item unless the list is empty, in which case it throws
     * an exception.
     */
   
    public T removeFromFront() throws EmptyListException
    {
      // if statement throws an exception if list is empty
        if( isEmpty() )
        {
            throw new EmptyListException( name );
        }
       
        T removedItem = firstNode.getData(); // retrieve data being removed
       
        // selection structure updates firstNode and lastNode references
        if( firstNode == lastNode )
        {
            firstNode = lastNode = null;
            numElements--; // subtracting a counter from numElements
        }
        else
        {
            firstNode = firstNode.getNext();
            numElements--; // subtracting a counter from numElements
        }
       
        return removedItem; // returning item to be removed
    }
   
    /*
     * This method removes the last item in the list and returns it unless
     * this list is empty, in which case it throws an exception.
     */
   
    public T removeFromBack() throws EmptyListException
    {
      // if statement throws an exception if list is empty
        if( isEmpty() )
        {
            throw new EmptyListException( name );
        }
        
        T removedItem = lastNode.getData(); // retrieve data being removed
       
        // selection structure updates firstNode and lastNode references
        if( firstNode == lastNode )
        {
            firstNode = lastNode = null;
            numElements--; // subtracting a counter from numElements
        }
        else
        {
            ListNode<T> current = firstNode;
           
            // looping structure searches for node that's not last
            while( current.getNext() != lastNode )
            {
                current = current.getNext();
            }
           
            lastNode = current;
            current.setNext(null);
            numElements--; // subtracting a counter from numElements
        }
       
        return removedItem; // returning item to be removed
    }
   
    /*
     * This method removes an element from the list at a passed index unless
     * the list is empty or the index is out of range, in which cases
     * it throws an exception
     *
     * @param index passed index value to be removed
     */
   
    public void remove( int index ) throws EmptyListException, IndexOutOfBoundsException
    {
      // if statement throws an exception if list is empty
      if( isEmpty() )
        {
            throw new EmptyListException( name );
        }
     
      // if statement throws an exception if index is out of bounds
      if ( index > ( numElements - 1 ) || index < 0 )
      {
            throw new IndexOutOfBoundsException();
      }
     
      // removes item at front of the list if item to be removed
      // is at the front of the list
      if( index == 0 )
      {
            removeFromFront();
      }
      // removes item at the back of the list if index is
      // for last item in list
      else if( index == ( numElements - 1 ) )
      {
            removeFromBack();
      }
      // looping structure to determine which item to remove
      // when index is not for first or last item in list
      else{
            int i=0;
           
            ListNode<T> current = firstNode;
         
            // search for item in list up to lastNode
            while( current != lastNode )
            {
                  if( i != ( index - 1 ) )
                  {
                        current = current.getNext();
                        i++;
                  }
                  else{
                        current.setNext( current.getNext().getNext() );
                        current = current.getNext();
                        numElements--; // subtracting a counter from numElements
                        i++;
                  }
            }
      }
    }
   
    /*
     * This method returns the element at the given index unless the list is
     * empty or the index is out of range, in which case it throws an exception.
     *
     * @param index passed index value to be located
     */
   
    public T get( int index ) throws EmptyListException, IndexOutOfBoundsException
    {
      // if statement throws an exception if list is empty
      if( isEmpty() )
        {
            throw new EmptyListException( name );
        }
     
      // if statement throws an exception if index is out of bounds
      if( index > ( numElements - 1 ) || index < 0 )
      {
            throw new IndexOutOfBoundsException();
      }
     
      ListNode<T> current = firstNode;
     
      // loop searches for index
      for(int i=0; i<index ; i++ )
      {
            current = current.getNext();
      }
        return current.getData(); // returns found element
    }
   
    /*
     * This method finds items in the list and removes them unless
     * the list is empty, in which case it throws an exception.
     *
     * @param item passed item to be found and removed
     */
   
    public Boolean findAndRemove( T item ) throws EmptyListException
    {
      // if statement throws an exception if list is empty
        if( isEmpty() )
        {
            throw new EmptyListException( name );
        }
       
        // finds passed item's index
        int index = findItem(item);
       
        // if/else structure removes item from list if it is not
        // out of range and returns Boolean with success response
        if( index != -1 )
        {
            remove(index);
            return true;
        }
        else
        {
            return false;
        }
    }
   
    /*
     * This method searches for an item in the list and returns
     * that item. If the item is not found it returns -1.
     *
     * @param item passed item to be found
     */
   
    public int findItem( T item )
    {
      // if statement throws an exception if list is empty
        if( isEmpty() )
        {
            throw new EmptyListException( name );
        }
       
        int i=0;
       
        ListNode<T> current = firstNode;
       
        // compares passed item to item found next in list;
        // if item is the same it returns item's index
        while( current.getNext() != lastNode )
        {
            if( current.getData() == item )
            {
                return i;
            }
            current = current.getNext();
            i++;
        }
       
        return -1; // returns -1 if item is not found in list
    }
   
    /*
     * This method returns the number of elements in the list.
     */
   
    public int lengthIs()
    {
        return numElements;
    }
   
    /*
     * This method removes all elements from the list.
     */
   
    public void clear()
    {
      // setting firstNode and lastNode to null
        firstNode = lastNode = null;
        numElements = 0; // resetting numElements
    }
   
    /*
     * This method prints Empty NAMEOFLIST if list is empty, otherwise
     * it prints the name of the list and the list's contents
     */
   
    public void print()
    {
      // if statement prints that the list is empty if it is empty
        if( isEmpty() )
        {
           // System.out.printf( "Empty %s\n", name );
            return;
        }
       
        ListNode<T> current = firstNode;
       
        // Printing the name of the list if it is not empty
        //System.out.print( "The list '"+ name +"' contains:" );
      
        // for loop prints the elements in the list
        for( int i=0; i < numElements; i++ )
        {
            //System.out.printf( " " + current.getData() );
            current = current.getNext();
        }

       // System.out.printf( "\n\n" ); //spaces to make formatting correct
    }

    /*
     * This method checks to see if the list is empty, returning
     * true if it is empty and false if it not.
     */
   
    public Boolean isEmpty()
    {
        return firstNode == null;
    }
}
ListNode.java
package Jared; // package declaration



// each class represents one node in a list
public class ListNode<T>
{
      private T data; // data for this node
      private ListNode<T> nextNode; // reference to the next node
     
      /*
       * This constructor sets data to a passed value and nextNode
       * to null.
       *
       * @param object T instance passed to which data is set
       */
     
      public ListNode( T object )
      {
            this( object, null );
      }
     
      /*
       * This constructor sets data and nextNode to passed values.
       *
       * @param object T instance passed to which data is set
       * @param node passed ListNode<T> to which nextNode is set
       */
     
      public ListNode( T object, ListNode<T> node )
      {
            data = object;
            nextNode = node;
      }
     
      /*
       * This method sets data equal to a passed object.
       *
       * @param object passed T reference to which data is set
       */
     
      public void setData( T object )
      {
            data = object;
      }
     
      /*
       * This method returns data reference in node.
       */
     
      public T getData()
      {
            return data;
      }
     
      /*
       * This method sets nextNode to a passed reference.
       *
       * @param next passed reference to which nextNode is set
       */
     
      public void setNext( ListNode<T> next )
      {
            nextNode = next;
      }
     
      /*
       * This method returns nextNode.
       */
     
      public ListNode<T> getNext()
      {
            return nextNode;
      }
}

Output: