Find maximum depth of nested parenthesis in a string

QUESTION

We are given a string having parenthesis like below\n ( ((X)) (((Y))) )\nWe need to find the maximum depth of balanced parenthesis, like 4 in above example. Since Y is surrounded by 4 balanced parenthesis.\n\nIf parenthesis are unbalanced then return -1.

“TESTCASE_1”: “( a(b) (c) (d(e(f)g)h) I (j(k)l)m)\n###—###SEPERATOR—###—\n4”, “TESTCASE_2”: “( p((q)) ((s)t) )\n###—###SEPERATOR—###—\n3”, “TESTCASE_3”: “b) (c) ()\n###—###SEPERATOR—###—\n-1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>
#include <stdio.h>
using namespace std;
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()
{
  char s[50];
  scanf("%[^\n]s",s);
    //string s = "( ((X)) (((Y))) )";
    cout << maxDepth(s);
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.