[Solved] CS1134-Homework 5-Implement an interpreter-like postfix calculator

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>

45 1x =xx xy =y

5+1

1x

+ 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.