USE JAVA

THIS IS THE ASSIGNMENT 1

package Javalab;

import java.util.Scanner;

public class Assignment1

{

static class stack

{

int top = -1;

//Counter the number in the array

char items[] = new char [1000];

//Set the max of the array is 1000

void push(char a)

{

if(top == 999)

{

System.out.println("The stack is full ");

}

else

{

//Just make sure the first element of the stack is the place of the 0

items[++top] = a;

}

}

char pop()

{

if (top

{

System.out.println("The stack is underflow ");

//check the stack is empty or not

return '\0';

}

else

{

char element = items[top];

top--;

return element;

}

}

boolean isEmpty()

{

return(top == -1) ? true: false;

//If the top is not equal -1, it will return false. Otherwise it will return true

}

}

//Matching left and right bracket

static boolean isMatch(char character1, char character2)

{

if(character1 == '(' && character2 == ')')//have to satisfy two option

{

return true;

}

else if(character1 == '{' && character2 == '}')

{

return true;

}

else if(character1 == '[' && character2 == ']')

{

return true;

}

else

{

return false;

}

}

static boolean balanced (char a[])

{

stack s = new stack();

for(int i = 0;i

{

//we put all bracket into one stack then we matching them

if(a[i] == '(' || a[i] == '{' || a[i] == '[')

{

s.push(a[i]);

}

if(a[i] == ')' || a[i] == '}' || a[i] == ']')

{

//first we check the stack is empty or not

if(s.isEmpty())

{

return false;

}

else if( !isMatch(s.pop(),a[i]))//if the result of the function is false

{

return false;

}

}

}

if(s.isEmpty())

{

return true;

}

else

{

return false;

}

}

public static void main(String[] args)

{

System.out.println("Enter the bracket you want to match: ");

Scanner sc= new Scanner(System.in);

String str = sc.nextLine();

// Creating array of string length

char[] ch = new char[str.length()];

// Copy character by character into array

for (int i = 0; i

{

ch[i] = str.charAt(i);

}

if (balanced(ch))

{

System.out.println("Balanced ");

}

else {

System.out.println("Not Balanced ");

}

sc.close();

}

}

1. Using your favorite programming language, implement a singly linked list with the following operations: addFirst, removeFirst, addLast, removeLast, getFirst, getLast, size. 2. [2 bonus marks*] Write and implement a recursive algorithm that shows all the elements of the single linked list, starting from the head. Explain the worst-case running time of your algorithm. 3. Implement a stack on the singly linked list with the operations of Lab Assignment 1. Hint: Using the same Stack class you implemented, change the array to an object of the singly linked list class. The functionality of push and pop is now based on the methods of the linked list class. 4. Practical application 1: Balanced parentheses. (a) Implement the balanced-bracket checker algorithm of Lab Assignment 1 using the singly linked list implementation of the stack. (b) Explain how your algorithm checks for balanced parenthesis in O(n), when the input is a string of length n. 5. Implement a queue on the singly linked list of Item #1, with the following operations: enqueue, dequeue, front, size, isEmpty. Note: both operations, enqueue and dequeue, must run in O(1). 6. Practical application 2: The merge problem. Given two sorted lists of integers, A and B, the aim is to merge A and B, producing a sorted list S. (a) Write an algorithm that stores A and B in two queues (one in each queue), merges A and B, and outputs a sorted list S in O(n) worst-case time. Note: your algorithm must use queues for A, B and S. (b) Implement your algorithm in your favorite programming language. (c) Explain how your algorithm runs in O(n), where n is the length of S. (d) [2 bonus marks*] Run your algorithm on randomly generated sorted lists A and B of different sizes: 100, 200, 300, ..., 2000 and record the CPU time taken by the algorithm. Create a table (or a plot) and explain how your algorithm runs in O(n) by inspecting your results. * Maximum 2 bonus marks. Submission: 1. Your assignment must be submitted during the lab session in the section you are registered in. Any submission on or 15 minutes prior to the end of the lab session will not be accepted and a zero mark will be given. Late assignments will be given a zero mark. Submissions by email will not be accepted. 2. Provide the source code for all your programs. Run the balanced-bracket checker during the lab and show they work for various sample inputs, including (more may be included during the evaluation in the lab; a and d are balanced): a. (9*[3* {[(3+3)/5]*7}]) c. ((3*(9-(4*(6-5)))) b. {3* (2+[3-[4/[6/9]]]}) d. {2-{3* {6/[[[(((9-0)))]]]}}/7} 4. Run the Merge algorithm with the following inputs: (i) A = 1,3,5,7,9 B= 2,3,6,8,10 (ii) A = 1,2,3,4,5 B = 6,7,8,9,10 (iii) A = 2,4,8,16,32 B = 1,3,5,7,9 (iv) A = 10,11,12,13 B= 1,2,3,4 5. Run the recursive algorithm that shows the elements of the queue in the examples of #4. 6. Explain how your singly linked list, stack and queue work. These will be asked when the lab assignment is submitted. Marks will be deducted if not clear how your algorithms and programs work. (11) n