# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="9BfyADmSOdB1"
# # **FreeBirds Crew**
#
# ### We Learn and Grow Together
#
# <img src="https://drive.google.com/uc?export=view&id=1reciCAdssIhi1y9EoBddRTMTTNg_ZRLk" alt ="drawing" width="500"/>

# + [markdown] id="FQz3PMQKOkZ3"
# ### **Stacks**
# A Stack is an Abstract Data Type, Serves as a Collection of elements.
# It has two Principals -
# 1. Push
# 2. Pop
# **Push**,which adds an element to the collection, and **Pop**, which removes the most recently added element. 
#
# Stacks uses the *LIFO(Last in First Out)* Principal that defines as, the order of elements in which they are added in stack the last element is present at the top of the Stack.
#
# ### **Conditions in Stacks**
# Stacks has Bounded Capacity such that If the Stack is Full, not have enough space to add more elements then that condition is called **OverFlow**, Similiarly if the Stack has no Elements Such that No Element Can be Popped Out then the Condition is Called **UnderFlow**.
#
#
# <img src="https://www.tutorialspoint.com/data_structures_algorithms/images/stack_representation.jpg" alt ="drawing" width="500"/>

# + [markdown] id="MVgcUvV3W8mn"
# ## Topics that are Covered in this Session - 
# 1. Stack Implementation using Python
# 2. Stack Implementation using Linked List
# 3. Check if given expression is balanced expression or not
# 4. Find duplicate parenthesis in an expression
# 5. Decode the given sequence to construct minimum number without repeated digits
# 6. Inorder Tree Traversal | Iterative & Recursive
# 7. Preorder Tree Traversal | Iterative & Recursive
# 10. Postorder Tree Traversal | Iterative & Recursive

# + [markdown] id="Wai3fYTFnriZ"
# ### **Stack Implementation in Python**
#
# The main functions that needs to be implemented are - 
#
# 1. empty() – Returns if the stack is empty – Time Complexity : O(1)
# 2. size() – Returns the size of the stack – Time Complexity : O(1)
# 3. top() – Returns a reference to the top element of the stack – Time Complexity : O(1)
# 4. push(g) – Adds the element ‘g’ at the top of the stack – Time Complexity : O(1)
# 5. pop() – Deletes the top element of the stack – Time Complexity : O(1)
#
# <img src="https://cdn.programiz.com/sites/tutorial2program/files/stack.png" alt ="drawing" width="500"/>
#
#
#
#
# We can Implement Stacks in Python by using following Techniques - 
# 1. List
# 2. Collections.deque
# 3. Queue.LifoQueue

# + [markdown] id="Q6W6BfeCo2qK"
# #### **Stacks using List**
# Python has build-in Data Structure called **List**, that has **append()** method so we use that instead of **push() and pop()** method that is used to remove elements from **stack** that is also available in Lists and Works in **LIFO Order**. Time Compelexity of LIST Operations are O(n)
#
# **NOTE** - Unfortunately, List has a some disadvantages as well. The biggest issue is that there comes speed issues if the size of the list grows. The items that are stored in list are placed next to each other in memory if the size grows and more items need to added then python has to do some **Memory Allocations**, due to which the append() operations take more time then ususal.

# + id="LhsCNbNmOezK" outputId="fc5aefa6-26a0-4081-82f5-b4866833416c" colab={"base_uri": "https://localhost:8080/", "height": 233}
print("Making Stack using List")
stack = [] 
print(stack)  
# append() function of list used in place of push() function of Stack that add elements in Stack 
stack.append('Subscribe') 
stack.append('FreeBirds Crew') 
stack.append('Youtube') 
  
print('Adding Elements....') 
print(stack)
  
# pop() fucntion of list is same as pop() function in stack that works in LIFO Order. 
print('\nPopped Elements are: ') 
print(stack.pop()) 
print(stack.pop()) 
print(stack.pop()) 
  
print('\nStack gives Index Error of we Try to Pop from the Empty Stack...') 
print(stack)

# + [markdown] id="WtP3B2RWs4TV"
# #### **Stacks using Collections.deque**
# Let's Implement the Stack using DEQUE Class of Collections Module. DEQUE is better then LIST When we need Quick Append and Pop Opertions from both Ends of the Container. DEQUE has O(1) Time Complexity for append() and pop() as Compared to the LIST which that O(n) Time Complexity.
# Same methods on deque as seen in list are used, append() and pop().

# + id="OEMRzxpLq5uT" outputId="aa0b872e-45d7-4eab-f24c-4232b8a59bcd" colab={"base_uri": "https://localhost:8080/", "height": 233}
from collections import deque 

print("Building Stack using Deque Class of Collections Module....")  
stack = deque() 
print(stack)
  
# append() function of list used in place of push() function of Stack that add elements in Stack 
stack.append('a') 
stack.append('b') 
stack.append('c') 
  
print('Adding Elements....') 
print(stack) 
  
# pop() fucntion of list is same as pop() function in stack that works in LIFO Order.  
print('\nPopped Elements are: ') 
print(stack.pop()) 
print(stack.pop()) 
print(stack.pop()) 
  
print('\nStack gives Index Error of we Try to Pop from the Empty Stack...') 
print(stack) 


# + [markdown] id="CqyIpIm-uYDM"
# #### **Stacks using Queue.LifoQueue**
# QUEUE module has a LIFO Queue, which is a Stack. Data is inserted into Queue using put() function and get() takes data out from the Queue.
# There are various functions present in this module:
# 1. maxsize – Number of items allowed in the queue.
# 2. empty() – Return True if the queue is empty, False otherwise.
# 3. full() – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
# 4. get() – Remove and return an item from the queue. If queue is empty, wait until an item is available.
# 5. get_nowait() – Return an item if one is immediately available, else raise QueueEmpty.
# 6. put(item) – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
# 7. put_nowait(item) – Put an item into the queue without blocking.
# 8. qsize() – Return the number of items in the queue. If no free slot is immediately available, raise QueueFull. [Source](https://www.geeksforgeeks.org)

# + id="PHjNOAIVuKA9" outputId="c2ff15f7-85b3-4000-ce7e-3733e69f32c8" colab={"base_uri": "https://localhost:8080/", "height": 251}
from queue import LifoQueue 

print("Making the Stack using LifoQueue...")
stack = LifoQueue(maxsize = 3) 
print(stack)

# qsize() is the function that shows the size of the stack 
print(stack.qsize()) 
   
# put() function is used to add elements in the Stack
print("Adding Elements in Stack ....")
stack.put('a') 
stack.put('b') 
stack.put('c') 
  
print("Check if it's Full: ", stack.full())  
print("Size of the Stack: ", stack.qsize())  
  
# get() fucntion is used to Pop Elements from the Stack.
print('\nPop Elements from the Stack ....') 
print(stack.get()) 
print(stack.get()) 
print(stack.get()) 
  
print("\nEmpty Stack: ", stack.empty())


# + [markdown] id="0ZoJNrOV8L_g"
# ### **Stack Implementation using Linked List**
#
# Let's Implement Stack using Linked List in Such a Way that A Stack is then a Pointer to the "Head" of the List where Pushing and Popping Operations Happens at the Head of the List, Counter is also Track the Size of the List.
#
# **NOTE** - Advantage of Linked List is that, we can make a Dynamic Change in Size of Stack, and memory is also dynamically allocated so Stack Overflow cannot happen unless memory is exhausted. 
#

# + id="Rxq2UKjj6PTP" outputId="89855cf0-d9c2-403e-e224-06b37df157b2" colab={"base_uri": "https://localhost:8080/", "height": 161}
# Stack Class
class Node:
	def __init__(self, key, next=None):
		self.key = key
		self.next = next


class Stack:
	def __init__(self):
		self.top = None

  # Adding Elements in Stack using Push Operations
	def push(self, x):

		# Allocate the new node in the heap
		node = Node(x)
		# Check if stack is full, if not then add Element
		if node is None:
			print("Heap Overflow", end='')
			return
		print("Inserting ...", x)
		# set the data in allocated node
		node.data = x
		# Set the .next pointer of the new node to point to the current top node of the list
		node.next = self.top
		# update top pointer
		self.top = node

	# Function to check if the stack is empty or not
	def isEmpty(self):
		return self.top is None

	# Function to return top element in a stack
	def peek(self):

		# check for empty stack
		if not self.isEmpty():
			return self.top.data
		else:
			print("Stack is empty")
			return -1

	# Function to pop top element from the stack
	def pop(self):  # remove at the beginning

		# Check for stack Underflow
		if self.top is None:
			print("Stack Underflow", end='')
			return

		print("Removing ...", self.peek())

		# update the top pointer to point to the next node
		self.top = self.top.next


if __name__ == '__main__':

	stack = Stack()

	stack.push(1)
	stack.push(2)
	stack.push(3)

	print("Top element is: ", stack.peek())

	stack.pop()
	stack.pop()
	stack.pop()

	if stack.isEmpty():
		print("Stack is empty")
	else:
		print("Stack is not empty")

# + [markdown] id="uzGZii1c_zxx"
# ### **Check if Given Expression is Balanced Expression or Not**
#
# <img src="https://drive.google.com/uc?export=view&id=1-Frjs0_9Trap-ugHVOqpG5CpnFtXiyFm" alt ="drawing" width="500"/>
#
#

# + id="ItvQHcCw8OV8" outputId="a1daa15c-eceb-403b-c908-72dc31fc8337" colab={"base_uri": "https://localhost:8080/", "height": 35}
from collections import deque


# Function to Check if the Expression is Balanced or not
def CheckExpression(exp):

	# Check that the Length of the Expression is Even
	if len(exp) & 1:
		return False

	# Make a Stack using DEQUE
	stack = deque()

	# Let's Start Traversing
	for ch in exp:

		# Append into the Stack when Found Open Braces
		if ch == '(' or ch == '{' or ch == '[':
			stack.append(ch)

		# Find the Close Braces
		if ch == ')' or ch == '}' or ch == ']':
			# return false if mismatch is found
			if not stack:
				return False

			# pop character from the stack
			top = stack.pop()

			# if the popped character if not an opening brace or does not pair
			
			if (top == '(' and ch != ')') or (top == '{' and ch != '}' or
											  (top == '[' and ch != ']')):
				return False

	# expression is balanced only if stack is empty at this point
	return not stack

if __name__ == '__main__':

	exp = "{()}[{}"

	if CheckExpression(exp):
		print("The expression is balanced")
	else:
		print("The expression is not balanced")


# + [markdown] id="ocNC9pXOMN6F"
# ### **Find the Duplicate Parenthesis in an Expression**
#
# Like -
#
# **Input**  - ((x+y))+z
#
# **Output** - Duplicate Found 
#
#
# **Input**  - (x+y)
#
# **Output** - Duplicate not Found 
#

# + id="vIqiOdMP_3zy" outputId="f69898a9-e6b1-446e-e429-95d71696723b" colab={"base_uri": "https://localhost:8080/", "height": 35}
from collections import deque

def FindDupParenthesis(exp):

	if len(exp) <= 3:
		return False

	stack = deque()

	for c in exp:
		# if current in the expression is a not a closing parenthesis
		if c != ')':
			stack.append(c)
		# if current in the expression is a closing parenthesis
		else:
			# if we top element in the stack is an opening parenthesis,
			
			if stack[-1] == '(':
				return True

			# pop till '(' is found for current ')'
			while stack[-1] != '(':
				stack.pop()

			# pop '('
			stack.pop()

	# if we reach here, then the expression does not have any duplicate parenthesis
	return False


if __name__ == '__main__':

	exp = "((x+y))"  # assumes valid expression

	if FindDupParenthesis(exp):
		print("The expression have duplicate parenthesis.")
	else:
		print("The expression does not have duplicate parenthesis")


# + [markdown] id="zq0aXwRAhgtH"
# ### **Decode the given sequence to construct minimum number without repeated digits**
#
# **Sequences -> Output**
#
# IIDDIDID -> 125437698
#
# DDDD -> 54321 
#
# I denotes the 'Increasing Sequences' and D denotes the 'Decreasing Sequences', Decode it to construct the minimum number without Repeating digits.

# + id="9kOqCCPOHBDv" outputId="13ab328f-4a6b-4450-cae9-be26a40c6e09" colab={"base_uri": "https://localhost:8080/", "height": 35}
from collections import deque

# Function to decode the given sequence to construct minimum number
# without repeated digits
def decode(seq):
  result = ""
  stack = deque()

  for i in range(len(seq) + 1):
    stack.append(i + 1)
    #print(stack)

    if i == len(seq) or seq[i] == 'I':
      while stack:
        result += str(stack.pop())
    #print(result)
  return result
  

if __name__ == '__main__':

	seq = "DIIDII"	# input sequence

	print("Minimum number is", decode(seq))


# + [markdown] id="GlpXDIfvtDPk"
# ### **Inorder Tree Traversal | Iterative & Recursive**
# ![](https://leetcode.com/articles/Figures/145_transverse.png)
# Trees are traversed in multiple ways in Depth_First_Order(Pre-Order,In-Order, and Post-Order) or Breadth_First_Order(Level Order Traversal)
#
# As We Know Tree is not a linear data-strcuture, that is from a given node there can be more then one possible way to next node.
#
# So For Tranversing the Binary Tree (non-empty) using In-Order Tranversal manner, we do three things for Every **Node N** starting from root node of the Tree -
# 1. (L) Recursively Traverse the Left Subtree, After that Come Again at N
# 2. (N) Process N itself also.
# 3. (R) Recursively Traverse the Right Subtree, After that ome back to N.
#
# In this way we can traverse the Tree using In-Order. (Depth First Search)
#
# ![Image](https://www.techiedelight.com/wp-content/uploads/Inorder-Traversal.png)

# + id="BzpwVIlylAEj" outputId="cf67add7-1596-41d4-966b-967d68bd566d" colab={"base_uri": "https://localhost:8080/", "height": 35}
#Recursive Implementation
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def inorder_rec(root):
  #Return None if Tree is Empty
	if root is None:
		return

  #Traverse the Left Part of the Tree
	inorder_rec(root.left)

	#Display the Data or Number on Node
	print(root.data, end=' ')

	#Traverse the right tree
	inorder(root.right)
 
if __name__ == '__main__':
  root = Node(1)
  root.left = Node(2)
  root.right = Node(3)
  root.left.left = Node(10)
  root.right.left = Node(5)
  root.right.right = Node(11)
  root.right.left.left = Node(7)
  root.right.left.right = Node(8)

  inorder_rec(root)

# + id="lngwes1PlJJ4" outputId="66329096-d6b4-4dc8-88b9-4393c87f984e" colab={"base_uri": "https://localhost:8080/", "height": 35}
#Iterative Implementation
from collections import deque
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def inorder_itr(root):

    stack = deque()
    current = root
    while stack or current:

        # if current node is not None, push to the stack and move to its left child
        if current:
            stack.append(current)
            current = current.left
        else:
            # else if current node is None, we pop an element from the stack,print it and move to right
            current = stack.pop()
            print(current.data, end=' ')

            current = current.right

if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(6)
    root.right.left.left = Node(7)
    root.right.left.right = Node(8)

    inorder_itr(root)


# + [markdown] id="e12G3c-CA3Wp"
# ### **Pre-Order Tree Traversal | Iterative & Recursive**
#
# Trees are traversed in multiple ways in Depth_First_Order(Pre-Order,In-Order, and Post-Order) or Breadth_First_Order(Level Order Traversal)
#
# As We Know Tree is not a linear data-strcuture, that is from a given node there can be more then one possible way to next node.
#
# So For Tranversing the Binary Tree (non-empty) using Pre-Order Tranversal manner, we do three things for Every **Node N** starting from root node of the Tree -
# 1. (N) Process N itself also.
# 2. (L) Recursively Traverse the Left Subtree, After that Come Again at N
# 3. (R) Recursively Traverse the Right Subtree, After that ome back to N.
#
# In this way we can traverse the Tree using In-Order. (Depth First Search)
#
# ![Image](https://www.techiedelight.com/wp-content/uploads/Preorder-Traversal.png)

# + id="GRmgWt5olZwx" outputId="9f329d3a-64e9-4dad-a953-a68f4b5eaecc" colab={"base_uri": "https://localhost:8080/", "height": 35}
#Recursive Implementation
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def preorder_rec(root):

    if root is None:
        return

    print(root.data, end=' ')

    preorder_rec(root.left)

    preorder_rec(root.right)


if __name__ == '__main__':

    root = Node(1)
    root.left = Node(11)
    root.right = Node(6)
    root.left.left = Node(10)
    root.right.left = Node(5)
    root.right.right = Node(2)
    root.right.left.left = Node(13)
    root.right.left.right = Node(8)
    
    preorder_rec(root)


# + id="UwY3pmFOlbAC" outputId="cc2413d4-38ce-40ef-edc9-aba6d76792d4" colab={"base_uri": "https://localhost:8080/", "height": 35}
#Iterative Implementation
from collections import deque

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def preorder_itr(root):

    if root is None:
        return

    stack = deque()
    stack.append(root)

    current = root

    while stack:

        # if current node is not None, print it and push its right child to the stack and move to its left child
        if current:
            print(current.data, end=' ')

            if current.right:
                stack.append(current.right)

            current = current.left
        # else if current node is None, we pop a node from the stack set current node to the popped node
        else:
            current = stack.pop()


if __name__ == '__main__':
    root = Node(1)
    root.left = Node(11)
    root.right = Node(6)
    root.left.left = Node(10)
    root.right.left = Node(5)
    root.right.right = Node(2)
    root.right.left.left = Node(13)
    root.right.left.right = Node(8)

    preorder_itr(root)


# + [markdown] id="JLURUshWEI5V"
# ### **Pre-Order Tree Traversal | Iterative & Recursive**
#
# Trees are traversed in multiple ways in Depth_First_Order(Pre-Order,In-Order, and Post-Order) or Breadth_First_Order(Level Order Traversal)
#
# As We Know Tree is not a linear data-strcuture, that is from a given node there can be more then one possible way to next node.
#
# So For Tranversing the Binary Tree (non-empty) using Pre-Order Tranversal manner, we do three things for Every **Node N** starting from root node of the Tree -
# 1. (L) Recursively Traverse the Left Subtree, After that Come Again at N
# 2. (R) Recursively Traverse the Right Subtree, After that ome back to N.
# 3. (N) Process N itself also.
#
# In this way we can traverse the Tree using In-Order. (Depth First Search)
#
# ![Image](https://www.techiedelight.com/wp-content/uploads/Postorder-Traversal.png)

# + id="wXJN8nXWCZwf" outputId="0216ebfd-bf34-4e83-dd40-7b7dfd83ad71" colab={"base_uri": "https://localhost:8080/", "height": 35}
#Recursive Implementation
class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def postorder(root):
    if root is None:
        return

    postorder(root.left)

    postorder(root.right)

    print(root.data, end=' ')


if __name__ == '__main__':
    root = Node(1)
    root.left = Node(11)
    root.right = Node(6)
    root.left.left = Node(10)
    root.right.left = Node(5)
    root.right.right = Node(2)
    root.right.left.left = Node(13)
    root.right.left.right = Node(8)

    postorder_rec(root)


# + id="wsHEV5_DEmKh" outputId="08a38f09-9081-42a5-9069-4cefc468ed06" colab={"base_uri": "https://localhost:8080/", "height": 35}
#Iterative Implementation
from collections import deque
class Node:
    def __init__(self, key):
        self.data = key
        self.left = self.right = None

def postorderIterative(root):

    stack = deque()
    stack.append(root)

    out = deque()

    while stack:

        current = stack.pop()
        out.append(current.data)

        if current.left:
            stack.append(current.left)

        if current.right:
            stack.append(current.right)

    while out:
        print(out.pop(), end=' ')


if __name__ == '__main__':
    root = Node(1)
    root.left = Node(11)
    root.right = Node(6)
    root.left.left = Node(10)
    root.right.left = Node(5)
    root.right.right = Node(2)
    root.right.left.left = Node(13)
    root.right.left.right = Node(8)

    postorderIterative(root)



# + id="yB-Ay0AuFLTQ"
#Delete without head pointer
def deleteNode(curr_node):
    temp = curr_node.next
    curr_node.data = temp.data 
    curr_node.next = temp.next

# + id="fAdccY2RJE8n"


StarcoderdataJupyterScriptsDedupFiltered