Description
Question 1:
Implement an interpreter-like postfix calculator. Your program should repeatedly:
-
Print a prompt to the user. The prompt should be: ‘–>’
-
Read an expression from the user
-
Evaluate that expression
-
Print the result
Your calculator should support 2 kinds of expressions:
-
Arithmetic expressions – are given in postfix notation. The tokens of the expression are separated by a space.
-
Assignment expressions – are expression of the form:
variable_name = arithmetic_expression
When evaluated, it first evaluates the arithmetic_expression (given in postfix notation), and then it associates that value with variable_name (in a data structure of your choice).
-
The value of an assignment expression, is the name of the variable being assigned.
-
Assume that the variable_name, the ‘=’ symbol, and the arithmetic_expression are separated by a space.
Notes:
-
Arithmetic expressions can contain variable names, for referencing to values associated with variables that were defined before.
-
You may assume that the input the user enters, is valid. That is, the arithmetic expressions are legal; all variables used in an expression were already defined; etc.
-
The program should keep reading, and evaluating expressions until the user types ‘done( )’.
Your program should interact with the user exactly as demonstrated in the example below:
–> 4
4
–>51-
4
–> x = 5 1 –
x
–> x
4
–> x x +
8
–> y = 1 x + 3 4 * – 2 /
y
–> y
-3.5
–> done()
Question 2:
Give a Python implementation for the MaxStack ADT. The MaxStack ADT supports the following operations:
-
MaxStack(): initializes an empty MaxStack object
-
maxS.is_empty(): returns True if maxS does not contain any elements, or False otherwise.
-
len(maxS): Returns the number of elements in maxS
-
maxS.push(e): adds element e to the top of maxS.
-
maxS.top(): returns a reference to the top element of maxS, without removing it; an exception is raised if maxS is empty.
-
maxS.pop(): removes and return the top element from maxS; an exception is raised if maxS is empty.
-
maxS.max(): returns the element in maxS with the largest value, without removing it; an exception is raised if maxS is empty.
Note: Assume that the user inserts only integers to this stack (so they could be compared to one another, and a maximum data is well defined).
For example, your implementation should follow the behavior below:
-
maxS = MaxStack()
-
maxS.push(3)
-
maxS.push(1)
-
maxS.push(6)
-
maxS.push(4)
-
maxS.max()
6
-
maxS.pop()
4
-
maxS.pop()
6
-
maxS.max()
3
Implementation Requirements:
-
For the representation of MaxStack objects, your data members should be:
-
-
A Stack – of type ArrayStack
-
-
-
Additional (1) space – for additional data members, if needed
-
-
Your implementation should support the max operation in (1) worst-case time. For all other Stack operation, the running time should remain as it was in the original implementation.
Hint: You may want to store a tuple, as elements of the ArrayStack. That is, to attach to every “real” data in this stack some additional information.
Give a Python implementation for the MidStack ADT. The MidStack ADT supports the following operations:
-
MidStack(): initializes an empty MidStack object
-
midS.is_empty(): returns True if S does not contain any elements, or False otherwise.
-
len(midS): Returns the number of elements midS
-
midS.push(e): adds element e to the top of midS.
-
midS.top(): returns a reference to the top element of midS, without removing it; an exception is raised if S is empty.
-
midS.pop(): removes and returns the top element from midS; an exception is raised if midS is empty.
-
midS.mid_push(e): adds element e in the middle of midS.
That is, assuming there are n elements in S: In the case n is even, e would go exactly in the middle. If n is odd, e will go after the %&’(th element.
For example, your implementation should follow the behavior as demonstrated in
-
the two execution examples below:
>>> midS = MidStack()
>>> midS = MidStack()
>>> midS.push(2)
>>> midS.push(2)
>>> midS.push(4)
>>> midS.push(4)
>>> midS.push(6)
>>> midS.push(6)
>>> midS.push(8)
>>> midS.push(8)
>>> midS.mid_push(10)
>>> midS.push(10)
>>> midS.pop()
>>> midS.mid_push(12)
8
>>> midS.pop()
>>> midS.pop()
10
6
>>> midS.pop()
>>> midS.pop()
8
10
>>> midS.pop()
>>> midS.pop()
12
4
>>> midS.pop()
>>> midS.pop()
6
2
>>> midS.pop()
4
>>> midS.pop()
2
-
For the representation of MidStack objects, your data members should be:
-
-
A Stack – of type ArrayStack
-
-
-
A double ended queue – of type ArrayDeque
-
-
-
Additional (1) space – for additional data members, if needed
-
-
Your implementation should support the mid_push operation in (1) amortized time. For all other Stack operation, the running time should remain as it was in the original implementation (That is, 1 amortized for push and pop, and (1) worst-case for top, len and is_empty).
Question 4:
Give an alternative implementation for the Queue ADT.
Implementation Requirements:
-
For the representation of Queue objects, your data members should be:
-
-
Two Stacks – of type ArrayStack
-
-
-
Additional (1) space – for additional data members, if needed
-
-
Any sequence of n enqueue and dequeue operations (starting with an empty queue) should run in worst-case of ( ) altogether.
Question 5:
Implement the following function:
def permutations(lst)
The function is given a list lst of integers, and returns a list containing all the different permutations of the elements in lst. Each such permutation should be represented as a list.
For example, if lst=[1, 2, 3], the call permutations(lst) could return
[[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 2, 1], [3, 1, 2], [2, 3, 1]]
Implementation Requirements:
-
Your implementation should be non-recursive.
-
Your implementation is allowed to use a Stack, a Queue, and (1) additional space.
Hint: Use the stack to store the elements yet to be used to generate the permutations, and use the queue to store the (partial) collection of permutations generated so far.