<jupyter_start><jupyter_text>Stack &copy;  [<NAME>](<EMAIL>)  Industrial and Enterprise Systems Engineering, The Grainger College of Engineering,  UIUC   Implement Stack using Queues<jupyter_code># Program to implement a stack using 
# two queue 
from queue import Queue
  
class Stack:
      
    def __init__(self):
          
        # Two inbuilt queues 
        self.q1 = Queue()
        self.q2 = Queue() 
              
        # To maintain current number 
        # of elements
        self.curr_size = 0
  
    def push(self, x):
        self.curr_size += 1
  
        # Push x first in empty q2 
        self.q2.put(x) 
  
        # Push all the remaining 
        # elements in q1 to q2. 
        while (not self.q1.empty()):
            self.q2.put(self.q1.queue[0]) 
            self.q1.get()
  
        # swap the names of two queues 
        self.q = self.q1 
        self.q1 = self.q2 
        self.q2 = self.q
  
    def pop(self):
  
        # if no elements are there in q1 
        if (self.q1.empty()): 
            return
        self.q1.get() 
        self.curr_size -= 1
  
    def top(self):
        if (self.q1.empty()):
            return -1
        return self.q1.queue[0]
  
    def size(self):
        return self.curr_size
  
# Driver Code 
if __name__ == '__main__':
    s = Stack()
    s.push(1) 
    s.push(2) 
    s.push(3) 
  
    print("current size: ", s.size())
    print(s.top()) 
    s.pop() 
    print(s.top()) 
    s.pop() 
    print(s.top()) 
  
    print("current size: ", s.size())
# Program to implement a stack using 
# two queue 
from queue import Queue
  
class Stack:
      
    def __init__(self):
          
        # Two inbuilt queues 
        self.q1 = Queue()
        self.q2 = Queue() 
              
        # To maintain current number 
        # of elements
        self.curr_size = 0
  
    def push(self, x):
        self.curr_size += 1
  
        # Push x first in empty q2 
        self.q1.put(x) 
  
  
    def pop(self):
        
        while self.curr_size != 1 or not self.q1.empty():
            self.q2.put(self.q1.queue[0])
            self.q1.get()
        popped_item = self.q1.get()
        
        # swap the names of two queues 
        self.q = self.q1 
        self.q1 = self.q2 
        self.q2 = self.q
           
        self.curr_size -= 1
        
        return popped_item
  
    def top(self):
        if (self.q1.empty()):
            return -1
        return self.q1.queue[0]
  
    def size(self):
        return self.curr_size
  
# Driver Code 
if __name__ == '__main__':
    s = Stack()
    s.push(1) 
    s.push(2) 
    s.push(3) 
  
    print("current size: ", s.size())
    print(s.top()) 
    s.pop() 
    print(s.top()) 
    s.pop() 
    print(s.top()) 
  
    print("current size: ", s.size())<jupyter_output>current size:  3
1<jupyter_text>Design a stack that supports getMin() in O(1) time and O(1) extra space<jupyter_code># Class to make a Node
class Node:
    # Constructor which assign argument to nade's value
    def __init__(self, value):
        self.value = value
        self.next = None
 
    # This method returns the string representation of the object.
    def __str__(self):
        return "Node({})".format(self.value)
     
    # __repr__ is same as __str__
    __repr__ = __str__
 
 
class Stack:
    # Stack Constructor initialise top of stack and counter.
    def __init__(self):
        self.top = None
        self.count = 0
        self.minimum = None
         
    # This method returns the string representation of the object (stack).
    def __str__(self):
        temp = self.top
        out = []
        while temp:
            out.append(str(temp.value))
            temp = temp.next
        out = '\n'.join(out)
        return ('Top {} \n\nStack :\n{}'.format(self.top,out))
         
    # __repr__ is same as __str__
    __repr__=__str__
     
    # This method is used to get minimum element of stack
    def getMin(self):
        if self.top is None:
            return "Stack is empty"
        else:
            print("Minimum Element in the stack is: {}" .format(self.minimum))
 
 
 
    # Method to check if Stack is Empty or not
    def isEmpty(self):
        # If top equals to None then stack is empty
        if self.top == None:
            return True
        else:
        # If top not equal to None then stack is empty
            return False
 
    # This method returns length of stack    
    def __len__(self):
        self.count = 0
        tempNode = self.top
        while tempNode:
            tempNode = tempNode.next
            self.count+=1
        return self.count
 
    # This method returns top of stack    
    def peek(self):
        if self.top is None:
            print ("Stack is empty")
        else:
            if self.top.value < self.minimum:
                print("Top Most Element is: {}" .format(self.minimum))
            else:
                print("Top Most Element is: {}" .format(self.top.value))
 
    # This method is used to add node to stack
    def push(self,value):
        if self.top is None:
            self.top = Node(value)
            self.minimum = value
         
        elif value < self.minimum:
            temp = (2 * value) - self.minimum
            new_node = Node(temp)
            new_node.next = self.top
            self.top = new_node
            self.minimum = value
        else:
            new_node = Node(value)
            new_node.next = self.top
            self.top = new_node
        print("Number Inserted: {}" .format(value))
 
    # This method is used to pop top of stack
    def pop(self):
        if self.top is None:
            print( "Stack is empty")
        else:
            removedNode = self.top.value
            self.top = self.top.next
            if removedNode < self.minimum:
                print ("Top Most Element Removed :{} " .format(self.minimum))
                self.minimum = ( ( 2 * self.minimum ) - removedNode )
            else:
                print ("Top Most Element Removed : {}" .format(removedNode))
 
                 
             
     
# Driver program to test above class
stack = Stack()
 
stack.push(3)
stack.push(5)
stack.getMin()
stack.push(2)
stack.push(1)
stack.getMin()    
stack.pop()
stack.getMin()
stack.pop()
stack.peek()<jupyter_output>Number Inserted: 3
Number Inserted: 5
Minimum Element in the stack is: 3
Number Inserted: 2
Number Inserted: 1
Minimum Element in the stack is: 1
Top Most Element Removed :1 
Minimum Element in the stack is: 2
Top Most Element Removed :2 
Top Most Element is: 5<jupyter_text>Check for Balanced Brackets in an expression (well-formedness) using Stack<jupyter_code># Python3 program to check for
# balanced brackets.
 
# function to check if
# brackets are balanced
 
 
def areBracketsBalanced(expr):
    stack = []
 
    # Traversing the Expression
    for char in expr:
        if char in ["(", "{", "["]:
 
            # Push the element in the stack
            stack.append(char)
        else:
 
            # IF current character is not opening
            # bracket, then it must be closing.
            # So stack cannot be empty at this point.
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == '(':
                if char != ")":
                    return False
            if current_char == '{':
                if char != "}":
                    return False
            if current_char == '[':
                if char != "]":
                    return False
 
    # Check Empty Stack
    if stack:
        return False
    return True
 
 
# Driver Code
if __name__ == "__main__":
    expr = "{()}[]"
 
    # Function call
    if areBracketsBalanced(expr):
        print("Balanced")
    else:
        print("Not Balanced")<jupyter_output>Balanced<jupyter_text>Next Greater Element<jupyter_code># Python program to print next greater element using stack
 
# Stack Functions to be used by printNGE()
 
 
def createStack():
    stack = []
    return stack
 
 
def isEmpty(stack):
    return len(stack) == 0
 
 
def push(stack, x):
    stack.append(x)
 
 
def pop(stack):
    if isEmpty(stack):
        print("Error : stack underflow")
    else:
        return stack.pop()
 
 
'''prints element and NGE pair for all elements of
   arr[] '''
 
 
def printNGE(arr):
    s = createStack()
    element = 0
    next = 0
 
    # push the first element to stack
    push(s, arr[0])
 
    # iterate for rest of the elements
    for i in range(1, len(arr), 1):
        next = arr[i]
 
        if isEmpty(s) == False:
 
            # if stack is not empty, then pop an element from stack
            element = pop(s)
 
            '''If the popped element is smaller than next, then
                a) print the pair
                b) keep popping while elements are smaller and
                   stack is not empty '''
            while element < next:
                print(str(element) + " -- " + str(next))
                if isEmpty(s) == True:
                    break
                element = pop(s)
 
            '''If element is greater than next, then push
               the element back '''
            if element > next:
                push(s, element)
 
        '''push next to stack so that we can find
           next greater for it '''
        push(s, next)
 
    '''After iterating over the loop, the remaining
       elements in stack do not have the next greater
       element, so print -1 for them '''
 
    while isEmpty(s) == False:
        element = pop(s)
        next = -1
        print(str(element) + " -- " + str(next))
 
 
# Driver code
arr = [11, 13, 21, 3]
printNGE(arr)
 
# Python3 code
class Solution:
    def nextLargerElement(self,arr,n):
        #code here
        s=[]
        for i in range(len(arr)):
            while s and s[-1].get("value") < arr[i]:
                d = s.pop()
                arr[d.get("ind")] = arr[i]
            s.append({"value": arr[i], "ind": i})
        while s:
            d = s.pop()
            arr[d.get("ind")] = -1
        return arr
         
if __name__ == "__main__":
    print(Solution().nextLargerElement([6,8,0,1,3],5))<jupyter_output>[8, -1, 1, 3, -1]<jupyter_text>Expression Evaluation<jupyter_code># Python3 program to evaluate a given
# expression where tokens are
# separated by space.
 
# Function to find precedence
# of operators.
def precedence(op):
     
    if op == '+' or op == '-':
        return 1
    if op == '*' or op == '/':
        return 2
    return 0
 
# Function to perform arithmetic
# operations.
def applyOp(a, b, op):
     
    if op == '+': return a + b
    if op == '-': return a - b
    if op == '*': return a * b
    if op == '/': return a // b
 
# Function that returns value of
# expression after evaluation.
def evaluate(tokens):
     
    # stack to store integer values.
    values = []
     
    # stack to store operators.
    ops = []
    i = 0
     
    while i < len(tokens):
         
        # Current token is a whitespace,
        # skip it.
        if tokens[i] == ' ':
            i += 1
            continue
         
        # Current token is an opening
        # brace, push it to 'ops'
        elif tokens[i] == '(':
            ops.append(tokens[i])
         
        # Current token is a number, push
        # it to stack for numbers.
        elif tokens[i].isdigit():
            val = 0
             
            # There may be more than one
            # digits in the number.
            while (i < len(tokens) and
                tokens[i].isdigit()):
             
                val = (val * 10) + int(tokens[i])
                i += 1
             
            values.append(val)
             
            # right now the i points to
            # the character next to the digit,
            # since the for loop also increases
            # the i, we would skip one
            #  token position; we need to
            # decrease the value of i by 1 to
            # correct the offset.
            i-=1
         
        # Closing brace encountered,
        # solve entire brace.
        elif tokens[i] == ')':
         
            while len(ops) != 0 and ops[-1] != '(':
             
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                 
                values.append(applyOp(val1, val2, op))
             
            # pop opening brace.
            ops.pop()
         
        # Current token is an operator.
        else:
         
            # While top of 'ops' has same or
            # greater precedence to current
            # token, which is an operator.
            # Apply operator on top of 'ops'
            # to top two elements in values stack.
            while (len(ops) != 0 and
                precedence(ops[-1]) >=
                   precedence(tokens[i])):
                         
                val2 = values.pop()
                val1 = values.pop()
                op = ops.pop()
                 
                values.append(applyOp(val1, val2, op))
             
            # Push current token to 'ops'.
            ops.append(tokens[i])
         
        i += 1
     
    # Entire expression has been parsed
    # at this point, apply remaining ops
    # to remaining values.
    while len(ops) != 0:
         
        val2 = values.pop()
        val1 = values.pop()
        op = ops.pop()
                 
        values.append(applyOp(val1, val2, op))
     
    # Top of 'values' contains result,
    # return it.
    return values[-1]
 
# Driver Code
if __name__ == "__main__":
     
    print(evaluate("10 + 2 * 6"))
    print(evaluate("100 * 2 + 12"))
    print(evaluate("100 * ( 2 + 12 )"))
    print(evaluate("100 * ( 2 + 12 ) / 14"))<jupyter_output>22
212
1400
100<jupyter_text>6. The Stock Span Problem<jupyter_code># Python linear time solution for stock span problem
 
# A stack based efficient method to calculate s
def calculateSpan(price, S):
     
    n = len(price)
    # Create a stack and push index of fist element to it
    st = []
    st.append(0)
 
    # Span value of first element is always 1
    S[0] = 1
 
    # Calculate span values for rest of the elements
    for i in range(1, n):
         
        # Pop elements from stack whlie stack is not
        # empty and top of stack is smaller than price[i]
        while( len(st) > 0 and price[st[-1]] <= price[i]):
            st.pop()
 
        # If stack becomes empty, then price[i] is greater
        # than all elements on left of it, i.e. price[0],
        # price[1], ..price[i-1]. Else the price[i] is
        # greater than elements after top of stack
        S[i] = i + 1 if len(st) <= 0 else (i - st[-1])
 
        # Push this element to stack
        st.append(i)
 
 
# A utility function to print elements of array
def printArray(arr, n):
    for i in range(0, n):
        print (arr[i], end =" ")
 
 
# Driver program to test above function
price = [10, 4, 5, 90, 120, 80]
S = [0 for i in range(len(price)+1)]
 
# Fill the span values in array S[]
calculateSpan(price, S)
 
# Print the calculated span values
printArray(S, len(price))<jupyter_output>1 1 2 4 5 1<jupyter_text>7. Largest Rectangular Area in a Histogram | Set 2<jupyter_code># Python3 program to find maximum
# rectangular area in linear time
 
def max_area_histogram(histogram):
     
    # This function calulates maximum
    # rectangular area under given
    # histogram with n bars
 
    # Create an empty stack. The stack
    # holds indexes of histogram[] list.
    # The bars stored in the stack are
    # always in increasing order of
    # their heights.
    stack = list()
 
    max_area = 0 # Initialize max area
 
    # Run through all bars of
    # given histogram
    index = 0
    while index < len(histogram):
         
        # If this bar is higher
        # than the bar on top
        # stack, push it to stack
 
        if (not stack) or (histogram[stack[-1]] <= histogram[index]):
            stack.append(index)
            index += 1
 
        # If this bar is lower than top of stack,
        # then calculate area of rectangle with
        # stack top as the smallest (or minimum
        # height) bar.'i' is 'right index' for
        # the top and element before top in stack
        # is 'left index'
        else:
            # pop the top
            top_of_stack = stack.pop()
 
            # Calculate the area with
            # histogram[top_of_stack] stack
            # as smallest bar
            area = (histogram[top_of_stack] *
                   ((index - stack[-1] - 1)
                   if stack else index))
 
            # update max area, if needed
            max_area = max(max_area, area)
 
    # Now pop the remaining bars from
    # stack and calculate area with
    # every popped bar as the smallest bar
    while stack:
         
        # pop the top
        top_of_stack = stack.pop()
 
        # Calculate the area with
        # histogram[top_of_stack]
        # stack as smallest bar
        area = (histogram[top_of_stack] *
              ((index - stack[-1] - 1)
                if stack else index))
 
        # update max area, if needed
        max_area = max(max_area, area)
 
    # Return maximum area under
    # the given histogram
    return max_area
 
# Driver Code
hist = [6, 2, 5, 4, 5, 1, 6]
print("Maximum area is",
       max_area_histogram(hist))
#this is single line comment
"""
this
is
multiline
comment
"""
def getMaxArea(arr):
  s = [-1]
  n = len(arr)
  area = 0
  i = 0
  left_smaller = [-1]*n
  right_smaller = [n]*n
  while i < n:
      while s and (s[-1] != -1) and (arr[s[-1]] > arr[i]):
          right_smaller[s[-1]] = i
          s.pop()
      if((i > 0) and (arr[i] == arr[i-1])):
          left_smaller[i] = left_smaller[i-1]
      else:
          left_smaller[i] = s[-1]
      s.append(i)
      i += 1
  for j in range(0, n):
      area = max(area, arr[j]*(right_smaller[j]-left_smaller[j]-1))
  return area
 
hist = [6, 2, 5, 4, 5, 1, 6]
print("maxArea = ", getMaxArea(hist))<jupyter_output>maxArea =  12<jupyter_text>8. Minimum number of bracket reversals needed to make an expression balanced<jupyter_code># Python3 program to find minimum number of
# reversals required to balance an expression
 
# Returns count of minimum reversals
# for making expr balanced. Returns -1
# if expr cannot be balanced.
def countMinReversals(expr):
 
    lenn = len(expr)
 
    # length of expression must be even
    # to make it balanced by using reversals.
    if (lenn % 2) :
        return -1
 
    # After this loop, stack contains
    # unbalanced part of expression, 
    # i.e., expression of the form "...."
    s = []
    for i in range(lenn):
        if (expr[i] =='' and len(s)):
 
            if (s[0] == '') :
                s.pop(0)
            else:
                s.insert(0, expr[i])
        else:
            s.insert(0, expr[i])
     
    # Length of the reduced expression
    # red_len = (m+n)
    red_len = len(s)
 
    # count opening brackets at the
    # end of stack
    n = 0
    while (len(s)and s[0] == '') :
            s.pop(0)
            n += 1
 
    # return ceil(m/2) + ceil(n/2) which
    # is actually equal to (m+n)/2 + n%2
    # when m+n is even.
    return (red_len // 2 + n % 2)
 
# Driver Code
if __name__ == '__main__':
 
    expr = "}}{{"
    print(countMinReversals(expr.strip()))<jupyter_output>2<jupyter_text>9. Iterative Depth First Traversal of Graph<jupyter_code># An Iterative Python program to do DFS traversal from
# a given source vertex. DFS(int s) traverses vertices
# reachable from s.
 
# This class represents a directed graph using adjacency
# list representation
class Graph:
    def __init__(self,V): # Constructor
        self.V = V        # No. of vertices
        self.adj  = [[] for i in range(V)]  # adjacency lists
 
    def addEdge(self,v, w):     # to add an edge to graph
        self.adj[v].append(w)    # Add w to v’s list.
 
 
    # prints all not yet visited vertices reachable from s
    def DFS(self,s):            # prints all vertices in DFS manner from a given source.
                                # Initially mark all verices as not visited
        visited = [False for i in range(self.V)]
 
        # Create a stack for DFS
        stack = []
 
        # Push the current source node.
        stack.append(s)
 
        while (len(stack)):
            # Pop a vertex from stack and print it
            s = stack[-1]
            stack.pop()
 
            # Stack may contain same vertex twice. So
            # we need to print the popped item only
            # if it is not visited.
            if (not visited[s]):
                print(s,end=' ')
                visited[s] = True
 
            # Get all adjacent vertices of the popped vertex s
            # If a adjacent has not been visited, then push it
            # to the stack.
            for node in self.adj[s]:
                if (not visited[node]):
                    stack.append(node)
 
 
 
# Driver program to test methods of graph class
 
g = Graph(5); # Total 5 vertices in graph
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(1, 4);
 
print("Following is Depth First Traversal")
g.DFS(0)
# An Iterative Python3 program to do DFS
# traversal from a given source vertex.
# DFS(s) traverses vertices reachable from s.
class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
     
    def addEdge(self, v, w):
        self.adj[v].append(w) # Add w to v’s list.
     
    # prints all not yet visited vertices
    # reachable from s
    def DFSUtil(self, s, visited):
         
        # Create a stack for DFS
        stack = []
     
        # Push the current source node.
        stack.append(s)
     
        while (len(stack) != 0):
             
            # Pop a vertex from stack and print it
            s = stack.pop()
     
            # Stack may contain same vertex twice.
            # So we need to prthe popped item only
            # if it is not visited.
            if (not visited[s]):
                print(s, end = " ")
                visited[s] = True
     
            # Get all adjacent vertices of the
            # popped vertex s. If a adjacent has not 
            # been visited, then push it to the stack.
            i = 0
            while i < len(self.adj[s]):
                if (not visited[self.adj[s][i]]):
                    stack.append(self.adj[s][i])
                i += 1
     
    # prints all vertices in DFS manner
    def DFS(self):
         
        # Mark all the vertices as not visited
        visited = [False] * self.V
        for i in range(self.V):
            if (not visited[i]):
                self.DFSUtil(i, visited)
 
# Driver Code
if __name__ == '__main__':
 
    g = Graph(5) # Total 5 vertices in graph
    g.addEdge(1, 0)
    g.addEdge(2, 1)
    g.addEdge(3, 4)
    g.addEdge(4, 0)
 
    print("Following is Depth First Traversal")
    g.DFS()
 
s = "Shared Documents/currency_rates_PowerAutomate.xlsx"
s.split('/')[-2]
"Shared Documents/folder/currency_rates_PowerAutomate.xlsx\"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10221053992329901, 'fraction_numerical': 0.01288404360753221, 'mean_word_length': 1.6596378638551454, 'pattern_counts': {'":': 8, '<': 44, '<?xml version=': 0, '>': 36, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '138244', 'license': 'MIT', 'n_tokens_mistral': 7349, 'n_tokens_neox': 6859, 'n_words': 2369, 'path': 'ds/stack.ipynb', 'repo_name': 'OmkarMehta/ds-algo', 'size': '23225'}