1. Write a program that takes in RPN instructions, so to add 3 and 4, you would use 3 4 +. You should also allow variables so you can do x = 3 4 + then x x * which would return 49.
2. Create a MaxStack that supports the regular stack operations plus the max and len. All operations should be O(1).
3. Create a MidStack that supports the regular stack operations plus the ability to insert into the middle of the stack. The mid_push should push an element directly in the middle of the stack.
4. Create an alternate implementation of the Queue ADT.
5. Create a function permutations that returns a list of all the possible permutations. You should use the stack and queues, and the code should be non recursive. Given permutations([1,2,3]) it should return [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],[3,2,1]] (although the order does not need to be the same as shown).

For all your Python programming homework, contact us for a quote.

Solution:

YourNetID_hw5_q1.py

“””
Question 1: Implement an interpreter-like postfix calculator
– Print a prompt to the user. The prompt should be: ‘–>’
– Read an expression from the user
– Evaluate that expression
– Print the result
“””
from ArrayStack import ArrayStack

# Global variable
# Keep value os variable name
variable_dictionary = {}

def postfix_evaluate(str_exp):
“””
Evaluate the string expression
“””
operator_list = “+-*/”
# Stack contain the expressin
stack_exp = ArrayStack()
token_exp = str_exp.split()

for token in token_exp:
if token in operator_list:
#expect token is operator
op1 = stack_exp.pop()
op2 = stack_exp.pop()
if token == ‘+’:
result = op2 + op1
elif token == ‘-‘:
result = op2 – op1
elif token == ‘*’:
result = op2 * op1
elif token == ‘/’:
if op1 == 0:
raise ZeroDivisionError
else:
result = op2 / op1
stack_exp.push(result)
else:
# expect token is number
try:
# If token is number
stack_exp.push(int(token))
except:
# If token is variable name
stack_exp.push(variable_dictionary[token])

return stack_exp.pop()

def main_process():
promt_response = input(“–> “)
while promt_response != “done()”:
# Check this is assignment experssions
input_word = str(promt_response).split()
if len(input_word) > 2 and input_word[0][0].isalpha() and input_word[1] == ‘=’:
#variable_name = arithmetic_expression
variable_name = promt_response.split()[0]
arithmetic_expression = promt_response.split(“= “)[1]
variable_value = postfix_evaluate(arithmetic_expression)
# Put to global map variable dictionary
variable_dictionary[variable_name] = variable_value
# print the variable value
print(variable_name)
else:
# This is arithmetic experssions
print(postfix_evaluate(str(promt_response)))
# Ask for next loop
promt_response = input(“–> “)

if __name__ == “__main__”:
main_process()

YourNetID_hw5_q2.py

“””
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
“””

from ArrayStack import ArrayStack

class MaxStack:
def __init__(self):
“””
Constructor
“””
self.data = ArrayStack()
self.max_value = None

def __len__(self):
“””
len(MaxStack)
“””
return len(self.data)

def is_empty(self):
“””
maxS.is_empty(): returns True if maxS does not contain any elements, or False otherwise.
“””
return (len(self.data) == 0)

def push(self, e):
“””
maxS.push(e): adds element e to the top of maxS.
“””
if self.is_empty():
# add first variable
self.max_value = e
self.data.push(tuple((e,e)))
else:
# the stack have been have value. Need to check the new value with current max
if e > self.max_value:
# update the max value
self.max_value = e
self.data.push(tuple((e, self.max_value)))

def top(self):
“””
maxS.top(): returns a reference to the top element of maxS, without removing it; an exception is raised if maxS is empty.
“””
if self.is_empty():
raise Exception(“Stack is empty”)
return self.data.top()[0]

def pop(self):
“””
maxS.pop(): removes and return the top element from maxS; an exception is raised if maxS is empty.
“””
if self.is_empty():
raise Exception(“Stack is empty”)
result = self.top()
# Remove in real database
self.data.pop()
# Update new max value if we pop the max
self.max_value = self.data.top()[1]
return result

def max(self):
“””
maxS.max(): returns the element in maxS with the largest value, without removing it; an exception is raised if maxS is empty
“””
if self.is_empty():
raise Exception(“Stack is empty”)
return self.max_value

YourNetID_hw5_q3.py

“””
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.
“””

from ArrayDeque import ArrayDeque
from ArrayStack import ArrayStack

class MidStack:
def __init__(self):
“””
Default constructor MidStack
“””
self._top = ArrayDeque()
self._bottom = ArrayStack()

def is_empty(self):
“””
midS.is_empty(): returns True if S does not contain any elements, or False otherwise.
“””
return (len(self) == 0)

def __len__(self):
“””
len(midS): Returns the number of elements midS
“””
return len(self._top) + len(self._bottom)

def push(self, e):
“””
midS.push(e): adds element e to the top of midS.
“””
if 1 == (len(self) % 2):
last_element = self._top.last()
self._bottom.push(last_element)
self._top.dequeue_last()
self._top.enqueue_first(e)

def top(self):
“””
midS.top(): returns a reference to the top element of midS, without removing it; an exception is raised if S is empty.
“””
if self.is_empty():
raise Exception(“Stack is empty”)
return self._top.first()

def pop(self):
“””
midS.pop(): removes and returns the top element from midS; an exception is raised if midS is empty.
“””
if self.is_empty():
raise Exception(“Stack is empty”)
if 0 == (len(self) % 2):
top_element = self._bottom.pop()
self._top.enqueue_last(top_element)
return self._top.dequeue_first()

def mid_push(self, e):
“””
midS.mid_push(e): adds element e in the middle of midS.
“””
if 0 == (len(self) % 2):
self._top.enqueue_last(e)
else:
self._bottom.push(e)

if __name__ == “__main__”:
midS1 = MidStack()
midS1.push(2)
midS1.push(4)
midS1.push(6)
midS1.push(8)
midS1.mid_push(10)
print(midS1.pop())
print(midS1.pop())
print(midS1.pop())
print(midS1.pop())
print(midS1.pop())
print (“=======================”)

midS = MidStack()
midS.push(2)
midS.push(4)
midS.push(6)
midS.push(8)
midS.push(10)
midS.mid_push(12)
print(midS.pop())
print(midS.pop())
print(midS.pop())
print(midS.pop())
print(midS.pop())
print(midS.pop())

YourNetID_hw5_q4.py

“””
Question 4:
Give an alternative implementation for the Queue ADT.
“””

from ArrayStack import ArrayStack

class Queue:
def __init__(self):
self._data = ArrayStack()
self._data_helper = ArrayStack()
self._first = None

def __len__(self):
“””
len(Queue) function
“””
return len(self._data)

def is_empty(self):
return len(self) == 0

def enqueue(self, e):
“””
Enqueue to the queue. push to the main data
“””
if (self.is_empty()):
self._first = e
self._data.push(e)

def dequeue(self):
“””
Enqueue function
“””
# Reverse the stack
for e in range(len(self._data)):
self._data_helper.push(self._data.pop())

result = self._data_helper.top()
self._data_helper.pop()
# update first element
try:
self._first = self._data_helper.top()
except:
self._first = None
# Put to data stack
for e in range(len(self._data_helper)):
self._data.push(self._data_helper.pop())
return result

def first(self):
if(self.is_empty()):
raise Exception(“Queue is empty”)
return self._first

if __name__ == “__main__”:
# Testing
queue = Queue()
queue.enqueue(2)
queue.enqueue(4)
queue.enqueue(6)
queue.enqueue(8)
print(queue.first())
print(queue.dequeue())
print(queue.first())
print(queue.dequeue())
print(queue.first())
print(queue.dequeue())
print(queue.first())
print(queue.dequeue())
YourNetID_hw5_q5.py

“””
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
“””
from ArrayStack import ArrayStack
from ArrayQueue import ArrayQueue

def permutations(lst):
number_remain_stack = ArrayStack()
permutation_queue = ArrayQueue()
result = []
current_permutation_counter = 0
new_permutation_counter = 0

# fill the stack
for e in lst:
number_remain_stack.push(e)

perm = []
perm.append(number_remain_stack.pop())
permutation_queue.enqueue(perm)
current_permutation_counter += 1

for i in range(len(number_remain_stack)):
number = number_remain_stack.pop()

for permu in range(current_permutation_counter):
current_permutation = permutation_queue.dequeue()
for j in range(len(current_permutation) + 1):
new_permutation = list(current_permutation)
new_permutation.insert(j, number)
permutation_queue.enqueue(new_permutation)
new_permutation_counter += 1
current_permutation_counter = new_permutation_counter

while permutation_queue.is_empty() != True:
result.append(permutation_queue.dequeue())
return result

if __name__ == “__main__”:
# Testing
print(permutations([1,2,3]))