Question

Requirements

Both the stack and queue were implemented correctly according data structure and java standard practices. The stack was used to implement a post-fix calculator using push, pop, peek and other stack concepts. The queue was used to implement the palindrome using add, remove, insert and other queue concepts. Both implementations produced the expected output. All submission requirements were followed.

Test Harness for the first part:

public class StackCalcTest {
public static void main(String[] args) {
StackCalc stackCalc = new StackCalc();
String[] values = {"3", "5", "9", "*", "+"};
for(int i = 0; i < 5; i++) {
stackCalc.stack.push(values[i]);
}
System.out.println(stackCalc.stack);
System.out.println(stackCalc.answer());
}
}

Concepts

Stacks

Queues

Linked List

Programming Problems

Stack - Implementation. You will be able to use the push, pop and peek of Stack concept.

Post-Fix calculator - When an arithmetic expression is presented in the postfix form, you can use a stack to evaluate the expression to get the final value. For example: the expression 3 + 5 * 9 (which is in the usual infix form) can be written as 3 5 9 * + in the postfix. More interestingly, post form removes all parentheses and thus all implicit precedence rules.

Program Implementation Requirements

Use the stack concept to create a post-fix calculator. I will be using a test-harnessPreview the document to run your program. Please make sure it meets the requirements to be run by the test harness.

LinkedList/Queue - Implementation.

New concert tickets are available. You have to enter the names of the people in order to form a line. However, you will later find out that a few people are not eligible to buy tickets because they represent scalpers instead of actual concert goers. You will have to remove those people from the line. A special raffle will be done and the result of the raffle will insert a person to the front of the line. You will have to issue tickets to the first 10 people in line, but there are 15 people total in line. The others will have to put into a waitlist queue for the next available ticket.

Program Implementation Requirements

Use the Linked List (Original Line) and a Queue (waitlist) concept to create this program. The class name will be ConcertTickets. You will have the following methods: insertIntoLine(Person p), removeFromLine(Person p), addToWaitList(Person p), assignedTicket().

Click here for the test-harnessPreview the document.

import java.util.ArrayList;
public class ConcertTicketsTest {
public static void main(String[] args) {
ArrayList<String> listOfPeople = new ArrayList<String>();
listOfPeople.add("Monica");
listOfPeople.add("Chandler");
listOfPeople.add("Rachel");
listOfPeople.add("Phobe");
listOfPeople.add("Joey");
listOfPeople.add("Ross");
listOfPeople.add("John");
listOfPeople.add("Daenerys");
listOfPeople.add("Arya");
listOfPeople.add("Sansa");
listOfPeople.add("Rob");
listOfPeople.add("Ned");
ConcertTickets concertTickets = new ConcertTickets(listOfPeople);
concertTickets.removeFromLine("Ned");
concertTickets.removeFromLine("Ross");
concertTickets.insertInFront("Cersei");
System.out.println(concertTickets.printWaitlist());
System.out.println(concertTickets.listOfTicketHolders());
}
}

Submission:

Please submit .java file(s) only.

Answer 1

Programming Problems Stack - Implementation:

Stack: - A stack is a linear data structure which follows the LIFO (last-in-first-out) principle. That means the objects can be inserted or removed only at one end of it also called as a top. push Pushes an item onto the top of the stack.

Program in java Postfix problem:-

import java.io.*;
class Stack                                     //class create of stack
{
   private int[] a;
   private int top,m;
   public Stack(int max)
   {
     m=max;
     a=new int[m];
     top=-1;
   }
   public void push(int key)                       //function  create push
   {
     a[++top]=key;
   }
   public int pop()                                //function create pop
   {
     return(a[top--]);
   }
}
class StackCalc{                                     // class create satcalc
   public int calculate(String s)
   {
     int n,r=0;
     n=s.length();
     Stack a=new Stack(n);
     for(int i=0;i<n;i++)
     {
       char ch=s.charAt(i);
       if(ch>='0'&&ch<='9')
         a.push((int)(ch-'0'));
       else
       {
         int x=a.pop();
         int y=a.pop();
         switch(ch)
         {
           case '+':r=x+y;
              break;
           case '-':r=y-x;
              break;
           case '*':r=x*y;
              break;
           case '/':r=y/x;
              break;
           default:r=0;
         }
         a.push(r);
       }
     }
     r=a.pop();
     return(r);
   }
}
class PostfixEvaluation                            //Man class create and function call
{
   public static void main(String[] args)throws IOException
   {
     String input;
     while(true)
     {
       System.out.println("Enter the postfix expresion");
       input=getString();
       if(input.equals(""))
         break;
       StackCalc stac=new StackCalc();
       System.out.println("Result:- "+StackCalc.calculate(input));
     }
   }
   public static String getString()throws IOException
   {
     DataInputStream inp=new DataInputStream(System.in);
     String s=inp.readLine();
     return s;
   }
}

// output runs on the machine it will take input from the console.  

LinkedList/Queue - Implementation.:-in java

import java.util.*;

import java.io.*;

/* Class arrayQueue */
class ConcertTickets
{
protected int Queue[] ;
protected int front, rear, size, len;

/* Constructor */
public arrayQueue(int n)
{
size = n;
len = 0;
Queue = new int[size];
front = -1;
rear = -1;
}
/* Function to check if queue is empty */
public boolean isEmpty()
{
return front == -1;
}
/* Function to check if queue is full */
public boolean isFull()
{
return front==0 && rear == size -1 ;
}
/* Function to get the size of the queue */
public int getSize()
{
return len ;
}
/* Function to check the front element of the queue */
public int peek()
{
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
return Queue[front];
}
/* Function to insert an element to the queue */
public void insertIntoLine(Person p)
{
if (rear == -1)
{
front = 0;
rear = 0;
Queue[rear] = p;
}
else if (rear + 1 >= size)
throw new IndexOutOfBoundsException("Overflow Exception");
else if ( rear + 1 < size)
Queue[++rear] = p;
len++ ;
}
/* Function to remove front element from the queue */
public int removeFromLine()
{
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
else
{
len-- ;
int ele = Queue[front];
if ( front == rear)
{
front = -1;
rear = -1;
}
else
front++;
return ele;
}
}
/* Function to display the status of the queue */
public void display()
{
System.out.print("\nQueue = ");
if (len == 0)
{
System.out.print("Empty\n");
return ;
}
for (int i = front; i <= rear; i++)
System.out.print(Queue[i]+" ");
System.out.println();
}
/* Function to addtowaitlist the status of the line*/
addToWaitList(int  p)

{

if (rear == 0)
{
front = 0;
rear = 0;
Queue[rear] = p;
}
else if (rear + 1 >= size)
throw new IndexOutOfBoundsException("Overflow Exception");
else if ( rear + 1 < size)
Queue[++rear] = p;
len++ ;

}

/* Function to assigned ticket the status of the queue */

assignedTicket()

{

if (rear + 1 >= size)
throw new IndexOutOfBoundsException("Overflow Exception");
else if ( rear + 1 < size)
Queue[++rear] = p;
len++ ;

}

}
/* Class QueueImplement */
public class QueueImplement
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);

System.out.println("Array Queue Test\n");
System.out.println("Enter Size of Integer Queue ");
int n = scan.nextInt();
/* creating object of class arrayQueue */
ConcertTickets q = new ConcertTickets(n);
/* Perform Queue Operations */
char ch;
do{
System.out.println("\n Ticket Options");
System.out.println("1. insertIntoLine");
System.out.println("2. removeFromLine");
System.out.println("3. addToWaitList");
System.out.println("4.assignedTicket");
System.out.println("5. check full line of ticket");
System.out.println("6. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
try
{
q.insertIntoLine( scan.nextInt() );
}
catch(Exception e)
{
System.out.println("Error : " +e.getMessage());
}   
break;   
case 2 :
try
{
System.out.println("Removed Element = "+q.removeFromLine());
}
catch(Exception e)
{
System.out.println("Error : " +e.getMessage());
}
break;   
case 3 :
try
{
System.out.println("Peek Element = "+q.addToWaitList());
}
catch(Exception e)
{
System.out.println("Error : "+e.getMessage());
}
break;
case 4 :
System.out.println("Empty status = "+q.assignedTicke());
break;
case 5 :
System.out.println("Full status = "+q.isFull());
break;
case 6 :
System.out.println("Size = "+ q.getSize());
break;   
default : System.out.println("Wrong Entry \n ");
break;
}
/* display Queue */
q.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);

} while (ch == 'Y'|| ch == 'y');
}
}

/*Output runs the program java file*/