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

  • Find the matching brackets

    Given a string of opening and closing brackets, you are asked to find the matching opening bracket for each closing bracket. It’s guaranteed that the given sequence of brackets is valid.

    Input

    The input contains a single line s (1 ≀ |s| ≀ ).

    Output

    For each closing bracket, the program should print the index of its corresponding opening one. The indices should be separated by a space.

    Examples

    Input
    Output
    (()())
    2 4 1
    ((()))
    3 2 1
    ()()()
    1 3 5

    Explanation

    1. (()())
      1. Bracket
        (
        (
        )
        (
        )
        )
        Index
        1
        2
        3
        4
        5
        6
        Opening index
        -
        -
        2
        -
        4
        1
    1. ((()))
      1. Bracket
        (
        (
        (
        )
        )
        )
        Index
        1
        2
        3
        4
        5
        6
        Opening index
        -
        -
        -
        3
        2
        1
    1. ()()()
      1. Bracket
        (
        )
        (
        )
        (
        )
        Index
        1
        2
        3
        4
        5
        6
        Opening index
        -
        1
        -
        3
        -
        5
    Β 
    Β 

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 10 MB

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