In this assignment, you will create a calculator for postfix expressions. The ideas required for this question are covered in lectures talking discussing slide sets 8 and 9, and during lab.
Again, to emphasize, the code for all parts of this assignment should be contained in a single .py or .ipynb file.
Note that the data structures you create should be able to support float and character data types.
Write a program to initialize a doubly linked list (in this question, the instance of a DLL will be referred to as dll), and perform the following functions on them:
1. createDLL(): Should create an instance of a doubly linked list, dll. Func- tion does not need to return anything.
2. isEmpty(dll): Takes as input an instance of a doubly linked list, dll, and checks if it is empty. Should return 1 if dll is not empty, and 1 if dll is empty.
3. addFront(dll, val): Takes as input an instance of a doubly linked list, dll, and a value, val, and adds it to the head of the list. Function does not need to return anything.
4. removeFront(dll): Takes as input an instance of a doubly linked list, dll, and removes the head of the list. Function does not need to return anything.
How to test your code: Make sure you print out the DLL whenever you perform addFront or removeFront functions.
Use the above doubly linked list code to create a stack. For the purposes of this problem, the instance of a stack will be referred to as stack. Your stack implementation should support the following functions:
1. createStack(): Use the createDLL() function from the previous part to initialize an empty stack.
2. push(stack, val): Use the addFront() function from the previous part to implement the stack push function.
3. pop(stack, val): Use the removeFront() function from the previous part to implement the stack pop function.
How to test your code: Make sure to print out the stack after push and pop functions.
Use the stack implemented in the previous part and use it to create a postfix expression calculator. The calculator should take as input an expression, exp, from the user, and check if exp is a valid postfix expression. If exp is a valid postfix expression, then compute it and print out the value that exp evaluates to. If exp is an invalid postfix expression, print out "User input is not a valid postfix expression".
You are not required to support brackets/parenthesis. However, if you do support bracket- s/parenthesis, then that should also be taken into account while checking the validity of the expression.
In the last assignment, you implemented binary search, which is a O(logn) algorithm. In this problem, we will see how to do it in a singly linked list.
What is the biggest drawback in a linked list (SLL or DLL) that makes O(logn) search impossible on it?
Consider a doubly linked list. We know that every node in a DLL contains a pointer to the next and previous nodes respectively. Now suppose every node has a next pointer to every other node that appears on the list after it, and a previous pointer to every other node that appears on the list prior to it. Suppose this list has n such nodes.
1. What is the overall overhead in terms of pointer storage per node and on the list as a whole?
2. What is the average asymptotic cost for inserting a node at an arbitrary location in this list?
3. Describe how you might perform binary search on this modified list.
Implement this modified version of doubly linked list. It should support the same operations the previous problem on the assignment supported, as well as binary search. Of course, it is beneficial to store pre-sorted values in this list.