In practice 06, you will create a single Python file main.py. This file will contain solutions to 6 tasks. Task01 is to complete the methods in following classes:

* Stack
* Queue

Those two classes will be used in following tasks. For each of following tasks (from task02 to task06), you will create function, which solves a particular problem:

• task02(ds_class, commands)
• task03(formula)
• task04(formula)
• task05(maze, start, goal)
• task06(text)

Both filename and names of the functions have to be exactly the same as described.

When submitting your solution:

1. Zip the file main.py into .zip archive with arbitrary name.
2. Upload the .zip file to the BRUTE evaluation system.

You can obtain maximum of 2 points.

In starter code which is provided bellow each function contains docstring with short desription. Docstrings also contain examples of usage. Those examples can be used for testing your functions using doctest module. To run those tests you can simply run the main module as main script.

import copy
import string
 
# task01: finish implementation of Stack and Queue
class Stack:
	def __init__(self):
		pass
 
	def push(self, item):
		"""adds item to stack"""
		pass
 
	def pop(self):
		"""returns item from top of the stack and removes it from the stack
		returns None in case that queue is empty"""
		pass
 
	def peek(self):
		"""return item from top of the stack without removing it
		returns None in case that queue is empty"""
		pass
 
	def is_empty(self):
		"""returns True if there are no items in the stack, False otherwise"""
		pass
 
 
class Queue:
	def __init__(self):
		pass
 
	def enqueue(self, item):
		"""adds new item to the back of the queue"""
		pass
 
	def dequeue(self):
		"""returns item from the front of the queue and removes it from the queue
		returns None in case that queue is empty"""
		pass
 
	def peek(self):
		"""returns item from the front of the queue without removing it
		returns None in case that queue is empty"""
		pass
 
	def is_empty(self):
		"""returns True if there are no items in the queue, False otherwise"""
		pass
 
def task02(ds_class, commands):
	"""Executes a sequence of commands on an instance of a given data structure class (Queue or Stack).
 
	:param ds_class: (string) name of data structure to be tested ('Queue' or 'Stack')
	:param commands: list of commands (strings). Commands such as 'push X' and 'enqueue X' contain also value X
					X is integer number in string format (e.g. 'push 10', see examples bellow).
	:return: list of results corresponding to the output of each command
 
	Examples:
 
	>>> task02("Stack", ["push 6", "push 2", "push 3", "peek", "is_empty", "pop",
	... "pop", "push 7", "pop", "pop", "pop", "is_empty"])
	[3, False, 3, 2, 7, 6, None, True]
 
	>>> task02("Queue", ["enqueue 6", "enqueue 2", "peek", "dequeue", "enqueue 0",
	... "is_empty", "dequeue", "dequeue", "dequeue", "is_empty"])
	[6, 6, False, 2, 0, None, True]
	"""
	pass
 
 
def task03(formula):
	"""Checks if parenhesis in formula are ballanced
 
	Supported types are:
	- curly brackets: {}
	- round parenthesis: ()
	- square brackets: []
 
	:param formula: string to check
	:return: True if parenthesis are balanced, False otherwise
 
	Examples:
 
	>>> task03("Q.append(self.node(j[0],check,j[1]))")
	True
	>>> task03 ("([{}]){}({({([()])})})")
	True
	>>> task03 ("([{}]){}({({([()]))}})")
	False
	"""
	pass
 
 
def task04(formula):
	""" Evaluates equation in postfix notation
 
	Postfix notation (or reverse polish notation) is mathematical notation
	where operator such as +, - etc.
	always come after operands (numbers)
	Supported operators: +, - , *, /, //, **, %
 
	:param formula: (string) equation to evaluate. Operators and operands are separated by space.
	:return: (float) value rounded to 1 decimal place to which equation evaluates or None in case that
	the formula is not in correct postfix notation
 
	Examples:
	>>> task04("-3 2 + 3 +")
	2.0
 
	>>> task04("3 5 + 2 * 0.5 **")
	4.0
 
	>>> task04("1 3 6 + 2 * + 9 -")
	10.0
 
	"""
	pass
 
 
def task05(maze, start, goal):
	"""returns True if path in maze from start to goal exists, False otherwise
 
	Maze is 2D array containing only 0 or 1 values.
	0 value represents free space
	1 value represents wall
 
	In each step, there are only 4 movements allowed: up, down, left, right
	Diagonal movements are not allowed.
 
	Valid path contains zeros only. It is not possible to step on wall nor to cross the wall.
 
	Start poisition is invalid in case that there is wall on start position coordinates.
	In this case function returns False immediately.
 
	:param maze: 2D array (matrix) representing the maze; contains only integers 0 or 1
	:param start: tuple (r, c) with coordinates of start point
	:param goal: tuple (r, c) with coordinates of goal point
	:return: True if path from start to goal exists, False oterwise
 
 
	Examples:
	>>> map = [
	... [0, 1, 0, 1, 0, 0, 0, 0, 0],
 	... [0, 1, 0, 1, 0, 1, 0, 0, 0],
 	... [0, 1, 0, 1, 0, 0, 1, 0, 0],
	... [0, 1, 1, 1, 1, 0, 0, 1, 0],
	... [0, 1, 0, 0, 1, 0, 0, 1, 0],
	... [0, 1, 0, 0, 1, 0, 1, 0, 0],
	... [0, 0, 0, 0, 0, 0, 1, 0, 0]
	... ]
	>>> task05(map, (0,0), (6,8))
	True
	>>> task05(map, (0, 2), (6, 8)) # path does not exist
	False
	>>> task05(map, (0, 3), (6, 8)) # invalid start position
	False
	"""
	pass
 
 
def task06(text):
	"""Finds shortest substring in text which contains all letters from (english) alphabet (in whatever order)
 
	If there are multiple such substrings with the same length, return just the first one.
 
	:param text: (string)
	:return: (string) the shortest substring found or None if there is no such substring
 
 
	Examples:
	>>> task06("hiakjsabsa"+string.ascii_lowercase)
	'abcdefghijklmnopqrstuvwxyz'
	>>> task06(string.ascii_lowercase+"ziakjsabsa")
	'abcdefghijklmnopqrstuvwxyz'
	>>> print(task06("sa"))
	None
	"""
	pass