# CS1134-Homework 6-Implement an interpreter-like postfix calculator Solved

35.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## Description

5/5 - (1 vote)

Implementation Requirement: All queue operations should run in 𝜃(1) worstcase. Hint: You would want to use a doubly linked list as a data member.

Question 2: Many programming languages represent integers in a fixed number of bytes (a common size for an integer is 4 bytes). This, on one hand, bounds the range of integers that can be represented as an int data (in 4 bytes, only 232 different values coul d be represented), but, on the other hand, it allows fast execution for basic arithmetic expressions (such as +, -, * and /) typically done in hardware.
Python and some other programming languages, do not follow that kind of representation for integers, and allows to represent arbitrary large integers as int variables (as a result the performance of basic arithmetic is slower).
In this question, we will suggest a data structure for positive integer numbers, that can be arbitrary large. We will represent an integer value, as a linked list of its digits. For example, the number 375 will be represented by a 3-length list, with 3, 7 and 5 as its elements.

Note: this is not the representation Python uses. Complete the definition of the following Integer class:
class Integer: def __init__(self, num_str): ”’ Initializes an Integer object representing the value given in the string num_str”’ def __add__(self, other): ”’ Creates and returns an Integer object that represent the sum of self and other, also of type Integer”’ def __repr__(self): ”’ Creates and returns the string representation of self”’ 3 7 5 header trailer

For example, after implementing the Integer class, you should expect the following behavior: >>> n1 = Integer(‘375’) >>> n2 = Integer(‘4029′) >>> n3 = n1 + n2 >>> n3 4404
Note: When adding two Integer objects, implement the “Elementary School” addition technique. DO NOT convert the Integer objects to ints, add these ints by using Python + operator, and then convert the result back to an Integer object. This approach misses the point of this question.

Extra Credit: Support also the multiplication of two Integer objects (by implementing the “Elementary School” multiplication technique): def __mul__(self, other): ”’ Creates and returns an Integer object that represent the multiplication of self and other, also of type Integer”’

Question 3: In this question, we will suggest a data structure for storing strings with a lot of repetitions of successive characters. We will represent such strings as a linked list, where each maximal sequence of the same character in consecutive positions, will be stored as a single tuple containing the character and its count.
For example, the string “aaaaabbbaaac” will be represented as the following list: Complete the definition of the following CompactString class:
class CompactString: def __init__(self, orig_str): ”’ Initializes a CompactString object representing the string given in orig_str”’ def __add__(self, other): ”’ Creates and returns a CompactString object that represent the concatenation of self and other, also of type CompactString”’
def __lt__(self, other): ”’ returns True if”f self is lexicographically less than other, also of type CompactString”’ def __le__(self, other): ”’ returns True if”f self is lexicographically less than or equal to other, also of type CompactString”’ def __gt__(self, other): ”’ returns True if”f self is lexicographically greater than other, also of type CompactString”’
def __ge__(self, other): ”’ returns True if”f self is lexicographically greater than or equal to other, also of type CompactString”’ def __repr__(self): ”’ Creates and returns the string representation (of type str) of self”’
(‘a’, 5) (‘b’, 3) (‘a’, 3) (‘c’, 1)
For example, after implementing the CompactString class, you should expect the following behavior: >>> s1 = CompactString(‘aaaaabbbaaac’) >>> s2 = CompactString(‘aaaaaaacccaaaa’) >>> s3 = s2 + s1 #in s3’s linked list there will be 6 ’real’ nodes >>> s1 < s2 False
Note: Here too, when adding and comparing two CompactString objects, DO NOT convert the CompactString objects to strs, do the operation on strs (by using Python +, <, >, <=, >= operators), and then convert the result back to a CompactString object. This approach misses the point of this question.

>>> e1 = lnk_lst1.first_node() >>> e1_1 = e1.data.first_node() >>> e1_1.data = 10
>>> e2 = lnk_lst2.first_node() >>> e2_1 = e2.data.first_node() >>> print(e2_1.data) 10
b. Now, implement: def deep_copy_linked_list(lnk_lst) The function is given a nested doubly linked lists of integers lnk_lst, and returns a deep copy of lnk_lst. For example, after implementing deep_copy_linked_list, you should expect the following behavior: >>> lnk_lst1 = DoublyLinkedList() >>> elem1 = DoublyLinkedList() >>> elem1.add_last(1) >>> elem1.add_last(2) >>> lnk_lst1.add_last(elem1) >>> elem2 = 3 >>> lnk_lst1.add_last(elem2)