Description
Homework # 5
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:
1 . Arithmetic expressions – are given in postfix notation. The tokens of the expression are separated by a space.
2 . 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).
Notes:
- The value of an assignment expression, is the name of the variable being
- Assume that the variable_name, the ‘=’ symbol, and the arithmetic_expression are separated by a space.
Notes:
1 . Arithmetic expressions can contain variable names, for referencing to values associated with variables that were defined before.
2 . 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.
3 . 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 –> x –> 4 –> 8 –> y –> |
4
5 1 x x x y = y |
–
5 + |
1 x |
–
+ 3 |
4 | * | – 2 | / |
Question 2:
Give a Python implementation for the MaxStack ADT. The MaxStack ADT supports the following operations:
- MaxStack (): initializes an empty MaxStack object
- 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:
1 . 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
2 . 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.
Question 3:
Give a Python implementation for the MidStack ADT. The MidStack ADT supports the following operations:
- MidStack (): initializes an empty MidStack object
- is_empty() : returns True if S does not contain any elements, or False otherwise.
- len(midS): Returns the number of elements m i d S
- push(e) : adds element e to the top of m i d S .
- top(): returns a reference to the top element of midS, without removing it; an exception is raised if S is empty.
- pop() : removes and returns the top element from m i d S ; an exception is raised if midS is empty.
- mid_push (e): adds element e in the middle of m i d S .
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 ~~1
~th element.
For example, your implementation should follow the behavior as demonstrated in the two execution examples below:
> > > midS = MidStack()
>>> midS.push(2) >>> midS.push(4) >>> midS.push(6) >>> midS.push(8) >>> midS.mid_push(10)
>>> midS.pop() 8
>>> midS.pop() 6
>>> midS.pop() 10
>>> midS.pop() 4
>>> midS.pop() 2
Implementation Requirements:
1 . 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
2 . 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:
1 . 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
2 . 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: de f 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:
1 . Your implementation should be non-recursive.
2 . 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 s o far.
