Find an equal point in a string of brackets - GeeksforGeeks

Find an equal point in a string of brackets - GeeksforGeeks
Given a string of brackets, the task is to find an index k which decides the number of opening brackets is equal to the number of closing brackets.
String must be consists of only opening and closing brackets i.e. '(' and ')'.
An equal point is an index such that the number of opening brackets before it is equal to the number of closing brackets from and after.

1. Store the number of opening brackets appears in the string up to every index, it must start from starting index.
2. Similarly, Store the number of closing brackets appears in the string upto each and every index but it should be done from last index.
3. Check if any index has the same value of opening and closing brackets.

// Function to find an equal index

int findIndex(string str)

{

    int len = str.length();

    int open[len+1], close[len+1];

    int index = -1;

    memset(open, 0, sizeof (open));

    memset(close, 0, sizeof (close));

 

    open[0] = 0;

    close[len] = 0;

    if (str[0]=='(')

        open[1] = 1;

    if (str[len-1] == ')')

        close[len-1] = 1;

 

    // Store the number of opening brackets

    // at each index

    for (int i = 1; i < len; i++)

    {

        if ( str[i] == '(' )

            open[i+1] = open[i] + 1;

        else

            open[i+1] = open[i];

    }

 

    // Store the number of closing brackets

    // at each index

    for (int i = len-2; i >= 0; i--)

    {

        if ( str[i] == ')' )

            close[i] = close[i+1] + 1;

        else

            close[i] = close[i+1];

    }

 

    // check if there is no opening or closing

    // brackets

    if (open[len] == 0)

        return len;

    if (close[0] == 0)

        return 0;

 

    // check if there is any index at which

    // both brackets are equal

    for (int i=0; i<=len; i++)

        if (open[i] == close[i])

            index = i;

 

    return index;

}

Read full article from Find an equal point in a string of brackets - GeeksforGeeks