Find maximum depth of nested parenthesis in a string - GeeksforGeeks

Find maximum depth of nested parenthesis in a string - GeeksforGeeks
We are given a string having parenthesis like below
     "( ((X)) (((Y))) )"
We need to find the maximum depth of balanced parenthesis, like 4 in above example. Since 'Y' is surrounded by 4 balanced parenthesis.
If parenthesis are unbalanced then return -1.

Method 1 (Uses Stack)
A simple solution is to use a stack that keeps track of current open brackets.

1) Create a stack. 
2) Traverse the string, do following for every character
     a) If current character is ‘(’ push it to the stack .
     b) If character is ‘)’, pop an element.
     c) Maintain maximum count during the traversal. 

Time Complexity : O(n)
Auxiliary Space : O(n)

Method 2 ( O(1) auxiliary space )

1) Take two variables max and current_max, initialize both of them as 0.

2) Traverse the string, do following for every character
    a) If current character is ‘(’, increment current_max and 
       update max value if required.
    b) If character is ‘)’. Check if current_max is positive or
       not (this condition ensure that parenthesis are balanced). 
       If positive that means we previously had a ‘(’ character 
       so decrement current_max without worry. 
       If not positive then the parenthesis are not balanced. 
       Thus return -1. 
3) If current_max is not 0, then return -1 to ensure that the parenthesis
   are balanced. Else return max

int maxDepth(string S)

{

    int current_max = 0; // current count

    int max = 0;    // overall maximum count

    int n = S.length();

 

    // Traverse the input string

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

    {

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

        {

            current_max++;

 

            // update max if required

            if (current_max> max)

                max = current_max;

        }

        else if (S[i] == ')')

        {

            if (current_max>0)

                current_max--;

            else

                return -1;

        }

    }

 

    // finally check for unbalanced string

    if (current_max != 0)

        return -1;

 

    return max;

}

http://comproguide.blogspot.com/2015/03/maximum-nesting-depth-of-paranthesis.html
Read full article from Find maximum depth of nested parenthesis in a string - GeeksforGeeks