Tutorialspoint.dev

Find maximum depth of nested parenthesis in a string

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.

Examples :

Input : S = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)";
Output : 4

Input : S = "( p((q)) ((s)t) )";
Output : 3

Input : S = "";
Output : 0

Input : S = "b) (c) ()";
Output : -1 

Input : S = "(b) ((c) ()"
Output : -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 )
This can also be done without using stack.



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

Below is the implementation of above algorithm.

C/C++

// A C++ program to find the maximum depth of nested
// parenthesis in a given expression
#include <iostream>
using namespace std;
  
// function takes a string and returns the
// maximum depth nested parenthesis
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;
}
  
// Driver program
int main()
{
    string s = "( ((X)) (((Y))) )";
    cout << maxDepth(s);
    return 0;
}

Java

//Java program to find the maximum depth of nested 
// parenthesis in a given expression 
  
class GFG {
// function takes a string and returns the 
// maximum depth nested parenthesis 
  
    static 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.charAt(i) == '(') {
                current_max++;
  
                // update max if required 
                if (current_max > max) {
                    max = current_max;
                }
            } else if (S.charAt(i) == ')') {
                if (current_max > 0) {
                    current_max--;
                } else {
                    return -1;
                }
            }
        }
  
        // finally check for unbalanced string 
        if (current_max != 0) {
            return -1;
        }
  
        return max;
    }
  
// Driver program 
    public static void main(String[] args) {
        String s = "( ((X)) (((Y))) )";
        System.out.println(maxDepth(s));
    }
}

Python

# A Python program to find the maximum depth of nested
# parenthesis in a given expression
  
# function takes a string and returns the
# maximum depth nested parenthesis
def maxDepth(S):
    current_max = 0
    max = 0
    n = len(S)
  
    # Traverse the input string
    for i in xrange(n):
        if S[i] == '(':
            current_max += 1
  
            if current_max > max:
                max = current_max
        elif S[i] == ')':
            if current_max > 0:
                current_max -= 1
            else:
                return -1
  
    # finally check for unbalanced string
    if current_max != 0:
        return -1
  
    return max
  
# Driver program
s = "( ((X)) (((Y))) )"
print maxDepth(s)
  
# This code is contributed by BHAVYA JAIN

PHP

<?php
// A PHP program to find the 
// maximum depth of nested 
// parenthesis in a given
// expression
  
// function takes a string  
// and returns the maximum 
// depth nested parenthesis
function maxDepth($S)
{
    // current count
    $current_max = 0; 
      
    // overall maximum count
    $max = 0; 
    $n = strlen($S);
  
    // Traverse the input string
    for ($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;
}
  
// Driver Code
$s = "( ((X)) (((Y))) )";
echo maxDepth($s);
  
// This code is contributed by mits
?>


Output :

 4 

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter