Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Stack

    Stack is one of the most popular data structures used in algorithms. When using stacks, the elements added last would be the first ones to be removed. It's like a stack of plates, where the plate on top is the only one that can be removed until all the plates on top of it are taken away.
    A stack can be used in many real-world situations. When opening websites in a web browser, you can click on the back button to move to the previous page. The history of pages could be stored in a stack, and as soon as you hit a back button you can be navigated to the top of the stack. If you hit back again, the top page from the stack is removed, and you are navigated to the one below it.
    notion image
    There are several ways of implementing a stack in a programming language like Python:
    1. Using list - the top element of the queue will be the last element of the list. We can add with append, remove with pop, and get the element with [-1].
    1. Using deque from collections - it supports adding and removing elements from both the start and the end.
    1. LifoQueue from queue - Last-in-first-out queue, which is essentially the definition of the stack data structure.
    from queue import LifoQueue
    stack = LifoQueue()
    
    # push
    stack.put(1)
    stack.put(2)
    stack.put(3)
    
    # pop
    print(stack.get())      # prints 3
    print(stack.get())      # prints 2
    
    # peek
    print(stack.queue[-1])  # prints 1
    print(stack.empty())    # check if empty -> prints False
    # Using a simple list
    stack = []
    
    # push
    stack.append(1)
    stack.append(2)
    stack.append(3)
    
    # pop
    print(stack.pop())      # prints 3
    print(stack.pop())      # prints 2
    
    # peek
    print(stack[-1])        # prints 1
    print(len(stack) == 0)  # check if empty -> prints False

    Challenge: Check if the sequence of brackets is valid

    Given a sequence of brackets of a mathematical expression (i.e. (()())), you are asked to check if that sequence is valid. A sequence of brackets is valid if every opening bracket has a corresponding closing one and there are no extra opening or closing brackets.

    Input

    The only line of the input contains a single line b (1 ≀ |b| ≀ ) containing the bracket sequence.

    Output

    The program should print Yes in case the bracket sequence is valid, and No otherwise.

    Examples

    Input
    Output
    ()()
    Yes
    ())()(
    No
    ((()())())
    Yes
    Β 

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue