Implement a sorted linked list of strings. That means, every time you are asked to insert a new string, you should insert it in a position such that the list of strings remain lexicographically sorted. Refer to appendix A for input and output formats.
PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul Recall the Course Rule that copying or plagiarism in any form will result in an F. You are free to discuss with anyone, consult any textbook or web-resource, but you are expected to write your own program/solution from scratch. Instructions • Accept this assignment on GitHub Classroom • Edit the .c files provided in the GitHub Repository. Don’t change the filenames. • Link to the LaTeX homework template on Overleaf. • 5% will be deducted from your total score for not adhering to the naming conventions • 50% of the score for each coding problem is for indentation and comments. • Submitting after the deadline deducts 1% from your total score per hour. If you submit 24 hours late, 24% will be deducted from your score. • If you are planning to use your slack time, you have to (re)submit your PDF on Google Classroom when you hand in your final submission. This is important to ensure you do not get a zero on your pset because without a Google Classroom notification, we will only consider your work up to the deadline and none of your work in your slack time can be considered. • We are declaring the 12 hours prior to pset deadlines as the delayed response period. Unless it is regarding an emergency, all emails to course staff will be responded to 4 hours after the email is sent. Make sure you start working on your solutions sufficiently early to avoid last minute hiccups. • All questions in this pset will follow the same output and input format which has been added in Appendix A. • For this pset, you can hand in your Google Classroom assignment without any PDFs. However, rule 7 still applies ref. slack time. Questions 1. Implement a sorted linked list of strings. That means, every time you are asked to insert a new string, you should insert it in a position such that the list of strings remain lexicographically sorted. Refer to appendix A for input and output formats. [25] 1 https://classroom.github.com/a/KmYUUjIH https://www.overleaf.com/read/fdzkjnxpknnf PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul 2. Implement a stack of strings using linked list with all the stack-related operations discussed in class: push, pop, peek, isFull, isEmpty, display. Refer to appendix B for input and output formats. [6 + 6 + 4 + 2 + 4 + 3 = 25] 3. Implement a queue of strings using a circular array with all the queue-related opera- tions discussed in class: enqueue, dequeue, peekFront, peekRear, isFull, isEmpty, display. Refer to appendix C for input and output formats. [5 + 6 + 2 + 2 + 3 + 3 + 4 = 25] 4. Implement a program to convert a postfix expression into an infix expression. Take a sample input and manually trace its step-by-step execution in your answer. You can Refer to appendix D for input and output formats. [10 + 15 = 25] 2 PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul Appendix A: Question-1 Input/Output Format Input: Line 1: An integer N , the number of operations to be performed 1 6 Output: The command list: these are provided to you in the source files. Note that this menu is printed on the console only once, but the Enter choice> prompt should print each time (just like PSET3). Follow the order of the commands in the comments of the .c files included in the repository. 1 1) Insert 2 2) Display 3 Enter choice > Input: Lines: 1 . . . N will have N (here, 6) operations (denoted by the integer in the menu shown above) with their respective inputs (for insert/display operations). Please note, the Display operations print their outputs immediately after they are executed. We have denoted input in BLACK and output in RED. 1 1 2 apple 3 1 4 orange 5 2 6 apple -> orange 7 1 8 banana 9 1 10 melon 11 2 12 apple -> banana -> melon -> orange 3 PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul Appendix B: Question-2 Input/Output Format Input: Line 1: An integer N , the number of operations to be performed 1 13 Output: The command list: these are provided to you in the source files. Note that this menu is printed on the console only once, but the Enter choice> prompt should print each time (just like PSET3). Follow the order of the commands in the comments of the .c files included in the repository. 1 1) Push 2 2) Pop 3 3) Peek 4 4) isFull 5 5) isEmpty 6 6) Display 7 Enter choice > Input: Lines: 1 . . . N will have N (here, 13) operations (denoted by the integer in the menu shown above) with their respective inputs (for insert/display operations). Please note, the Pop, Peek, isFull, isEmpty, and Display operations print their outputs immediately after they are executed. isFull and isEmpty display 0 if it’s False, and 1 if it’s True. Peek and Display display -1 if the Stack is empty, and Pop returns -1 if the Stack is empty (refer to March 23 Classroom Post for details). We have denoted input in BLACK and output in RED. 1 5 2 1 3 1 4 apple 5 1 6 orange 7 6 8 orange 9 apple 10 2 11 orange 12 3 13 apple 14 2 15 apple 16 3 17 -1 4 PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul 18 1 19 sparrow 20 1 21 pigeon 22 4 23 0 24 1 25 crow 26 3 27 crow 28 6 29 crow 30 pigeon 31 sparrow 5 PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul Appendix C: Question-3 Input/Output Format Input: Line 1: The size of the Queue Line 2: An integer N , the number of operations to be performed 1 4 2 16 Output: The command list: these are provided to you in the source files. Note that this menu is printed on the console only once, but the Enter choice> prompt should print each time (just like PSET3). Follow the order of the commands in the comments of the .c files included in the repository. 1 1) Enqueue 2 2) Dequeue 3 3) peekFront 4 4) peekRear 5 5) isFull 6 6) isEmpty 7 7) Display 8 Enter choice > Input: Lines: 1 . . . N will have N (here, 16) operations (denoted by the integer in the menu shown above) with their respective inputs (for insert/display operations). Please note, the peekFront, peekRear, isFull, isEmpty, and Display operations print their outputs immediately after they are executed. isFull and isEmpty display 0 if it’s False, and 1 if it’s True. peekFront, peekRear, and Display display -1 if the Queue is empty, and Dequeue returns -1 if the Queue is empty, and Enqueue returns -1 if the Queue is full (refer to March 23 Classroom Post for details). We have denoted input in BLACK and output in RED. 1 6 2 1 3 1 4 apple 5 1 6 orange 7 1 8 banana 9 7 10 apple -> orange -> banana 11 3 12 apple 13 4 6 PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul 14 banana 15 2 16 1 17 melon 18 3 19 orange 20 1 21 pigeon 22 5 23 1 24 2 25 5 26 0 27 1 28 parrot 29 7 30 banana -> melon -> pigeon -> parrot 7 PSET 4 Ashoka University CS/PHY-1101-2: Introduction to Computer Programming Deadline: 23:59 IST, 16 April, 2021 by Goutam Paul Appendix D: Question-4 Input/Output Format Input: Line 1: A Postfix expression, consisting of letters (A-Z) or numbers (0-9). Assume that each operand is one character or one digit only, and the valid operators are +, -, *, / 1 ab+cd-*ef-/ Output: Display each line of the operation, highlighting the Stack connections between each item on the stack. 1 a 2 a -> b 3 (a + b) -> c 4 (a + b) -> c -> d 5 (a + b) -> (c - d) 6 ((a + b) * (c - d)) 7 ((a + b) * (c - d)) -> e 8 ((a + b) * (c - d)) -> e -> f 9 ((a + b) * (c - d)) -> (e - f) 10 (((a + b) * (c - d)) / (e - f)) 8