Programming assignment 1 Solution

The input to all the programs MUST be read from a file and NOT from command line unless specified. A command line should specify asking for the input file name for all the programs.

1. Implement insertion, deletion and search for a doubly-linked list as defined in class. The input has a list of pairs of an integer key followed with an operation delimited by spaces. An example of input file contents would look like 1.in 3.in 5.in 3.del 2.in 1.sch. There are a total of 3 operations in the input file given:

1. in operation: Insertions to the doubly-linked list are to be performed at the head unless otherwise specified. Duplicate insertions are to be rejected and DUPLICATE KEY should be output to the console.

3.in – Insert node with value 3 at the head of the list

5.in_8 - Insert node with value 5 between the node with value 8 and the next node. If the node with value 8 is a tail node, insert at the end.

2. del operation: Delete the node with the value of the integer key as specified.

6.del – Delete the node that has value 6 in the doubly linked list. If no such node exists, ignore the command.

3. sch operation: Search for the node with the value of the integer key as specified. If such a node exists, output FOUND to the console, else NOT FOUND.

2.sch – Search for a node with value 2 in the doubly linked list. If present output FOUND to the console. If not, output NOT FOUND to the console.

Output:

The list before operation and the list after operation displayed on the screen standard outout (not into a file).





Example:

Input file contents:

1.in 3.in 5.in 3.del 2.in 1.sch 4.in_5

Output of the program should look like:

Operation: 1.in

List before: NULL

List after: 1

Operation: 3.in

List before: 1

List after: 3 - 1

Operation: 5.in

List before: 3 - 1

List after: 5 - 3 - 1

Operation: 3.del

List before: 5 - 3 - 1

List after: 5 - 1

Operation: 2.in

List before: 5 - 1

List after: 2 - 5 - 1

Operation: 1.sch

FOUND

Operation: 4.in_5

List before: 2 - 5 - 1

List after: 2 - 5 - 4 - 1









2. Implement insertion (or push) and deletion (or pop) for a stack and a circular queue with length of n keys as defined in class. An example of input file contents for stack would look like 10 1.push 3.push 5.push pop 2.push and for queue it would look like 13 1.in 3.in 5.in 3.del 2.in. There are two operations for stack and two operations for queue. The first number in both the files indicates the size of the stack and queue respectively.

1. Stack operations: push and pop are the two operations for stack.

3.push – Push value 3 onto the stack, in case of overflow, print OVERFLOW and halt the program.

pop - Pops out the first value on the stack and outputs to the console.

2. Circular Queue operations: in and del are the two operations for the circular queue.

3.in – Insert value 3 into the circular queue, in case of overflow, print OVERFLOW and halt the program.

del - Deletes the first value at the front of the circular queue.

Output:

The list before operation and the list after operation displayed on the screen standard outout (not into a file).





Example:

Input file contents for STACK:

10 1.push 3.push 5.push pop

Output of the program should look like:

Operation: 1.push

List before: EMPTY

List after: 1

Operation: 3.push

List before: 1

List after: 3 - 1

Operation: 5.push

List before: 3 - 1

List after: 5 - 3 - 1

Operation: pop

List before: 5 - 3 - 1

List after: 3 - 1

Input file contents for CIRCULAR QUEUE:

7 1.in 3.in 5.in del

Output of the program should look like:

Operation: 1.in

List before: EMPTY

List after: 1

Operation: 3.in

List before: 1

List after: 1 - 3

Operation: 5.in

List before: 1 - 3

List after: 1 - 3 - 5

Operation: del

List before: 1 - 3 - 5

List after: 3 - 5





3. Write a program to evaluate the correctness of parenthesis matching problem using stacks. Given a string of parenthesis, program should output “True” or “False” depending on whether the parenthesis are matched or not.

Example:

Input file contents:

({}[]{}()[]))]

Output of the program should look like:

Incorrect





Write a separate program for each question., total 4 programs (one program for linked list, one for stack, one for queue and one for evaluator) are to be submitted to the same directory under “handin”. The output should be displayed for each operation except for problem #3.





*Provide a README file with specific instructions for compilation and execution for the grader to follow, and any notes you want to add such as how you handle “overflow”, etc.