- Problem 3 Reordering List Of Letters 25 Points A Write The Function Get Lowercase L That Takes As Input A List 1 (86.9 KiB) Viewed 77 times
Problem 4 – LinkedList of Letters (40 points) Note: this problem
is related to the previous problem, but it is independent, i.e.,
you can solve all the parts in this problem even if your
implementations in Problem 3 did not work correctly.
a) Create a class LinkedListWithTail which is an updated version
of the LinkedList class that we covered in the course (the file is
attached, where you will find the LinkedList implementation
including the __init__, print_list, and add_at_head methods). In
the LinkedListWithTail class, you are asked to add a tail attribute
to the linked list which refers to the last node in the list (so
head is the first node and tail is the last node). Update the class
and all the methods as necessary to initialize and update the tail
reference whenever needed. Also add a method
add_at_tail(self,other) to this class which takes a
LinkedListWithTail 𝑜𝑡ℎ𝑒𝑟 as input and adds this List at the end
(i.e., at the tail) of the self object. Note 1: you are not
required to include the remove methods Note 2: be careful that
unlike add_at_head which adds a single node at the head,
add_at_tail adds an entire list at tail.
b) Define a function ListToLinkedListWithTail(L) which takes a
list 𝐿 and returns a LinkedListWithTail which contains the same
data elements in 𝐿 in the same order (i.e., the data in L[0] is
equal to the data in the head of the returned
LinkedListWithTail).
c) Use this method along with the methods you implemented in
problem 3 to get two LinkedListWithTail objects: one containing the
lower-case letters in a List of letters and another containing the
upper-case letters, as in the code below. Note: if your solutions
in Problem 3 don’t work, you can hard-code the values of lower and
upper (i.e., set them equal to what the methods getLowerCase and
getUpperCase are supposed to return).
d) Use the add_at_tail method that you implemented in part (b)
to update the lower_LL list by adding the upper_LL at its tail. So
lower_LL will now include the lower-case elements followed by the
upper-case elements. Create an alias to the updated lower_LL; call
it merged_LL (because lower_LL is not a meaningful name anymore).
Verify the correctness of your implementation using the code below,
where it is expected that the two print_list calls print the same
set of elements in the same order. Note: similarly, if your
reOrderInPlace function from Problem 3 doesn’t work, you can
hard-code the re-ordered list L.
Problem 3 - Reordering List of Letters (25 points) a) Write the function get Lowercase (L) that takes, as input, a list of letters and returns another list that contains only the upper-case letters in L in the same order as they appear in L. The function should not modify the list L. Write another function getUppercase (L) which similarly retums a list with the upper-case letters without modifying L and while maintaining their order. Note 1: Each letter is represented as a string of length 1 Note 2: You are not allowed to use the built-in isupper and islower string methods b) Write a function reOrder (L) that takes a list of letters and reorders this list such that all lower-case letters are placed in the beginning of the list. Use the functions get lowercase (L) and get uppercase (L) of the previous part inside your function. Note that this function modifies the list itself, and keeps the relevant order of the letters (Le, the lower-case letters moved to the beginning should keep their order with respect to each other) c) Repeat part (b), but now you need to reorder the list in-place; this means that you are not allowed to use the functions you implemented in part (a) nor use any auxiliary list (L.e., cannot use a copy of L nor other lists). Call this function reOrderinplace(L). Sample Tests: L1 - I'v','A', 'A','','','c','d'] louer getowerCase(11) upper - BetUpperCase(L1) print('Lower in L., lower) print('upper in 1 -, upper) reOrder(1) print('ll after reordering, L1) 201 L3 I'A','') 15.1 . reOrder Inplace(L2) reOrderInplace(3) reorder Inplace(14) reOrder relace(LS) print('L2 after re-ordering in place = L2) print('13 after re-ordering in place -13) print('L4 after re-ordering in place 14) print('s after re-ordering in place=L5) Output: - Lower in Li - (Tv', 'b', 'c','d'] Upper in L1 = ('A', 'A', 'B'] L1 after reOrderine = ['V', 'b', 'c','d', 'A', 'A', 'B'] L2 after re-ordering in place - Il L3 after re-ordering in place - ('A', 'B'] L4 after re-ordering in place = ('a', 'b', 'c','d'] 15 after re-orderine in place = ['a', 'b', 'k','1','1', 'A', 'M', 'Z', 'L', 'F']
Problem 4 - LinkedList of Letters (40 points) Note: this problem is related to the previous problem, but it is independent, i.e., you can solve all the parts in this problem even if your implementations in Problem 3 did not work correctly. a) Create a class LinkedlistWithTail which is an updated version of the LinkedList class that we covered in the course (the file is attached, where you will find the LinkedList implementation including the _init_ print_list, and add_at_head methods). In the LinkedListWithTail class, you are asked to add a tail attribute to the linked list which refers to the last node in the list (so head is the first node and tail is the last node). Update the class and all the methods as necessary to initialize and update the tail reference whenever needed. Also add a method add_at_tail (self, other) to this class which takes a LinkedListWithTail other as input and adds this List at the end (i.e., at the tail) of the self object. Note 1: you are not required to include the remove methods Note 2: be careful that unlike add_at_head which adds a single node at the head, add_at_tail adds an entire list at tail. b) Define a function ListToLinkedlistWithtail (L) which takes a list L and returns a LinkedListWithTail which contains the same data elements in L in the same order (i.e., the data in L[O] is equal to the data in the head of the returned LinkedListWithTail). c) Use this method along with the methods you implemented in problem 3 to get two LinkedListWithTail objects: one containing the lower-case letters in a List of letters and another containing the upper-case letters, as in the code below. Note: if your solutions in Problem 3 don't work, you can hard-code the values of lower and upper (i.e., set them equal to what the methods get LowerCase and get UpperCase are supposed to return). = lower getLowerCase(L) # L is any List of letters upper getUpperCase(L) lower_LL = ListToLinkedlistWithTail(lower) unnan TI kadi+ TA
LUWET LITTLE 6CCLOWCT CUST upper = getUpperCase(L) lower_LL = ListToLinkedListWithTail(lower) upper_LL = ListToLinkedListWithTail(upper) d) Use the add_at_tail method that you implemented in part (b) to update the lower_LL list by adding the upper_LL at its tail. So lower_LL will now include the lower-case elements followed by the upper-case elements. Create an alias to the updated lower_LL; call it merged_LL (because lower_LL is not a meaningful name anymore). Verify the correctness of your implementation using the code below, where it is expected that the two print_list calls print the same set of elements in the same order. Note: similarly, if your reOrderInPlace function from Problem 3 doesn't work, you can hard-code the re-ordered list L. reOrderInplace(L) # L is any List of Letters LL = ListToLinkedListWithTail(L) LL.print_list() merged_LC.print_list() print(LL.length) print(merged_LL.length)
class Node: def __init_(self, data=None, next_node=None): self.data data self.next next_node def _str_(self): return str(self.data) class LinkedList: def __init__(self): self.length 0 self.head None def print_list(self): node = self.head while node is not None: print(node, end='') node = node.next print(") def add_at_head (self, node): node.next| = self.head self.head = node self.length+=1